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套件背后的数据结构是什么？

回答

相关问题