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 [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/d/optout.
