Great work as always! Are there any places where data.avl performs worse than the built-in sorted maps and sets?
On Wednesday, April 23, 2014 7:59:59 AM UTC-5, Michał Marczyk wrote: > > Hi, > > I am pleased to announce the 0.0.12 release of data.avl, a Clojure > Contrib library providing drop-in replacements for Clojure(Script)'s > built-in sorted maps and sets with additional functionality: > > 1. real (non-view) logarithmic-time slicing and splits; > > 2. logarithmic-time nearest neighbour lookups and rank queries; > > 3. support for transients. > > This release is identical to 0.0.12-alpha1 except for the fact that > the Vars clojure.data.avl/empty-{set,map}-hash{eq,code} are now marked > private, as they should be. > > Changes since 0.0.11 include an important fix to the rebalancing > algorithm, so I would strongly advise all users of 0.0.11 to upgrade > as soon as possible. There are also several new additions to the API, > on which more below. > > [org.clojure/data.avl "0.0.12"] > > <dependency> > <groupId>org.clojure</groupId> > <artifactId>data.avl</artifactId> > <version>0.0.12</version> > </dependency> > > org.clojure:data.avl:0.0.12 > > The following transcript of a REPL session includes calls to each of > the new public functions: > > (require '[clojure.data.avl :as avl]) > > (avl/nearest (avl/sorted-set 0 1 2) < 2) > ;= 1 > > (avl/subrange (avl/sorted-set 0 1 2 3 4 5) >= 1 < 4) > ;= #{1 2 3} > > (avl/split-at 2 (avl/sorted-set 0 1 2 3 4 5)) > ;= [#{0 1} #{2 3 4 5}] > > (avl/split-key 3 (avl/sorted-set 0 2 4 6)) > ;= [#{0 2} nil #{4 6}] > > All of these functions operate in time logarithmic in the size of > their inputs. avl/subrange returns a data.avl collection of the same > type as its input and completely independent from it -- that is, it > shares structure with the input where possible, but does not hold on > to any parts of the tree containing keys that should not be present in > the output. avl/split-at and avl/split-key return similarly > independent data.avl collections; the middle element of the vector > returned by split-key is the element at the split key if present in > the input, nil otherwise. > > "split" is the name usually applied in the literature to the operation > that splits a tree into a "left" tree, a middle element and a "right" > tree. "subrange" could also be called "slice". The split-* functions > take their collection argument last to be consistent with > clojure.core's split-at and split-with. Arguments accepted by subrange > are analogous to those taken by subseq/rsubseq. > > Many thanks to the two new contributors to this release (listed here > in chronological order of ticket creation): Pepijn de Vos, who > prompted me to develop the above-mentioned new features by creating > the ticket asking for what is now avl/nearest and mentioning > java.util.Navigable{Map,Set}, and who provided new tests for > avl/nearest; and Andy Fingerhut, who kept on top of the hashing > changes and provided the initial implementation of new-style hasheq > for data.avl with further tests. > > Cheers, > Michał > -- 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/d/optout.