不可变数据结构的性能问题

Question

我不明白为什么Set作为一种不可变数据结构，仍然可以有良好的性能。

据我所了解，F#中的Sets内部使用红黑树作为实现方法。如果每次想要向红黑树中添加新元素都需要重新创建它，那么它怎么可能具有良好的性能呢？我在这里缺少了什么东西吗？

虽然我是为F＃的Sets提出这个问题的，但我认为这对于任何其他具有或使用不可变数据结构的语言同样重要。

谢谢

- devoured elysium

---

请参见https://dev59.com/JHI-5IYBdhLWcg3w0MHx。 - user168237

Answer 1

几乎所有不可变集合都是某种平衡树。要创建一个新的树，您必须重新分配从更改（插入、删除、“更新”）到根的路径上的节点。只要树是平衡的，这需要对数时间。如果您有类似于红黑树的2-3-4树，带有预期出度三，您可以使用仅10个分配处理100万个元素。

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

如果您想了解这些结构如何工作的更多信息，请参阅Chris Okasaki的《纯函数式数据结构》。

- Norman Ramsey

---

这本PDF很棒。我原以为我得买这本书...不过我可能还是会买，因为我觉得看书更方便。 - wheaties

请注意，这不是一本书，而是克里斯的论文。书籍包含更多内容，并且是一本优秀的书籍-请购买！ - Dmitry Lomov

@wheaties，@mitya，是的，这本书非常棒——我有两本！Chris Okasaki也是一个很棒的人，我很高兴能够支持他。 - Norman Ramsey

Answer 2

您无需重新创建整个树。许多分支将保持不变，并可被“重复使用”。 举个简单的例子，如果新节点需要添加到当前树中的叶子上，则只需克隆该节点的父级并提供新的分支。

- jyoung

Answer 3

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

特别是对于平衡树（例如红黑树），这为您提供：

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

这可能对某些应用程序来说过于繁琐，但实际上并没有那么糟糕。此外，.NET垃圾收集器中的分配非常快（我认为本质上是O(1)），因此这实际上不是问题。更多分配意味着GC需要更频繁地运行，但这也不像听起来那么关键，因为现代计算机有相当多的内存。 .NET 4.0在许多情况下实际上都有所帮助（另请参见Jon Harrop在此处的答案）。

- Tomas Petricek

---

我认为这个答案实际上回答了这个问题。 - Daniel Buckmaster

Answer 4

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

我有一个不可变性能的现实世界示例。我使用F#制作了一个不可变红黑树并进行了一些测试，它的性能仅比c ++中的std :: sort慢3倍。 我认为这非常快，考虑到它并非专门设计用于排序。

- gradbot

Answer 5

语言语义的限制仅适用于该语言中的源代码。实现（编译器、解释器、运行时环境等）可以自由地进行任何操作，以获得最佳性能，只要保持相同的行为即可。这对大多数语言都是正确的。

编辑：

可以进行几种优化，包括数据共享（因为数据是不可变的），在幕后使用可变性，优化尾调用（因为FP使用大量递归）等。

- Cogwheel

---

是的，但这仍然没有回答我的问题。不可变数据结构如何与它们的非不可变对应物“竞争”？ - devoured elysium

@elysium：不可变数据结构通常与可变数据结构相比，在并行环境下性能不具竞争力，因为它们会产生更多的分配和缓存未命中。 - J D

Answer 6

请参考函数式编程：不可变数据结构的效率（尤其是我的回答，指出了Rich Hickey的演讲），以获取“一般”令人信服的证据，即不可变结构也可以非常高效。

至于在F# Set特定情况下是否真的如此高效，今天可能只有中等水平。在实际情况下，使用更有效的基础结构将是很好的选择（在理论上当然是O(logN)，但在实际情况下是O(1)）。

- Brian

---

我的书《Visual F# 2010 技术计算》对不可变和可变数据结构进行了基准测试，结果显示在 F# 中，不可变数据结构的速度最多慢了 40 倍。有趣的是，在 .NET 4 上，由于新的 GC，不可变数据结构在 F# 中的速度几乎与 Haskell 相当快。 - J D

Answer 7

我不确定这在语言中是如何实现的，但数据结构可以被程序员视为不可变的，而在幕后进行优化。

例如，我有一个列表a=[1,2,3,4,5]。我添加6。b=[a [6]]，它们都可以是不可变的。这样做不会影响性能，并且比复制值更快。

那么，让我问你一个问题，因为我不知道，为什么使用不可变对象会更慢？在树的情况下，我有点理解你的观点。我想你得重新创建当前节点上面的节点，但下面的节点不用（假设我们有子指针而不是父指针）。

- gtrak

Answer 8

简单来说，Set是一种以节点为基础的存储实体。在Set中，您可以将其实现为树形结构，在其中添加元素到Set的下一个版本时，您不需要重新创建所有边缘和节点，而只需创建一组新的边缘。这样做是因为节点本身永远不会改变，里面持有的对象也不会改变。

真正的好处不在于单线程应用程序，而在于多线程应用程序中。不可变数据结构消除了锁定机制的需要。如果它们永远不会改变，您就不必担心状态。

- wheaties