不可变数据结构性能

Question

我不明白为什么作为一个集合的东西是不变的，并且仍然有一个可以接受的性能。

根据我在F# Set中读到的内容，内部使用Red Black Trees作为它们的实现。如果每次我们想要向Red Black树添加新的东西，我们必须基本上重新创建它，它怎么会有好的性能呢？这里我漏掉了什么？

虽然我问的是F#的集合，但我认为这在任何其他具有或使用不可变数据结构的语言中都是一样的。

谢谢

Answer 1

几乎所有不可变的集合都是某种形式的平衡树。要创建新的树，您必须将路径上的节点从更改(插入、删除、“更新”)重新分配到根目录。只要树是平衡的，这就需要对数时间。如果您有一个2-3-4树(类似于红黑树)，并且预期出度为3，那么您可以使用10个分配来处理一百万个元素。

在期望数据结构是纯数据结构的语言中，它们确保分配是快速的。分配一个包含四个元素的节点将耗费一个比较、一个增量和四个存储。在许多情况下，您可以在多个分配中摊销比较的成本。

如果你想更多地了解这些结构是如何工作的，一个很好的来源是Chris Okasaki的。

Answer 2

您不必重新创建整个树。许多分支将保持不变，可以“重用”。举个简单的例子，如果需要将新节点添加到当前树的叶子中，那么只需要克隆该节点的父节点并为其分配新的分支。

Answer 3

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

特别是，对于平衡树(如红黑树)，这将为您提供：

• O( implementation)
• O(log N)在集合中添加/删除元素的时间(与可变log N相同)空间(新的分配)当添加/删除元素时(可变的将具有O(1))

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