不可变集合的效率本质上比可变集合低吗？

Question

不可变集合的效率本质上比可变集合低吗？

3

不可变对象是指无法更改状态的对象。它们在测试和调试方面比较容易，而且在并发编程中非常有用。然而，与可变的同类对象相比，当前实现的不可变集合性能较差。例如，将关联数组实现为不可变红黑树，平均插入/删除时间复杂度为O(log(n))，而哈希表平均插入/删除时间复杂度为O(1)。

通常情况下，不可变集合是否可以证明比可变集合效率低，或者我们是否会找到与可变集合一样快速的不可变实现？

- Joshua

@JoachimPileborg 注意到并修复了平均效率问题。 - Joshua

可能是如何在函数式语言中实现哈希表？的重复问题（至少有一个答案在那里谈到了性能）。 - Sylwester

2

可能是纯函数式编程的效率的重复问题。 - user395760

1

对于严格纯函数语言（在某种计算模型中，可能不是普遍适用的），存在一个O(log n)的减速因子；对于惰性纯函数语言，不存在渐近减速的证明或反驳。 - user395760

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Zach Halle · Accepted Answer

Okasaki展示了开发不可变数据结构“具有等效渐进性能”与它们的命令式对应物通常是可能的。不过，不可变结构可能会有更差的常量。但是，你可能会在性能上付出代价，但你会在程序员时间上得到回报；正如你所说，使用和理解不可变集合要容易得多。从这个角度来看，这个问题有些类似于我们为什么在C语言如此快速的时候还要使用其他语言的经常问法。因为它更容易使用，并且我们珍视程序员的时间。