时间戳

首页 > 解决方案 > 为什么 C# OrderBy 这么快？

c# - 为什么 C# OrderBy 这么快？

问题描述

看看这个例子：https ://repl.it/repls/PuzzledAthleticMacroinstruction

它创建具有随机值的对象列表，然后对它们进行排序。根据 n*log(n) 的大 O，您会期望排序花费的时间最长。但是，排序比生成列表要快得多。

输出是：

Generate list in 8421 milliseconds
Sort in 46 milliseconds
Before sorting, first element was 8445383 and last element was 11537420
After sorting, first element is 0 and last element is 11999999

这似乎是不可能的。

标签： c#algorithmperformancelinqsorting

解决方案

为什么 C# OrderBy 这么快？

因为它实际上并没有对集合进行排序。它将排序操作添加到表达式树并返回该表达式树以供以后可能的评估。然后，您可以将进一步的操作附加到该表达式树，并且在您从中读取数据之前不会对其进行评估。

考虑一下这些 LINQ 扩展方法最常见的用途可能是什么……查询数据库。您不希望为添加到树中的每个操作一遍又一遍地查询数据库。毕竟，如果其中一个操作是 a.Where()会大大减少结果的数量。将所有数据具体化到内存中，执行 N 次操作，最终还是最终过滤掉数据，这将是愚蠢的。相反，如果需要实际数据，则构建逻辑表达式树，然后将其转换为针对数据库的大型（但已优化）查询。

您的代码中也发生了同样的事情。事实上，细心的观察者会在运行代码时注意到最后两条语句之间的时间相对较长（至少是人类可观察到的）。

Console.WriteLine($"Before sorting, first element was {unsorted.First().Foo} and last element was {unsorted.Last().Foo}");

Console.WriteLine($"After sorting, first element is {sorted.First().Foo} and last element is {sorted.Last().Foo}");

这意味着第二条语句需要相当长的时间来执行。第二条语句似乎正在做的只是从集合中读取一个值。 但是，由于它是从集合中读取的第一个操作，即在计算表达式树时以及最终对集合进行排序时。sorted

如果您想在调用时强制执行排序操作.OrderBy()，实现整个集合的最简单方法是追加.ToList()：

var sorted = unsorted.OrderBy(element => element.Foo).ThenBy(element => element.Bar).ToList();

这样做你会发现“排序”操作现在需要人类可观察到的时间，而输出元素的最后两个语句根本不需要时间。

推荐阅读