Skip to content

namenu/data.deque

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

29 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

data.deque

Clojars Project

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.

Reference

About

Persistent Deque for Clojure(Script)

Topics

Resources

License

Stars

Watchers

Forks

Packages

No packages published