ImmutableList 中的性能降低Microsoft.Bcl.Immutable中的删除方法
从NuGet包Microsoft.Bcl.Immutable版本1.0.34以及1.1.22-beta中体验Microsoft ImmutableList一些意外性能
从不可变列表中删除项目时，性能非常慢。 对于包含20000个整数值（1 … 20000）的ImmutableList ，如果开始从值20000移除到1，则从列表中删除所有项目大约需要52秒。 如果我使用通用List执行相同操作，我在每次删除操作后创建列表副本大约需要500毫秒。
我对这些结果感到有些惊讶，因为我认为ImmutableList比复制通用List更快，但也许这是预期的？
示例代码
// Generic List Test var genericList = new List(); var sw = Stopwatch.StartNew(); for (int i = 0; i < 20000; i++) { genericList.Add(i); genericList = new List(genericList); } sw.Stop(); Console.WriteLine("Add duration for List: " + sw.ElapsedMilliseconds); IList completeList = new List(genericList); sw.Restart(); // Remove from 20000 -> 0. for (int i = completeList.Count - 1; i >= 0; i--) { genericList.Remove(completeList[i]); genericList = new List(genericList); } sw.Stop(); Console.WriteLine("Remove duration for List: " + sw.ElapsedMilliseconds); Console.WriteLine("Items after remove for List: " + genericList.Count); // ImmutableList Test var immutableList = ImmutableList.Empty; sw.Restart(); for (int i = 0; i < 20000; i++) { immutableList = immutableList.Add(i); } sw.Stop(); Console.WriteLine("Add duration for ImmutableList: " + sw.ElapsedMilliseconds); sw.Restart(); // Remove from 20000 -> 0. for (int i = completeList.Count - 1; i >= 0; i--) { immutableList = immutableList.Remove(completeList[i]); } sw.Stop(); Console.WriteLine("Remove duration for ImmutableList: " + sw.ElapsedMilliseconds); Console.WriteLine("Items after remove for ImmutableList: " + immutableList.Count);
更新
如果从ImmutableList的开头删除项目，就像使用普通的foreach循环一样，那么性能要好得多 。 删除所有项目然后花费不到100毫秒。 这不是你可以在所有场景中做的事情，但可以很好地了解。
Remove方法必须扫描整个列表以找到要删除的元素。 删除本身是O（1）因为只需要弹出最后一个元素。 两种算法都具有二次性能。
为什么运行时间差异很大？ 可能，因为ImmutableList是内部的树结构。 这意味着要扫描列表，会有大量指针解除引用和不可预测的分支和内存访问。 那很慢。