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。
以下是它与另一个 OrderBy(x => identity) 在性能方面的区别：

var result2 = e.Last();

并且

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

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

- Cristian Diaconescu

---

我希望有Min()和Max()返回对象而不是值的版本，这样就可以避免对整个项目集进行排序以获取具有最高或最低值的对象。 - itsme86

假设 BeersBeforeCollapsing 是一个 int，那么这将返回一个 int。不过它也可能是一个浮点数。 - itsme86

不，它返回一个 MyThing。 - Cristian Diaconescu

哦，哇，你说得对！抱歉，我本来会打赌的（而且还会输钱！） - Cristian Diaconescu

LINQ to Object并不执行任何聪明的融合优化。OrderBy().Last()是OrderBy()后跟着Last()，而不是比单独操作更快的东西。你基本上在问为什么就地排序操作List.Sort(使用introsort)比Enumerable.OrderBy(使用quicksort，受到要求通过键选择器lambda进行比较的限制)更快。如果你想深入了解这个问题，benchmark.net可能会告诉你答案。 - Jeroen Mostert

Answer 1

似乎 List 在比较使用 Comparer.Default 或没有 IComparer 的类型时，会使用 特殊优化的 C++ 版本排序。而 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来为MyInt创建一个Comparer，那么List.Sort与OrderBy差不多：

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

- NetMage