Skip to content


Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tag: data.finger-tr…
Fetching contributors…

Cannot retrieve contributors at this time

101 lines (74 sloc) 2.958 kb
(time (count (reduce #(-> % (conjr %2) rest) (reduce consl (EmptyTree. nil) (range 1e4)) (range 1e6))))
letfn: "Elapsed time: 5043.853495 msecs"
digit macro: "Elapsed time: 3411.159957 msecs"
32% better
(time (let [n 1e4, t (to-tree {:size [(constantly 1) + 0]} (range n))] (dotimes [i n] (split-tree t #(< i (:size %))))))
"Elapsed time: 4408.469664 msecs"
loopless split digit: "Elapsed time: 4102.303245 msecs"
later got this for the same code: "Elapsed time: 3976.687969 msecs"
(time (let [t (to-tree nil (range 1e5))] (dotimes [_ 3e4] (ft-concat t t))))
"Elapsed time: 2402.644912 msecs"
nodes without apply: "Elapsed time: 2004.185324 msecs"
Using digit for node and always using a delayed measure cache:
queue: 3302.095682 (3% better)
split: 3096.94213 (22% better)
concat: 1680.462405 (16% better)'s also less code.
Removing the assert in 'deep' helps a bit too:
queue: 2934.046655
split: 3086.496488
concat: 1631.712977
Delay deep's measure:
queue: 2156.064809
split: 2471.035156
concat: 1510.606604
Slightly better 'split' only calling measure/reduce on middle tree when needed.
split: 2347.711168
queue: 2151.073871
split: 2351.481345
concat: 1699.367853
queue: 6234.505356
split: 3824.236948
concat: 1958.039438
protocol call site caching:
queue: 5380.091688
split: 3552.108167
concat: 1679.4733
protocol methods inside deftype:
queue: 6115.087433
split: 2851.264586
concat: 1532.471135
Note PersistentQueue does queue test in 363.281297 msecs
(defn t [] (count (reduce #(-> % (conj %2) pop) (reduce conj clojure.lang.PersistentQueue/EMPTY (range 1e4)) (range 1e6))))
with Clojure 1.2.0:
queue: 2645.928817
split: 2374.810216
concat: 1530.395627
with record-based meters (+ some performance tweaks):
queue: (time (count (reduce #(-> % (conjr %2) rest) (reduce consl (EmptyTree. nil) (range 1e4)) (range 1e6))))
split: (time (let [n 1e4, t (to-tree len-meter (range n))] (dotimes [i n] (split-tree t #(< i %)))))
concat: (time (let [t (to-tree nil (range 1e5))] (dotimes [_ 3e4] (ft-concat t t))))
queue: 3334.090979
split: 313.484652
concat: 1763.906721
Len-Meter instead of Integer:
queue: (time (count (reduce #(-> % (conjr %2) rest) (reduce consl (EmptyTree. nil) (range 1e4)) (range 1e6))))
split: (time (let [n 1e4, t (to-tree len-meter (range n))] (dotimes [i n] (split-tree t #(< i (:len %))))))
concat: (time (let [t (to-tree nil (range 1e5))] (dotimes [_ 3e4] (ft-concat t t))))
split: 331.637379
Test for nil op:
queue: 2346.357413
split: 352.238152
concat 1518.418893
split with len-string-meter: 40264.907112
--- sorted set slowness:
(do (def rands (let [r (java.util.Random. 42)] (take 10000 (repeatedly #(.nextInt r))))) nil)
(defn s1 [] (first (reduce (fn [t i] (insert-where t #(when-let [r (:right %)] (< i r)) i)) (finger-tree right-meter) rands)))
; 914.896926
(defn s2 [] (first (reduce conj (sorted-set) rands)))
; 55.687814
Jump to Line
Something went wrong with that request. Please try again.