ImmutableList 和 List 的一般性能比较？

Question

我认为 ImmutableList 在添加和删除元素方面比 List 慢得多。那正确吗？

基准测试。添加的 ImmutableList 和 RemoveAt 的性能很好。RemoveAt 甚至比 List 更快。

    static void Main(string[] args)
    {
        // Generic List Test
        var genericList = new List<int>();

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

结果

Add duration for List<T>: 0
Remove duration for List<T>: 37
Items after remove for List<T>: 0
Add duration for ImmutableList<T>: 22
Remove duration for ImmutableList<T>: 14
Items after remove for ImmutableList<T>: 0

Answer 1

老实说，不变性意味着缺乏性能是一个神话。

我希望使用不可变列表可以更快地进行许多操作。

不可变列表的实现使用二叉搜索树，与数组的搜索、插入和删除相比，它具有良好的性能特征。复制这些因素仍然存在开销。因此，会有一个临界点，其中一个会比另一个表现更好。

我的机器的删除结果（不可变/常规）毫秒

     Deletes  100       1000      10000     100000
Count         
 1000         4/0       na        na        na
10000         4/0       5/1       na        na  
  1e5         4/2       5/23      22/215    na  
  1e6         7/44      8/431     37/4676   118/44081 
  1e7         8/718     7/7363    36/77638  110/x*
  1e8         8/7594    9/76200   31/781349 113/x* 

* I didn't have the patience to finish benchmarking here.