.net - ImmutableList 的性能特征

Question

是否在某处记录了 ImmutableList<T> 的性能特征？ ?我对渐近复杂性(big-O)感兴趣。 msdn 链接没有透露太多。

我知道 Add和 this[]都是 O(log n) from this article ，但我也想知道 Remove和 Insert .

如果可能的话，我也很想看看新引入的 System.Collections.Immutable 中整个类型的复杂性。命名空间。

Answer 1

好吧，根据对代码的一些检查，我希望 RemoveAt ( Remove 必须先找到该项目)和 Insert与 Add 几乎相同.基本原理是一样的。我更担心的是内存使用模式和类似的东西 - 如果你使用几个 ImmutableList s 并排并执行大量添加和删除操作，我预计您可能会很快遇到数据局部性问题，这会导致您的性能下降。 AddRange多半是捷径，真的只是调用一堆Node.Add无论如何，节省了一些开销，但不多。还有很多递归。
ImmutableArray不会导致这种情况，因为它总是创建一个全新的数组并复制旧数组。所以它会导致大量的内存复制和分配/收集，但它在性能方面也会更加稳定 - 访问时间不会随着使用而改变，并且在修改数组时甚至没有任何快捷方式，你总是有复制所有项目。这也意味着添加多个项目只需使用 AddRange 即可完成。 - 性能差异将是巨大的。 Add使用 Insert 在内部实现，所以现在是同样的事情。换句话说，所有的更改操作都是 o/O(n)，而读取是 o/O(1)。

总而言之，ImmutableList更关心频繁变化和牺牲读取性能，而ImmutableArray主要用于大量读取和相对较少的更改。