.net - ImmutableList 的性能特点

Question

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

从这篇文章中我已经知道Add并且this[]都是 O(log n) ，但我也想知道and 。RemoveInsert

---

我也很想看看新引入的System.Collections.Immutable命名空间中所有类型的复杂性是否可能。

Answer 1

好吧，根据对代码的一些检查，我希望RemoveAt（Remove必须首先找到该项目）并且Insert与Add. 基本原理是一样的。我更担心的是内存使用模式之类的东西 - 如果你ImmutableList并排使用几个 s 并进行大量添加和删除，我希望你可能会很快遇到数据局部性问题，这会导致你的表现直线下降。AddRange主要是一个捷径，反正它真的只调用一堆Node.Adds，节省一些开销，但不多。还有很多递归。

ImmutableArray不会导致这种情况，因为它总是创建一个全新的数组并复制旧数组。所以它会导致大量的内存复制和分配/收集，但它也会在性能方面更加稳定 - 访问时间不会随着使用而改变，并且在修改数组时甚至没有任何快捷方式，你总是有复制所有项目。这也意味着只需添加多个项目AddRange- 性能差异将是巨大的。Add是使用内部实现Insert的，所以现在是一样的。换句话说，所有的更改操作都是o/O(n)，而读取是o/O(1)。

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