.net - 不可变数据结构性能

Question

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

根据我在 F# Sets 中读到的内容，内部使用红黑树作为其实现。如果每次我们想要向红黑树添加新内容时，我们基本上都必须重新创建它，那么它如何才能具有良好的性能呢？我在这里缺少什么？

尽管我是针对 F# 的集合提出这个要求，但我认为这与具有或使用不可变数据结构的任何其他语言一样相关。

谢谢

Answer 1

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

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

如果您想了解更多有关这些结构如何工作的信息，一个很好的来源是 Purely Functional Data Structures作者:克里斯·冈崎。