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

问题描述

我最近听过 Rich Hickey的采访软件工程无线电在采访中，Rich提到Clojure的收藏是以树木的形式实现的。我希望以另一种语言实现持久化的数据结构，并且想了解如何实现Set和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.

我也想知道节点可能具有的最大分支数。 Rich在采访中提到树木很浅，所以推测分支因子大于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

还有一些论文：

• 快速功能列表，哈希列表，表达式和可变长度数组


• 理想的哈希树


• 来自菲尔的更多信息

• 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屋！