是否在某处记录了ImmutableList<T>的性能特征?我对渐近复杂度(大0)感兴趣。msdn链接没有透露太多信息。
从这篇文章中我已经知道Add和this[]都是O(log n)，但是我还想知道Remove和Insert。
如果可能的话，我也想看看新引入的System.Collections.Immutable名称空间中整个类型的复杂性。
嗯，基于对代码的一些检查，我希望RemoveAt (Remove必须首先找到项目)和Insert与Add几乎相同。基本原理是一样的。我更担心的是内存使用模式和类似的事情—如果您并排使用几个ImmutableList并进行大量的添加和删除，我预计您可能很快就会遇到数据局域性问题，这将导致您的性能急剧下降。AddRange主要是一个快捷方式，它实际上只调用了一堆Node.Add s，节省了一些开销，但不是很多。还有很多递归
ImmutableArray不会导致这种情况，因为它总是创建一个全新的数组并复制旧数组。因此，它将导致大量的内存复制和分配/收集，但它也将更加稳定的性能-访问时间不会随着使用而改变，甚至在修改数组时没有任何快捷方式，您总是必须复制所有项。这也意味着添加多个项目只需要用AddRange来完成——性能差异将是巨大的。Add是使用Insert在内部实现的，所以现在是一样的。换句话说，所有的修改操作都是o/o (n)，而读取操作是o/o(1)。
总而言之，ImmutableList更关心频繁的更改和牺牲读性能，而ImmutableArray主要用于大量的读取和相对较少的更改。