不可变的数据结构性能

Question

我不知道作为一个集合的东西如何是不可变的并且仍然具有可接受的性能.

从我在F#集中读到的内部使用红黑树作为它们的实现.如果每次我们想要为Red Black Tree添加新内容,我们必须基本上重新创建它,它如何才能获得良好的性能？我在这里错过了什么？

虽然我问F#的集合,但我认为这与任何其他拥有或使用不可变数据结构的语言相关.

谢谢

Answer 1

几乎所有不可变的集合都是某种形式的平衡树.要创建新树,您必须在路径上重新分配从更改(插入,删除,"更新")到根的路径上的节点.只要树是平衡的,这需要对数时间.如果你有类似2-3-4树(类似于红黑树)的东西,预期的outdegree 3,你可以只使用10个分配来处理一百万个元素.

在数据结构预期纯粹的语言中,它们确保分配速度快.分配四元素节点将花费比较,增量和四个存储.在许多情况下,您可以通过多次分配来摊销比较的成本.

如果您想更多地了解这些结构是如何工作的,那么Chris Okasaki的纯功能数据结构就是一个很好的来源.

Answer 2

您不必重新创建整个树.许多分支机构将保持不变并可以"重复使用".举一个简单的例子,如果需要将新节点添加到当前树中的叶子中,则只需要克隆该节点的父节点并给予新分支.

Answer 3

正如其他人指出的那样,您不必重新创建整个数据结构.您只需重新创建已更改的零件并引用保持不变的现有子树.由于数据结构的不变性,您可以重用子树,因此几乎不需要复制所有内容.事实上,如果您需要很少克隆可变数据结构,它可能会产生更大的影响.

特别是对于平行树(例如红黑树),这会给你:

• 从集合中添加/删除元素的O(log N)时间(与可变实现相同)
• 添加/删除元素时的O(log N)空间(新分配)(可变为O(1))

对于某些应用程序来说,这可能是 - 当然 - 开销太大,但实际上并不是那么糟糕.此外,.NET垃圾收集器中的分配非常快(我认为,基本上是O(1)),所以这不是一个真正的问题.更多的分配意味着GC需要更频繁地运行,但这也不像听起来那么重要 - 如今计算机拥有相当多的内存.在许多情况下,.NET 4.0实际上有所帮助(另请参阅Jon Harrop的答案)

Answer 4

正如其他人所说的,不必完全重新创建不可变数据结构,因为它可以重用自身的旧部分.您可以这样做,因为旧部件是不可变的,并且保证数据不会更改.

我有一个不可改变的性能的真实世界的例子.我用F#制作的不可变红黑树做了一些测试,它只比c ++中的std :: sort慢3倍.考虑到它不是专门为排序而设计的,我觉得它真的很快.