c# - Microsoft.Bcl.Immutable中的ImmutableList <T> Remove方法的性能降低

从NuGet软件包Microsoft.Bcl.Immutable 1.0.34版和1.1.22-beta版本的Microsoft ImmutableList中体验到一些意外的性能

从不可变列表中删除项目时，性能非常慢。
对于包含20000个整数值(1 ... 20000)的ImmutableList，如果开始从值20000删除为1，则大约需要52秒才能从列表中删除所有项。
如果我对通用List<T>进行相同操作，则在每次删除操作后在列表中创建一个副本，这大约需要500毫秒。

我对这些结果感到有些惊讶，因为我认为ImmutableList比复制通用的List<T>更快，但这也许是可以预期的吗？

范例程式码

// Generic List Test
var genericList = new List<int>();

var sw = Stopwatch.StartNew();
for (int i = 0; i < 20000; i++)
{
    genericList.Add(i);
    genericList = new List<int>(genericList);
}
sw.Stop();
Console.WriteLine("Add duration for List<T>: " + sw.ElapsedMilliseconds);
IList<int> completeList = new List<int>(genericList);

sw.Restart();

// Remove from 20000 -> 0.
for (int i = completeList.Count - 1; i >= 0; i--)
{
    genericList.Remove(completeList[i]);
    genericList = new List<int>(genericList);
}
sw.Stop();
Console.WriteLine("Remove duration for List<T>: " + sw.ElapsedMilliseconds);
Console.WriteLine("Items after remove for List<T>: " + genericList.Count);


// ImmutableList Test
var immutableList = ImmutableList<int>.Empty;

sw.Restart();
for (int i = 0; i < 20000; i++)
{
    immutableList = immutableList.Add(i);
}
sw.Stop();
Console.WriteLine("Add duration for ImmutableList<T>: " + 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<T>: " + sw.ElapsedMilliseconds);
Console.WriteLine("Items after remove for ImmutableList<T>: " + immutableList.Count);

更新

如果像普通的foreach循环一样从ImmutableList的开头删除项目，那么的性能会更好。然后，删除所有项目不到100毫秒。
这不是您在所有情况下都可以执行的操作，但是很高兴知道。

最佳答案

Remove方法必须扫描整个列表以找到要删除的元素。删除本身为O(1)，因为仅最后一个元素需要弹出。两种算法都具有二次性能。

为什么运行时差异巨大？可能是因为ImmutableList在内部是树结构。这意味着要扫描列表，将有大量的指针取消引用以及不可预测的分支和内存访问。那太慢了。

关于c# - Microsoft.Bcl.Immutable中的ImmutableList <T> Remove方法的性能降低，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24785116/