On Thu, Dec 30, 2010 at 3:24 AM, Andreas Kostler <andreas.koestler.le...@gmail.com> wrote: > Oh, vectors are indeed bad since vector concatenation is a linear time > operation. > My apologies to Meikel, I simply missed your remark about finger trees. > I guess a version that swaps the values "in place" would be the way to go.
When you perform (into v1 v2), the length of the time it takes is proportional to the length of v2. This is similar to the amount of work done when doing a list insertion (must rebuild the portion of the list up to the insertion point, but not the entire list. As for finger trees, I have not found them to be useful. Although they have good theoretical bounds, they are very slow in practice. For example, if you try splitting, concatenating, and traversing lists of, say, 100000 elements, these operations on finger trees are still many times slower than just using a naive take/drop/concat/seq on a regular list. How many millions of elements do you need to have for the so-called "fast" finger tree operations to be worth the overhead? I think it is highly unlikely that you will see any speed improvement by converting insertion sort to finger trees, but feel free to try. [Note: This is just based on my own personal benchmarking, and I would love to be proven wrong about finger trees], -- 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
