不可变数据结构性能 [英] Immutable data structures performance

问题描述

我不知道如何将某些东西作为一个不可变的，仍然有一个可以接受的表现。

从我在F＃中读取的内容使用红黑树作为其实现。如果每次我们想要添加一些新的红黑树，我们必须基本上重新创建它，它有怎样的表现呢？我在这里缺少什么？

虽然我问F＃的集合，但我认为这与使用或使用不可变数据结构的任何其他语言相关。 p>

谢谢

解决方案

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

在数据结构预计为纯粹的语言中，它们确保分配快。分配四元素节点将花费比较，增量和四个商店。在许多情况下，您可以在多个分配中分摊比较成本。

如果您想了解更多关于这些结构如何工作，一个很好的来源是 纯功能数据结构 由Chris Okasaki。

I don't get how can something as a Set be immutable and still have an acceptable performance.

From what I've read in F# Sets internally use Red Black Trees as their implementation. If each time we want to add something new to a Red Black Tree we have to basically recreate it, how can it have ever good performance? What am I missing here?

Although I am asking this for F#'s Sets, I think this is as relevant in any other language which has or uses immutable data structures.

Thanks

解决方案

Almost all immutable collections are some form of balanced tree. To create a new tree, you have to reallocate nodes on the path from the change (insert, remove, "update") to the root. As long as the tree is balanced this takes logarithmic time. If you have something like a 2-3-4 tree (similar to red-black trees) with expected outdegree three, you can handle a million elements using only 10 allocations.

And in languages where data structures are expected to be pure, they make sure allocation is fast. Allocating a four-element node is going to cost a compare, an increment, and four stores. And in many cases you can amortize the cost of a compare over several allocations.

If you want to know more about how these structures work, an excellent source is Purely Functional Data Structures by Chris Okasaki.

这篇关于不可变数据结构性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！