4 ms·

I mean, in Lisp your go-to structure will likely be unbalanced trees Which like Quicksort (nearly the same analysis btw), has exceptional average case performa

I mean, in Lisp your go-to structure will likely be unbalanced trees Which like Quicksort (nearly the same analysis btw), has exceptional average case performance (even faster than RB trees on the average !!!!) but the downside of horrific O(n^2) performance on the worst case. RBTrees or AVL trees all help at improving those worst cases (AVL strangely has its best case be the worst case of unbalanced trees lol). In any case, there's a lot of tree flavors. Lisp is certainly sufficient and simple when it's exploring these different details. Unbalanced trees, in any case, is actually a reasonably sane default. RB Tree or AVL is probably a better default but don't knock the unbalanced tree before you try it!! ------------ I've heard of highly optimized lisps where the typical list is turned into an array or at least a rope in the average case btw.

shawn_w 1y ago
>In any case, there's a lot of tree flavors. Lisp is certainly sufficient and simple when it's exploring these different details. I've become a fan of scapegoat trees¹ lately for (immutable) balanced trees. There are certainly a ton of other options besides RB and AVL trees that are fun to explore (in any language) >I've heard of highly optimized lisps where the typical list is turned into an array... Back in the lisp machine days there was CDR coding² to flatten out a list into a contiguous block, but I'm not sure if any modern common lisp or scheme implementations use it. [1]: https://en.wikipedia.org/wiki/Scapegoat_tree https://en.wikipedia.org/wiki/Scapegoat_tree [2]: https://en.wikipedia.org/wiki/CDR_coding https://en.wikipedia.org/wiki/CDR_coding