c# - Linq OrderBy() 与 List.Sort() 的速度

Question

这是随机整数的枚举:

var r = new Random();
var e = Enumerable.Repeat(1, 10_000_000).Select( _ => r.Next());

你认为哪个版本更快:

var result = e.OrderBy(x => x).Last(); //materialize the IEnumerable

或

var l = e.ToList();
l.Sort();
var result = l.Last();

我希望第一个示例中的 .OrderBy(x => x).Last() 是优化为仅对列表的一小部分进行排序或仅对列表进行 O(n) 遍历。

剧透:不是。

不过，这两个版本的性能至少应该不相上下吧？我的意思是:

在第一个中，OrderBy() 分配一个临时数组并对其进行排序。
在第二个中，我显式分配了一个列表并将 Sort() 就位。

实际结果表明 OrderBy() 示例慢了 4-5 倍! (5-6 秒对 1.2-1.3 秒)

谁能解释一下为什么？

.OrderBy(x => x) 案例确实为每个元素执行其 x => x 标识 lambda。
两者的区别:

var result2 = e.Last();

和

var result2 = e.Select(x=>x).Last();

是可测量的，但很小:在第二种情况下多 30 - 50 毫秒。所以这并不能解释巨大的差距。

Answer 1

看来 List有一个special optimized C++ version of sorting它在与 Comparer.Default 比较类型时使用或者没有 IComparer对于类型。 OrderBy总是进行适用于任何类型的通用排序，并且 IComparer .

如果替换 Select对象类型为 MyInt 的结果如下:

public class MyInt : IComparable {
    public int value;
    public MyInt(int newv) => value = newv;

    public int CompareTo(object obj) {
        if (obj is MyInt m2) {
            return value.CompareTo(m2.value);
        }
        else if (obj is int i2) {
            return value.CompareTo(i2);
        }
        else {
            throw new Exception($"can't compare MyInt to {obj.GetType()}");
        }
    }
}

var e = Enumerable.Repeat(1, 10_000_000).Select(_ => new MyInt(r.Next()));

然后 OrderBy将比 List.Sort 快 2 倍方法。

请注意，如果您使用 Comparer<>.Create创建一个 Comparer对于 MyInt , List.Sort与OrderBy差不多:

l.Sort(Comparer<MyInt>.Create((m1,m2) => m1.value.CompareTo(m2.value)));