Here's a round of benchmarks for the new functions
(avl/{nearest,subrange,split-at,split-key}), with a lookup benchmark
included as a point of reference.
Cheers,
Michał
(let [m (apply avl/sorted-map
(interleave (range 100000) (range 100000)))]
(c/bench (get m 99999))
(c/bench (avl/nearest m < 100000))
(c/bench (avl/subrange m >= 10000 < 75000))
(c/bench (avl/split-at 30000 m))
(c/bench (avl/split-key 30000 m)))
WARNING: Final GC required 4.244287716089524 % of runtime
Evaluation count : 213693000 in 60 samples of 3561550 calls.
Execution time mean : 278.027014 ns
Execution time std-deviation : 4.284738 ns
Execution time lower quantile : 273.830485 ns ( 2.5%)
Execution time upper quantile : 287.103701 ns (97.5%)
Overhead used : 2.289159 ns
Found 10 outliers in 60 samples (16.6667 %)
low-severe 9 (15.0000 %)
low-mild 1 (1.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
Evaluation count : 168881400 in 60 samples of 2814690 calls.
Execution time mean : 352.393290 ns
Execution time std-deviation : 5.226142 ns
Execution time lower quantile : 346.698762 ns ( 2.5%)
Execution time upper quantile : 364.246208 ns (97.5%)
Overhead used : 2.289159 ns
Found 4 outliers in 60 samples (6.6667 %)
low-severe 4 (6.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
Evaluation count : 1333200 in 60 samples of 22220 calls.
Execution time mean : 45.605490 µs
Execution time std-deviation : 682.937868 ns
Execution time lower quantile : 44.839275 µs ( 2.5%)
Execution time upper quantile : 47.176367 µs (97.5%)
Overhead used : 2.289159 ns
Found 3 outliers in 60 samples (5.0000 %)
low-severe 3 (5.0000 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
Evaluation count : 2338740 in 60 samples of 38979 calls.
Execution time mean : 25.715076 µs
Execution time std-deviation : 366.924494 ns
Execution time lower quantile : 25.249912 µs ( 2.5%)
Execution time upper quantile : 26.592419 µs (97.5%)
Overhead used : 2.289159 ns
Found 2 outliers in 60 samples (3.3333 %)
low-severe 2 (3.3333 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
Evaluation count : 2596800 in 60 samples of 43280 calls.
Execution time mean : 23.343989 µs
Execution time std-deviation : 308.669720 ns
Execution time lower quantile : 22.908707 µs ( 2.5%)
Execution time upper quantile : 24.143221 µs (97.5%)
Overhead used : 2.289159 ns
Found 4 outliers in 60 samples (6.6667 %)
low-severe 4 (6.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
On 24 April 2014 08:51, Michał Marczyk <michal.marc...@gmail.com> wrote:
> Cheers Alex!
>
> See below for the results of yesterday's run of my benchmark suite for
> the basic operations. (I'll post some benchmark results for the new
> functions in a separate message sometime soon.)
>
> In general, it's fair to expect (persistent) assoc/dissoc to be slower
> with data.avl maps, since AVL trees do more work to rebalance
> themselves than red-black trees. (That's on average, of course.)
>
> The upside is that lookups in AVL trees are faster on average,
> sometimes quite dramatically, due to the trees being shallower. It's
> worth pointing out that this really is "on average" -- individual
> timings depend on the path through the tree the lookup operation needs
> to traverse, and for nodes at exactly the same position in the tree
> the built-ins are slightly faster (23.9 ns vs. 25.5 ns for a lookup
> succeeding at the root node, see the (get % 131071) benchmark case
> below; as I recall, 0 happens to occupy the same position in both
> benchmark maps as well) -- but if we hit a deeper part of a red-black
> tree, data.avl is likely to win by a large margin, as in the case of
> the 311 ns (data.avl) vs. 588 ns (built-in) result for looking up
> 299999 in the two benchmark maps.
>
> For longer chains of "updates" -- including construction of instances
> with more than a handful of elements -- data.avl wins thanks to its
> support for transients; in particular, inserting 300000 entries in
> ascending order of keys took 197 ns with data.avl's sorted-map during
> my benchmark run yesterday vs. 317 ns with the built-in.
>
>
> ;;; the setup:
>
> (def ks (range 300000))
> (def ksks (interleave ks ks))
>
> (def rb (apply sorted-map ksks))
> (def avl (apply avl/sorted-map ksks))
>
> ;;; the actual benchmark run
>
> Clojure 1.5.1
> user=> (all-benchmarks)
> (lookup-benchmarks)
> ===================
> (c/bench (get avl 0))
> WARNING: Final GC required 17.95425214438086 % of runtime
> WARNING: Final GC required 1.44548564181991 % of runtime
> Evaluation count : 233348580 in 60 samples of 3889143 calls.
> Execution time mean : 257.269857 ns
> Execution time std-deviation : 2.083817 ns
> Execution time lower quantile : 254.044412 ns ( 2.5%)
> Execution time upper quantile : 261.944879 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 1 outliers in 60 samples (1.6667 %)
> low-severe 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (get rb 0))
> WARNING: Final GC required 1.443796805141993 % of runtime
> Evaluation count : 245219880 in 60 samples of 4086998 calls.
> Execution time mean : 244.222199 ns
> Execution time std-deviation : 1.613109 ns
> Execution time lower quantile : 240.981893 ns ( 2.5%)
> Execution time upper quantile : 247.680884 ns (97.5%)
> Overhead used : 2.115402 ns
> (c/bench (get avl 131071))
> WARNING: Final GC required 1.538687432575083 % of runtime
> Evaluation count : 2189108520 in 60 samples of 36485142 calls.
> Execution time mean : 25.463933 ns
> Execution time std-deviation : 0.159206 ns
> Execution time lower quantile : 25.242537 ns ( 2.5%)
> Execution time upper quantile : 25.846594 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 2 outliers in 60 samples (3.3333 %)
> low-severe 2 (3.3333 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (get rb 131071))
> WARNING: Final GC required 1.544907815808739 % of runtime
> Evaluation count : 2306183280 in 60 samples of 38436388 calls.
> Execution time mean : 23.873777 ns
> Execution time std-deviation : 0.243375 ns
> Execution time lower quantile : 23.590693 ns ( 2.5%)
> Execution time upper quantile : 24.503250 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 3 outliers in 60 samples (5.0000 %)
> low-severe 1 (1.6667 %)
> low-mild 2 (3.3333 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (get avl 299999))
> WARNING: Final GC required 1.4317314000518289 % of runtime
> Evaluation count : 192818880 in 60 samples of 3213648 calls.
> Execution time mean : 311.396507 ns
> Execution time std-deviation : 2.029572 ns
> Execution time lower quantile : 308.219265 ns ( 2.5%)
> Execution time upper quantile : 315.544485 ns (97.5%)
> Overhead used : 2.115402 ns
> (c/bench (get rb 299999))
> WARNING: Final GC required 1.424486278904469 % of runtime
> Evaluation count : 102060180 in 60 samples of 1701003 calls.
> Execution time mean : 588.846851 ns
> Execution time std-deviation : 3.124839 ns
> Execution time lower quantile : 584.394022 ns ( 2.5%)
> Execution time upper quantile : 594.415623 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 1 outliers in 60 samples (1.6667 %)
> low-severe 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (construction-benchmarks)
> =========================
> (c/bench (apply avl/sorted-map ksks))
> WARNING: Final GC required 5.3006864743254365 % of runtime
> Evaluation count : 360 in 60 samples of 6 calls.
> Execution time mean : 197.715700 ms
> Execution time std-deviation : 1.410989 ms
> Execution time lower quantile : 195.528307 ms ( 2.5%)
> Execution time upper quantile : 200.733827 ms (97.5%)
> Overhead used : 2.115402 ns
>
> Found 1 outliers in 60 samples (1.6667 %)
> low-severe 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (apply sorted-map ksks))
> WARNING: Final GC required 4.7280630882454275 % of runtime
> Evaluation count : 240 in 60 samples of 4 calls.
> Execution time mean : 317.073457 ms
> Execution time std-deviation : 1.799728 ms
> Execution time lower quantile : 314.404224 ms ( 2.5%)
> Execution time upper quantile : 320.886432 ms (97.5%)
> Overhead used : 2.115402 ns
> (assoc-benchmarks)
> ==================
> (c/bench (assoc avl -1 -1))
> WARNING: Final GC required 1.4272766765260692 % of runtime
> Evaluation count : 94731120 in 60 samples of 1578852 calls.
> Execution time mean : 640.949880 ns
> Execution time std-deviation : 5.268487 ns
> Execution time lower quantile : 632.929494 ns ( 2.5%)
> Execution time upper quantile : 651.026693 ns (97.5%)
> Overhead used : 2.115402 ns
> (c/bench (assoc rb -1 -1))
> WARNING: Final GC required 1.4813094150003698 % of runtime
> Evaluation count : 101334900 in 60 samples of 1688915 calls.
> Execution time mean : 586.478825 ns
> Execution time std-deviation : 6.445327 ns
> Execution time lower quantile : 577.251444 ns ( 2.5%)
> Execution time upper quantile : 600.983215 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 2 outliers in 60 samples (3.3333 %)
> low-severe 2 (3.3333 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (assoc avl 131071.5 131071.5))
> WARNING: Final GC required 1.44705071828203 % of runtime
> Evaluation count : 89874900 in 60 samples of 1497915 calls.
> Execution time mean : 674.654642 ns
> Execution time std-deviation : 7.380872 ns
> Execution time lower quantile : 662.647528 ns ( 2.5%)
> Execution time upper quantile : 690.152387 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 1 outliers in 60 samples (1.6667 %)
> low-severe 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (assoc rb 131071.5 131071.5))
> WARNING: Final GC required 1.476998263803252 % of runtime
> Evaluation count : 104773620 in 60 samples of 1746227 calls.
> Execution time mean : 581.851687 ns
> Execution time std-deviation : 5.236315 ns
> Execution time lower quantile : 573.394307 ns ( 2.5%)
> Execution time upper quantile : 591.444744 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 1 outliers in 60 samples (1.6667 %)
> low-severe 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (assoc avl 300000 300000))
> WARNING: Final GC required 1.4573754017132279 % of runtime
> Evaluation count : 52686120 in 60 samples of 878102 calls.
> Execution time mean : 1.143503 µs
> Execution time std-deviation : 8.905816 ns
> Execution time lower quantile : 1.128491 µs ( 2.5%)
> Execution time upper quantile : 1.161180 µs (97.5%)
> Overhead used : 2.115402 ns
>
> Found 1 outliers in 60 samples (1.6667 %)
> low-severe 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (assoc rb 300000 300000))
> WARNING: Final GC required 1.4453736865925522 % of runtime
> Evaluation count : 61066200 in 60 samples of 1017770 calls.
> Execution time mean : 986.964073 ns
> Execution time std-deviation : 9.099675 ns
> Execution time lower quantile : 971.014487 ns ( 2.5%)
> Execution time upper quantile : 1.005402 µs (97.5%)
> Overhead used : 2.115402 ns
>
> Found 1 outliers in 60 samples (1.6667 %)
> low-severe 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (dissoc-benchmarks)
> ===================
> (c/bench (dissoc avl 0))
> WARNING: Final GC required 1.409625923637254 % of runtime
> Evaluation count : 95106480 in 60 samples of 1585108 calls.
> Execution time mean : 632.360192 ns
> Execution time std-deviation : 6.758100 ns
> Execution time lower quantile : 622.348742 ns ( 2.5%)
> Execution time upper quantile : 644.801029 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 1 outliers in 60 samples (1.6667 %)
> low-severe 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (dissoc rb 0))
> WARNING: Final GC required 1.4395319870486911 % of runtime
> Evaluation count : 98152980 in 60 samples of 1635883 calls.
> Execution time mean : 616.735094 ns
> Execution time std-deviation : 7.850262 ns
> Execution time lower quantile : 603.999108 ns ( 2.5%)
> Execution time upper quantile : 631.343617 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 1 outliers in 60 samples (1.6667 %)
> low-severe 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (dissoc avl 131071))
> WARNING: Final GC required 1.521591424378216 % of runtime
> Evaluation count : 221033940 in 60 samples of 3683899 calls.
> Execution time mean : 274.098530 ns
> Execution time std-deviation : 2.452287 ns
> Execution time lower quantile : 270.107011 ns ( 2.5%)
> Execution time upper quantile : 279.445027 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 6 outliers in 60 samples (10.0000 %)
> low-severe 6 (10.0000 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (dissoc rb 131071))
> WARNING: Final GC required 1.518838691811953 % of runtime
> Evaluation count : 110069460 in 60 samples of 1834491 calls.
> Execution time mean : 544.040051 ns
> Execution time std-deviation : 6.594133 ns
> Execution time lower quantile : 533.460485 ns ( 2.5%)
> Execution time upper quantile : 559.612526 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 2 outliers in 60 samples (3.3333 %)
> low-severe 2 (3.3333 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (dissoc avl 299999))
> WARNING: Final GC required 1.4221011007954931 % of runtime
> Evaluation count : 55003980 in 60 samples of 916733 calls.
> Execution time mean : 1.106014 µs
> Execution time std-deviation : 7.937471 ns
> Execution time lower quantile : 1.090420 µs ( 2.5%)
> Execution time upper quantile : 1.119023 µs (97.5%)
> Overhead used : 2.115402 ns
> (c/bench (dissoc rb 299999))
> WARNING: Final GC required 1.4984644559577371 % of runtime
> Evaluation count : 69322080 in 60 samples of 1155368 calls.
> Execution time mean : 866.398607 ns
> Execution time std-deviation : 9.504058 ns
> Execution time lower quantile : 851.988220 ns ( 2.5%)
> Execution time upper quantile : 887.694665 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 1 outliers in 60 samples (1.6667 %)
> low-severe 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (reduce-kv-benchmarks)
> ======================
> (c/bench (reduce-kv + 0 avl))
> WARNING: Final GC required 1.4943999357205922 % of runtime
> Evaluation count : 1680 in 60 samples of 28 calls.
> Execution time mean : 37.019830 ms
> Execution time std-deviation : 211.307503 µs
> Execution time lower quantile : 36.602312 ms ( 2.5%)
> Execution time upper quantile : 37.377517 ms (97.5%)
> Overhead used : 2.115402 ns
> (c/bench (reduce-kv + 0 rb))
> WARNING: Final GC required 1.470636145118843 % of runtime
> Evaluation count : 1500 in 60 samples of 25 calls.
> Execution time mean : 41.019274 ms
> Execution time std-deviation : 285.334885 µs
> Execution time lower quantile : 40.541044 ms ( 2.5%)
> Execution time upper quantile : 41.504517 ms (97.5%)
> Overhead used : 2.115402 ns
> (select-benchmarks)
> ===================
> (c/bench (nth avl 0))
> WARNING: Final GC required 1.494616669407989 % of runtime
> Evaluation count : 222102300 in 60 samples of 3701705 calls.
> Execution time mean : 269.443606 ns
> Execution time std-deviation : 2.158203 ns
> Execution time lower quantile : 265.797360 ns ( 2.5%)
> Execution time upper quantile : 273.406291 ns (97.5%)
> Overhead used : 2.115402 ns
> (c/bench (nth (seq rb) 0))
> WARNING: Final GC required 1.420496053869465 % of runtime
> Evaluation count : 272733660 in 60 samples of 4545561 calls.
> Execution time mean : 218.593345 ns
> Execution time std-deviation : 1.965696 ns
> Execution time lower quantile : 215.009791 ns ( 2.5%)
> Execution time upper quantile : 221.595814 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 1 outliers in 60 samples (1.6667 %)
> low-severe 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (nth avl 131071))
> WARNING: Final GC required 1.4913582150274651 % of runtime
> Evaluation count : 2340271560 in 60 samples of 39004526 calls.
> Execution time mean : 23.958321 ns
> Execution time std-deviation : 0.273586 ns
> Execution time lower quantile : 23.512070 ns ( 2.5%)
> Execution time upper quantile : 24.470681 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 1 outliers in 60 samples (1.6667 %)
> low-severe 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (nth (seq rb) 131071))
> WARNING: Final GC required 1.442980458629981 % of runtime
> Evaluation count : 15240 in 60 samples of 254 calls.
> Execution time mean : 3.971846 ms
> Execution time std-deviation : 37.538641 µs
> Execution time lower quantile : 3.908583 ms ( 2.5%)
> Execution time upper quantile : 4.046135 ms (97.5%)
> Overhead used : 2.115402 ns
>
> Found 1 outliers in 60 samples (1.6667 %)
> low-severe 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (nth avl 299999))
> WARNING: Final GC required 1.396166903433299 % of runtime
> Evaluation count : 62932200 in 60 samples of 1048870 calls.
> Execution time mean : 966.061999 ns
> Execution time std-deviation : 12.227245 ns
> Execution time lower quantile : 950.801928 ns ( 2.5%)
> Execution time upper quantile : 994.606117 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 4 outliers in 60 samples (6.6667 %)
> low-severe 3 (5.0000 %)
> low-mild 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (nth (seq rb) 299999))
> WARNING: Final GC required 1.411884727250311 % of runtime
> Evaluation count : 3480 in 60 samples of 58 calls.
> Execution time mean : 17.404103 ms
> Execution time std-deviation : 125.910185 µs
> Execution time lower quantile : 17.180238 ms ( 2.5%)
> Execution time upper quantile : 17.698525 ms (97.5%)
> Overhead used : 2.115402 ns
>
> Found 2 outliers in 60 samples (3.3333 %)
> low-severe 2 (3.3333 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (rank-of-benchmarks)
> ====================
> (c/bench (avl/rank-of avl 0))
> WARNING: Final GC required 1.410760546097934 % of runtime
> Evaluation count : 228328740 in 60 samples of 3805479 calls.
> Execution time mean : 262.229200 ns
> Execution time std-deviation : 1.545106 ns
> Execution time lower quantile : 260.026098 ns ( 2.5%)
> Execution time upper quantile : 265.501717 ns (97.5%)
> Overhead used : 2.115402 ns
> (c/bench (rb-rank-of rb 0))
> WARNING: Final GC required 1.528903400498107 % of runtime
> Evaluation count : 122421060 in 60 samples of 2040351 calls.
> Execution time mean : 489.908995 ns
> Execution time std-deviation : 4.341988 ns
> Execution time lower quantile : 483.130264 ns ( 2.5%)
> Execution time upper quantile : 497.383919 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 1 outliers in 60 samples (1.6667 %)
> low-severe 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (avl/rank-of avl 131071))
> WARNING: Final GC required 1.601437516988401 % of runtime
> Evaluation count : 1923909240 in 60 samples of 32065154 calls.
> Execution time mean : 29.024185 ns
> Execution time std-deviation : 0.271967 ns
> Execution time lower quantile : 28.621628 ns ( 2.5%)
> Execution time upper quantile : 29.530897 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 3 outliers in 60 samples (5.0000 %)
> low-severe 2 (3.3333 %)
> low-mild 1 (1.6667 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (rb-rank-of rb 131071))
> WARNING: Final GC required 1.5253557008726901 % of runtime
> Evaluation count : 2700 in 60 samples of 45 calls.
> Execution time mean : 22.259014 ms
> Execution time std-deviation : 176.571734 µs
> Execution time lower quantile : 21.949530 ms ( 2.5%)
> Execution time upper quantile : 22.639924 ms (97.5%)
> Overhead used : 2.115402 ns
> (c/bench (avl/rank-of avl 299999))
> WARNING: Final GC required 1.46116006270368 % of runtime
> Evaluation count : 139283400 in 60 samples of 2321390 calls.
> Execution time mean : 429.526612 ns
> Execution time std-deviation : 3.425081 ns
> Execution time lower quantile : 425.422751 ns ( 2.5%)
> Execution time upper quantile : 437.939328 ns (97.5%)
> Overhead used : 2.115402 ns
>
> Found 2 outliers in 60 samples (3.3333 %)
> low-severe 2 (3.3333 %)
> Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
> (c/bench (rb-rank-of rb 299999))
> WARNING: Final GC required 1.5002581976759541 % of runtime
> Evaluation count : 1200 in 60 samples of 20 calls.
> Execution time mean : 50.728340 ms
> Execution time std-deviation : 353.191435 µs
> Execution time lower quantile : 50.130720 ms ( 2.5%)
> Execution time upper quantile : 51.368250 ms (97.5%)
> Overhead used : 2.115402 ns
> nil
>
>
> On 23 April 2014 18:37, Alex Miller <a...@puredanger.com> wrote:
>> 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.
--
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.
