Clojure 的集合背后的数据结构是什么? [英] What is the data structure behind Clojure's sets?

问题描述

我最近听了 Rich Hickey 的采访在软件工程电台.在采访中，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. 创建集合 {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.

我还想知道一个节点可能拥有的最大分支数.里奇在采访中提到树很浅，所以想必分支因子大于2.

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.

Phil 在 Clojure/Conj 上的演讲:http://www.youtube.com/watch?v=K2NYwP90bNs

There is this talk by Phil at Clojure/Conj: http://www.youtube.com/watch?v=K2NYwP90bNs

还有一些论文:

• 快速函数列表、哈希列表、双端队列和可变长度数组
• 理想哈希树
• 更多来自 Phil 的内容

您还可以阅读纯函数数据结构 克里斯冈崎.这篇博文谈到了这本书: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屋！