On Oct 3, 10:59 am, Cesare <[EMAIL PROTECTED]> wrote:
> On Oct 3, 4:42 pm, Rich Hickey <[EMAIL PROTECTED]> wrote:
>
> > On Oct 3, 10:12 am, Cesare <[EMAIL PROTECTED]> wrote:
> > Subvectors can be created in constant time because they copy nothing
> > and share structure with the original. So, they are effectively views
> > on the original vector, and share its access times. No magic here,
> > sorry :)
>
> mmm... so access by index for a sub-vector causes the same number of
> hops than the super-vector, right? This means that it's O(log32N) if
> the vector is not created using subvect, otherwise N is the length of
> the super-vector, not the vector itself.
> Am I right?
>
Yes. If it is important to get access bounded by the subvector's N you
can just call vec on it, at a one-time O(subvecN) cost.
It is important to note that for vectors that are created by vec (and
literals) that have never been updated, creating the tree
representation is done lazily on update and used by the changed
versions only, so access to this root value is in fact always O(1),
for that vector and any subvectors.
(class [1 2 3 4 5])
-> clojure.lang.LazilyPersistentVector
(class (vec (range 1000)))
-> clojure.lang.LazilyPersistentVector
i.e. LazilyPersistentVectors are O(1)
Rich
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
