On 30/12/2010, at 8:40 PM, Mark Engelberg wrote: > 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. Isn't that the problem though? This will make the best case inefficient since the work performed by into is proportional to the length of v2 (or v1 if you swap them around). Therefore, even thought the list is sorted you still need to traverse v2. A simple fix would be checking (= i 0) but that's kinda ugly. > > 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 have no experience with finger trees what so ever. I only understand Meikels comment now :)
> > 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 -- “There is a strong correlation between being smart and being a nerd, and an even stronger inverse correlation between being a nerd and being popular” (Paul Graham) -- ********************************************************** Andreas Koestler, Software Engineer Leica Geosystems Pty Ltd 270 Gladstone Road, Dutton Park QLD 4102 Main: +61 7 3891 9772 Direct: +61 7 3117 8808 Fax: +61 7 3891 9336 Email: andreas.koest...@leica-geosystems.com ************www.leica-geosystems.com************* when it has to be right, Leica Geosystems Please consider the environment before printing this email. -- 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
