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
> 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
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
