functional-programming - 不可变集合本质上是低效的吗

Question

不可变对象(immutable对象)是不能改变状态的对象。它们更容易测试和调试，并且在并发编程中非常有用。但是，与可变集合相比，当前不可变集合的实现性能较差。例如，将关联数组实现为一棵不可变的红黑树平均具有 O(log(n)) 次插入/删除，而哈希表平均具有 O(1) 次插入/删除。

一般来说，不可变集合是否比它们的可变表亲效率​​低，或者我们有一天会找到同样快的不可变实现？

Answer 1

Okasaki证明通常可以开发“具有等效渐近性能”的不可变数据结构作为它们的命令式对应物。然而，不可变结构可能具有更差的常量。但是，您可能为性能付出的代价确实会在程序员时间中得到返回；正如您所说，使用和理解不可变集合要容易得多。通过这种方式，这个问题有点类似于反复出现的问题，即为什么我们在 C 如此之快的情况下使用其他语言。因为它更容易，而且我们重视程序员的时间。