Clojure套件背後的數據結構是什麼？

我最近聽了Rich Hickey's interview on Software Engineering Radio。在採訪中，Rich提到Clojure的收藏被實現爲樹木。我希望以另一種語言實現持久化數據結構，並希望瞭解集合和Clojure的其他持久數據結構如何實現。Clojure套件背後的數據結構是什麼？

在以下情況下，樹在每個點上的外觀如何？

創建一套{1 2 3}
創建的{1 2 3}工會和{4}
創建的{1 2 3 4}，我想明白是怎麼區別{1}

生成三組（{1 2 3},{1 2 3 4}和{2 3 4}）共享結構，以及如何處理「刪除」。

我也想知道一個節點可能有的最大分支數量。 Rich在採訪中提到樹木很淺，所以推測分支因子大於2。

來源

2013-04-29 davidchambers

分支因子是32. – 2013-04-29 04:32:46

迂腐筆記：我只是在http://www.youtube.com/watch?v=sp2Zv7KFQQ0聽取Rich Hickey _Clojure數據結構2_。不確定在何時何地記錄。集合具有不同的存儲實現。（默認？）向量是淺層樹。其他集合可能有其他實現。 – 2013-04-29 19:56:13

他們這樣做。具體來說：哈希集，哈希映射和向量每個節點有32個子節點;排序集和排序圖是紅黑樹，每個節點有2個孩子。 – Chouser 2013-05-04 14:39:10

您可能需要閱讀Phil Bagwell的工作。他對數據結構的研究是Clojure，Haskell和Scala持久數據結構的基礎。

有這樣的話題由菲爾的Clojure /連詞：http://www.youtube.com/watch?v=K2NYwP90bNs

也有一些論文：

你也可以閱讀由Chris Okasaki提供的。這個博客文章談到這本書：http://okasaki.blogspot.com.br/2008/02/ten-years-of-purely-functional-data.html

來源

2013-05-06 19:45:50

這裏有一個出發點：https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashSet.java

你可以看到它在PersistentHashMap方面來實現。

來源

2013-04-29 04:10:36 gtrak

你真的應該讀Clojure Programming，它包含了很詳細的內容，包括圖片。簡而言之，集合是深度搜索樹木的第一步。我們可以證明你的例子是這樣的：

(def x #{1 2 3}) 

x 
| 
| \ 
|\ 3 
1 \ 
    2 

(def y (conj x 4)) 

x y 
|/\ 
| \ 4 
|\ 3 
1 \ 
    2 

(def z (difference y #{1})) 

x y 
|/\ 
| \ 4 
|\ 3 
1/\ 
z- 2

注意，這些都只是指示性的，我不是說，這正是Clojure的內部使用的佈局。這是要點。

來源

2013-04-29 10:17:37 SCdF

我喜歡SCdF的圖紙和解釋，但是如果你想要更深入的話，你應該在Higher-Order上閱讀關於Clojure數據結構的優秀系列文章。它詳細解釋了Clojure的地圖是如何工作的，而Clojure的套裝只是地圖頂部的一個薄層：#{:a :b}被實現爲圍繞{:a :a, :b :b}環繞。

來源

2013-05-02 18:32:10 amalloy

Clojure套件背後的數據結構是什麼？

回答

相關問題