Clojure集合背后的数据结构是什么？ [英] What is the data structure behind Clojure's sets?
问题描述
我最近听过 Rich Hickey在Software Engineering Radio 。在访谈期间，Rich提到Clojure的集合被实现为树。我希望实现另一种语言的持久性数据结构，并且想了解如何实现集合和Clojure的其他持久性数据结构。
I recently listened to Rich Hickey's interview on Software Engineering Radio. During the interview Rich mentioned that Clojure's collections are implemented as trees. I'm hoping to implement persistent data structures in another language, and would like to understand how sets and Clojure's other persistent data structures are implemented.
树将是什么样子在下面的场景中的每一点？
What would the tree look like at each point in the following scenario?
-
创建集
{1 2 3}
创建 {1 2 3} 和 {4}
创建 {1 2 3 4} 和 {1}
了解如何生成三个集合（ {1 2 3} ， {1 2 3 4} 和 {2 3 4} ）共享结构，以及如何处理删除。
I'd like to understand how the three sets generated ({1 2 3}, {1 2 3 4}, and {2 3 4}) share structure, and how "deletions" are handled.
我也想知道节点可能具有的最大分支数。 Rich在采访中提到树木很浅，所以推测分支因子大于两个。
I'd also like to know the maximum number of branches that a node may have. Rich mentioned in the interview that the trees are shallow, so presumably the branching factor is greater than two.
推荐答案
阅读Phil Bagwell的工作。他对数据结构的研究是Clojure，Haskell和Scala持久数据结构的基础。
You probably need to read the work of Phil Bagwell. His research into data structures is the base of Clojure, Haskell and Scala persistent data structures.
在Clojure / Conj中Phil的演讲： http://www.youtube.com/watch?v=K2NYwP90bNs
There is this talk by Phil at Clojure/Conj: http://www.youtube.com/watch?v=K2NYwP90bNs
还有一些论文：
- Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays
- Ideal Hash Trees
- More from Phil here
您还可以阅读纯功能数据结构。本博客介绍了这本书： http：// okasaki。 blogspot.com.br/2008/02/ten-years-of-purely-functional-data.html
You can also read Purely Functional Data Structures by Chris Okasaki. This blog post talks about the book: http://okasaki.blogspot.com.br/2008/02/ten-years-of-purely-functional-data.html
这篇关于Clojure集合背后的数据结构是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
