OrderBy扩展方法如何收集订单

Question

假设我们有一个类Foo，它有一个Int32字段Bar，并且您想要按Bar值对Foo对象的集合进行排序。一种方法是实现IComparable的CompareTo()方法，但也可以像这样使用语言集成查询(LINQ)来实现

List<Foo> foos = new List<Foo>();
// assign some values here
var sortedFoos = foos.OrderBy(f => f.Bar);

现在在sortedFoos中，我们有了排序的foos集合。但是，如果使用System.Diagnostics.StopWatch对象来衡量OrderBy()对集合进行排序所用的时间，则始终为0毫秒。但无论何时打印sortedFoos集合，它显然都是经过排序的。这怎么可能。对集合进行排序不需要花费时间，但是在方法执行之后，集合是排序的吗？有人能给我解释一下这是怎么回事吗？还有一件事。假设在对foos集合进行排序后，我向其添加了另一个元素。现在，每当我打印出集合的时候，我添加的元素应该在最后，对吧？错了！foos集合的排序方式是这样的，我添加的元素是foos集合的一部分，即使我在排序后将该元素添加到foos中。我不明白这些是如何工作的，所以有人能为我解释清楚吗?！

Answer 1

LINQ相信延迟执行。这意味着只有在开始迭代或访问结果时才会对表达式求值。

Answer 2

几乎所有的LINQ方法都使用惰性求值--它们不会立即执行任何操作，但是当您请求数据时，它们会设置查询来执行正确的操作。

OrderBy也遵循这个模型--尽管它没有像Where和Select这样的方法那么懒惰。当您请求OrderBy结果的第一个结果时，它将读取源中的所有数据，对所有数据进行排序，然后返回第一个元素。例如，与Select相比，请求投影中的第一个元素仅要求源中的第一个元素。

如果你对LINQ to Objects在幕后是如何工作的感兴趣，你可能想读一读我的Edulinq blog series - LINQ to Objects的一个完整的重新实现，其中有一篇博客文章描述了每个方法的行为和实现。

(在我自己的OrderBy实现中，我实际上只是懒惰地排序--我使用快速排序，并且排序“恰到好处”以返回下一个元素。这可以使像largeCollection.OrderBy(...).First()这样的事情变得更快。)

Answer 3

OrderBy扩展使用它正在使用的类型的默认IComparer，除非通过适当的重载传递替代方法。

排序工作将被推迟，直到首次访问语句返回的IOrderedEnumerable<T>。如果将Stopwatch放在第一次访问的周围，就会看到排序需要多长时间。

这很有意义，因为您的语句可以由多个返回IOrderedEnumerable的调用组成。由于排序调用是链接的，因此它们可以流畅地扩展结果，允许最终返回的IOrderedEnumerable以最方便的方式执行排序。这可能是通过链接所有IComparer调用并排序一次来实现的。贪婪的实现将不得不多次进行浪费排序。

例如，考虑

class MadeUp
{
    public int A;
    public DateTime B;
    public string C;
    public Guid D;
}

var verySorted = madeUps.OrderBy(m => m.A)
                    .ThenBy(m => m.B)
                    .ThenByDescending(m => m.C)
                    .ThenBy(m => m.D);

如果verySorted被贪婪地求值，那么序列中的每个属性都将被求值，并且序列将被重新排序4次。因为IOrderedEnumerable的linq实现将排序推迟到枚举，所以它能够优化该过程。

用于A、B、C和D的IComparer可以组合成一个复合委托，类似于下面的简化表示，

int result
result = comparerA(A, B);
if (result == 0)
{
    result = comparerB(A, B);
    if (result == 0)
    {
        result = comparerC(A, B);
        if (result == 0)
        {
            result = comparerD(A, B);
        }
    }
}

return result;

然后使用复合委托对序列进行一次排序。