Hi Daniel, First, about getting this into core: the idea behind core.rrb-vector is to provide extensions to the core Clojure vector API which could at any point in time be folded into the core library -- or simply dropped into any projects which need them with no need for them to pay attention to which vector types they are using. Hence the core.* name. That's as close to an answer as I can provide on this point. :-)
About RRB trees vs. finger trees: RRB trees are a variation on the idea behind Clojure's PersistentVector, whereby concatenation and slicing in logarithmic time become possible at the cost of a slight slowdown of operations on vectors resulting from the application these two additional operations. There is no slowdown in the base case of a vector which never participated in concatenation / slicing. (That's in principle; core.rrb-vector's vector is currently slower than c.l.PersistentVector and about on a par with gvec. Figuring out how to close the gap is one of the major goals for further development.) As we all know from experience, persistent vectors are *extremely* fast, and RRB trees only sacrifice a little of this speed, so there is every hope that they will be eminently usable in practice. Rather importantly, RRB trees can seamlessly interoperate with regular persistent vectors, and indeed core.rrb-vector allows you to pass in vectors of arbitrary type to its catvec and subvec functions. (Strictly speaking, element types of vectors passed into catvec must match, that is, you can't concatenate a vector of objects with a vector of longs; but you can certainly concatenate a regular vector of objects with a clojure.core/subvec-created "view vector" of objects and a previously created RRB vector. RRB tree variants of vec, vector and vector-of are available, but there should be no reason to use them; I'm only using them for tests and benchmarking.) Finger trees are a slightly different beast in that they are more like a toolkit for constructing ad hoc special-purpose persistent data structures. The data.finger-tree contrib [1] is designed to support such usage. One could indeed use it to construct a vector workalike (in fact I believe the provided counted-double-list is pretty much that) with pretty great big-O complexity on a number of operations. Unfortunately the real-world performance of finger trees is generally considered to be less satisfying than the complexity bounds -- which is why we use persistent vectors in the first place: the finger tree paper [2] was published in 2006, so the choice was certainly open in Clojure's early days. Daniel Spiewak's talk mentioned by Phil goes into some details and attributes the underwhelming performance mostly to poor memory locality; you can watch it at [3]. Finger trees may still be useful because of this toolkit-like feel to them; when specialized data structures are available, however, they will often be superior in performance. Cheers, Michał [1] https://github.com/clojure/data.finger-tree [2] http://www.soi.city.ac.uk/~ross/papers/FingerTree.html [3] http://www.youtube.com/watch?v=pNhBQJN44YQ On 1 June 2013 02:09, Daniel <doubleagen...@gmail.com> wrote: > Apologies for my lack of knowledge. My understanding was that a finger tree > implementation has been in development for some time and was to provide the > same benefits. Can you explain the differences between RRB trees and finger > trees? Any hope of getting this project into core? > > -- > -- > 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 > Note that posts from new members are moderated - please be patient with your > first post. > 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 > --- > 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 clojure+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > -- -- 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 Note that posts from new members are moderated - please be patient with your first post. 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 --- 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
