On Fri, Mar 13, 2009 at 7:49 AM, Chouser <chou...@gmail.com> wrote: > > On Fri, Mar 13, 2009 at 2:18 AM, Sergio <bigmonac...@gmail.com> wrote: >> >> There are a couple of obvious ones, but also some others that I >> haven't seen documented (like, map is much faster on lists than on >> vectors since rest is O(1) for lists). > > You're right that 'rest' is O(1) for lists, but it's O(1) for vectors as well. > > Your blog post include this table: > >> rest - O(1) for lists. O(n) for vectors. >> count - O(1) for lists and vectors
I think that count is O(n) for lists, no? >> nth - O(n) for lists. O(1) for vectors. >> cons - O(1) for lists, O(n) for vectors > > This has a couple errors. Both 'rest' and 'cons' are O(1) on vectors. > I'm not sure what in the source code led you to believe otherwise. > Both 'rest' and 'cons' create a seq from the vector, but this is an > O(1) operation. You can also run some timing experiments and see that > 'map' is at least as fast on vectors as on lists. > > (defn timemap [c] > (time > (dotimes [i 100] > (last (map identity c))))) > > (timemap (into [] (range 10000))) ==> "Elapsed time: 158.464048 msecs" > (timemap (into [] (range 100000))) ==> "Elapsed time: 1690.745615 msecs" > > Note that multiplying the length of the vector by 10 increased the > time by roughly 10 -- this suggests an O(n) operation, as we would > expect. > > (timemap (into () (range 10000))) ==> "Elapsed time: 185.460957 msecs" > (timemap (into () (range 100000))) ==> "Elapsed time: 1821.346964 msecs" > > Again we see evidence of 'map' being O(n), but when walking across a > list it appears to run slightly *slower* than across a vector, though > probably not by enough to be significant. > > > We can even time 'rest' itself: > > (defn timerest [c] > (time > (dotimes [i 1000000] > (rest c)))) > > (timerest (into [] (range 10000))) ==> "Elapsed time: 125.826519 msecs" > > If 'rest' were O(n) on vectors, we should be able to multiply the > length of the vector by 100 and see the time go up by roughly 100x: > > (timerest (into [] (range 1000000))) ==> "Elapsed time: 147.096976 msecs" > > The amount of time it takes to build the vector goes up significantly, > but the timed part, calling 'rest' a million times, doesn't take > anywhere near 100 times longer. > > --Chouser > > > > -- Venlig hilsen / Kind regards, Christian Vest Hansen. --~--~---------~--~----~------------~-------~--~----~ 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 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 -~----------~----~----~----~------~----~------~--~---
