On Thu, Dec 30, 2010 at 9:50 PM, Ken Wesson <kwess...@gmail.com> wrote: > Are these searches, which should be log n? Or full (e.g. in-order) traversals?
I'm talking about full traversals. Finger trees are sequences, and after building the sequence, splitting, concatenating, or whatever, I find I eventually need to visit all the elements. This is something like a hundred times slower on a large finger tree than a basic sequence. I had tried a couple years back to implement finger trees in Racket, and found it too slow to be of use. Recently, when I saw chouser had developed an implementation in Clojure (https://github.com/clojure/data.finger-tree), I eagerly checked it out to see if his implementation worked better than my own effort. It's definitely faster than my Racket attempt, but I still found it to be quite slow. I hope I'm incorrect and someone can show me a good demonstration of an application where finger trees outperform Clojure's built-in sequences. But my impression is that even though they are "asymptotically fast", the constant factors are too large, and even for lists of hundreds of thousands of elements, you'd be better off, for example, doing an "inefficient" concatenation of Clojure's vectors than the "efficient" concatenation of a finger tree. Play around with chouser's implementation and let me know what you find. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
