Hi Jules,
On Thursday, February 20, 2014 11:59:03 PM UTC+1, Jules wrote:
>
> Subvec provides a view on a subseq of a vector that behaves like a full
> vector. Supervec provides a similar view that makes two vectors behave like
> a single one
>
This data structure ("supervec") is usually known as a rope, and your
implementation degrades the *~O(1)* to worst case *O(k)* time for lookups,
assoc, conj and pop, where *k* is the amount of concatenations performed. A
good rope implementation can reduce that factor down to *O(log k)* through
balancing, but it will still break the performance guarantees a persistent
vector is supposed to have. If you try to use this in the reducers library,
the amount of concatenations fork/join performs might actually show notable
performance degradation for those operations. Further, passing it around to
code which might perform more concatenations will lead to even worse
performance, which may be hard to debug for people not knowing Clojure
internals.
However, it is a very nice solution if you know there will be limited
concatenations, that the concatenations result in a balanced tree, and you
don't pass this vector around to other people. :)
For a small discussion on this vs. RRB-trees, see Section 1.1 in
http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf.
Hopefully I'm not destroying your fun playing around with these things—that
is not the intent at all. I'm just saying that these things are (sadly?)
harder than it first looks like.
-- JN
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
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
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
