不可变的数据结构性能
我不明白如何能够作为一个集合是不可改变的，仍然有一个可以接受的性能。
从我读过的F＃集内部使用红黑树作为他们的实现。 如果每次我们要为红黑树添加新的东西，我们必须基本上重新创build它，怎么会有好的performance？ 我在这里错过了什么？
虽然我问这个F＃的集合，我认为这是任何其他语言具有或使用不变的数据结构相关。
谢谢
几乎所有不可变的集合都是某种forms的平衡树。 要创build一个新的树，必须重新分配从更改（插入，删除，“更新”）到根的path上的节点。 只要树是平衡的，这需要对数时间。 如果你有2-3-4树（类似于红黑树），并且期望超过3，那么你只能使用10个分配来处理一百万个元素。
在数据结构预期纯净的语言中，他们确保分配速度很快。 分配一个四元素节点将花费一个比较，一个增量和四个存储。 而且在很多情况下，您可以分摊比较的成本。
如果你想更多地了解这些结构是如何工作的，一个很好的来源是Chris Okasaki的“ Purely Functional Data Structures” 。
你不必重新创build整棵树。 许多分支将保持不变，可以“重用”。 作为一个简单的例子，如果新节点需要被添加到当前树中的一个叶，那么只有该节点的父节点需要被克隆并赋予新的分支。
正如其他人指出的那样，您不必重新创build整个数据结构。 您只需重新创build已更改的零件，并引用保持不变的现有子树。 由于数据结构的不变性，您可以重用子树，因此几乎不需要复制所有内容。 事实上，如果你很less需要克隆一个可变的数据结构，它可能会有更高的影响。
特别是，对于一棵平凡的树木（如红黑树），这给你：
- O（log N）添加/删除元素的时间（与可变实现相同）
- O（log N）空间（新分配）时添加/删除元素（mutable将有O（1））
对于某些应用程序来说，这可能会 – 当然是太多了，但实际上并不是那么糟糕。 而且，在.NET垃圾收集器中的分配速度非常快（我认为，本质上是O（1） ），所以这不是一个真正的问题。 更多的分配意味着GC需要更频繁地运行，但这也不像听起来那么重要 – 现在电脑有相当多的内存。 在许多情况下，.NET 4.0确实有帮助（另请参阅Jon Harrop的答案 ）
正如其他人所说，不可变数据结构不必完全重新创build，因为它可以重用自己的旧部分。 你可以这样做，因为旧的部分是不可变的，数据保证不会改变。
我有一个真实世界的不变performance的例子。 我用一个我在F＃中创build的不可改变的红黑树做了一些testing，它只比c ++中的std :: sort执行慢3倍。 考虑到它不是专门为sorting而devise的，我认为这是非常快的。
语言语义的局限只适用于语言中的源代码。 只要保持相同的行为，实现（编译器，解释器，运行时环境等）就可以自由地执行任何想要的最佳性能。 大多数语言都是如此。
编辑：
可以做一些优化，包括数据共享（正是因为数据是不可变的），在后台使用可变性，优化尾部调用（因为FP使用大量recursion）等等。
看到
函数式编程：不变的数据结构效率
（特别是我的回答指向Rich Hickey的谈话）“一般”令人信服的证据表明，不变的结构也是非常有效的。
至于在F＃ Set的具体情况下这是如此的恰到好处，或许今天的情况只是适度的。 使用更有效的底层结构（以实用术语来说是很好的;理论上讲，一切都是O（logN）（实际上是O（1）） ）。
很简单，Set是一个基于节点的存储实体。 在一个Set的情况下，你可以实现它作为一个树，当你添加一个元素到Set的下一个版本时，你不会重新创build所有的边和节点，而只是创build一组新的边。 你可以做到这一点，因为节点本身永远不会改变，对象也不会被改变。
在单线程应用程序中发现真正的好处，而在multithreading应用程序中。 不可变的数据结构消除了对locking机制的需求。 如果他们永远不会改变，你不必担心状态。
不知道这是如何在语言中实现的，但数据结构可以被认为是程序员不可改变的，但在幕后进行优化。
例如，我有一个列表a = [1,2,3,4,5]。 我追加了6. b = [a [6]]，它们都可以是不可变的。 这样做不会失去任何性能，而且比复制值更快。
所以，让我问你，因为我不知道，为什么做事会变慢一点？ 在树的情况下，我看你的观点。 你必须重新创build当前节点上的节点，我猜，但不是下面（假设我们有孩子指针而不是父指针）。
