相信要分類的Clojure集合

Question

如果我從外部API獲取對象的排序列表，是否有辦法將它放入排序集中，而無需重新排序呢？喜歡的東西：

=> (sorted? (assume-sorted [1 2 3])) 
true 

Answer 1

Clojure的使用持續性紅/黑樹數據結構的有序集合&地圖。當插入的項目使樹太不平衡時，樹的根節點重新排列以保持自己「近似」平衡。

您的測量結果顯示，與只在隨機位置生長的樹相比，重新平衡僅在右側生長的樹（每增加一個新的樹會使樹進一步向右偏移），開銷會稍微增加一些（有些插入會隨機使樹更加平衡）。

參見：

• https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
• https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentTreeMap.java

---

更新

我只是想在我的電腦上，並獲得比你的測試非常不同的結果。這再次顯示了試圖優化過早地（特別是如果變化小於2倍）的愚蠢：

(def x (range 1000000)) 
(def y (doall (shuffle x))) 

parse.core=> (time (doall (set x) nil)) 
"Elapsed time: 279.259531 msecs" 
"Elapsed time: 291.31022 msecs" 
"Elapsed time: 414.752484 msecs" 

parse.core=> (time (doall (set y) nil)) 
"Elapsed time: 286.496324 msecs" 
"Elapsed time: 284.95049 msecs" 
"Elapsed time: 285.568222 msecs" 
"Elapsed time: 301.55659 msecs" 

parse.core=> (time (doall (into (sorted-set) x) nil)) 
"Elapsed time: 816.473169 msecs" 
"Elapsed time: 775.025901 msecs" 
"Elapsed time: 763.638447 msecs" 

parse.core=> (time (doall (into (sorted-set) y) nil)) 
"Elapsed time: 1307.969889 msecs" 
"Elapsed time: 1313.099123 msecs" 
"Elapsed time: 1285.665797 msecs" 
"Elapsed time: 1307.879676 msecs" 

的故事的寓意

1. 首先要正確
2. 如果是足夠快，進入下一個問題
3. 如果需要更快，請測量最大瓶頸的位置
4. 決定是否更便宜地使用更多h/w在$ 0.03/hr或花費人力時間在co de變化（這將增加複雜性&降低可維護性等）。