Sorry =( I am horribly mistaken
I should have taken my time before posting..
But still, I really thought cons on vectors was O(n) base on
PersistentVector.java, line 148 (The version I'm reading is not the
current SVN head, so I don't know if it is that line for you)
Here is the snippet:
if(tail.length < 32)
{
Object[] newTail = new Object[tail.length + 1];
System.arraycopy(tail, 0, newTail, 0, tail.length);
newTail[tail.length] = val;
return new PersistentVector(meta(), cnt + 1, shift, root,
newTail);
}
I thought it was O(n) because of the System.arraycopy. I'm guessing
that for length<32 that is considered "constant" and the rest of the
cons function does something else.
Here is the microbenchmark that made me think map was slower on
vectors:
(def ls (list (range 1000000)))
(def vc (vec (range 1000000)))
(time (dorun (map (fn [x]) ls)))
"Elapsed time: 3.184435 msecs"
(time (dorun (map (fn [x]) vc)))
"Elapsed time: 498.535303 msecs"
Maybe you can explain it to me (On my blog I posted that maybe it was
because map was converting the vector to a seq and that was O(n), but
you just told me that converting vector to seq is O(n).
On Mar 13, 12: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
> > 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
-~----------~----~----~----~------~----~------~--~---
