Data.deque
Persistent Deque for Clojure(Script)
Install / Use
/learn @namenu/Data.dequeREADME
data.deque
data.deque is a persistent deque for Clojure(Script).
Deque(double-ended queue) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front or back.
The implementation of data.deque is based on a slightly modified version of Finger tree.
It gives O(1) access to both ends and amortized O(1) for immutable insertion/deletion.
Example
(require '[data.deque :as dq])
;; create an empty deque with `(deque)` or
(def dl (dq/deque 5 4 3 2 1))
(dq/peek-first dl)
;=> 1
(dq/peek-last dl)
;=> 5
(-> dl
(dq/add-first 0)
(dq/add-last 6)
seq)
;=> (0 1 2 3 4 5 6)
(-> dl
(dq/remove-first)
(dq/remove-last)
seq)
;=> (2 3 4)
Differences from core.data.finger-tree
- ClojureScript support
- Better performance
- No unnecessary features for deque
- Trees are not concatable / splittable
- No measuring interfaces
Benchmark
| implementation | small | medium | large | rate | | --------------------------- | -------: | -------: | -----: | ----: | | java.util.ArrayDeque (base) | 37.94ms | 271.44ms | 3.47s | x1 | | clojure.data.finger-tree | 196.50ms | 1.23s | 12.88s | x3.86 | | data.deque (JVM) | 158.50ms | 595.49ms | 6.13s | x1.89 | | data.deque (Browser) | 152ms | 807ms | 7.47s | x2.31 |
- Tested on 2.8 GHz Quad-Core Intel Core i7
Why Finger Tree?
Banker's Deque is also a purely functional data structure that guarantee amortized constant time but performs worse due to reverse operation. Real-Time Deque eliminates amortization by "Lazy Rebuilding" technique, but it also has some overhead due to its laziness. Finger Tree provides a balanced framework for building deque in terms of both time and space complexity.
