Relaxed Radix Balanced Trees (RRB-Trees) Vector.

Based on Phil Bagwell’s RRB-Trees, this collection type stores items in a relaxed radix balanced trees, which enables performant splitting and catenation. These features can be used to insert/remove items in the middle of a vector.

RRB-Tree vectors have support for transients, folding, efficient reversion, sectioning, slicing and catenation. Besides RRB-Tree vector, Dunaj offers following persistent vector types:

  • BVT vectors for efficient representation of medium to large vectors

  • tuples for efficient representation of small vectors

  • primitive vectors for efficient storage of host primitive data types.

This namespace does not provide any public vars, but instead extends BVT vector to automatically convert to RRB-Tree based vector on slicing. There is no need to require this namespace directly.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(def v (vec (range 10000)))
;;=> #'foo.bar/v

(defn insert-hamt
  [v i x]
  (into (vec (section v 0 i)) (cons x (section v i))))
;;=> #'foo.bar/insert-hamt

(defn insert-rrbt
  [v i x]
  (cat (conj (slice v 0 i) x) (slice v i)))
;;=> #'foo.bar/insert-rrbt

(time (dotimes [x 10000] (insert-hamt v x :foo)))
;; Elapsed time: 8385.197748 msecs
;;=> nil

(time (dotimes [x 10000] (insert-rrbt v x :foo)))
;; Elapsed time: 411.800573 msecs
;;=> nil