为什么LINQ操作比普通循环更快？

Question

为什么LINQ操作比普通循环更快？

5

今天在一次编程讨论中，我和一个朋友有些困惑。我们举了一个虚构的问题作为例子：有一个由n个随机整数（通常为100万）组成的List，我们想创建一个返回所有重复出现的整数集合的函数。这是相当简单的事情。我们创建了一个LINQ语句来解决这个问题，还有一个基于插入排序的算法。

现在，当我们测试代码运行速度时（使用System.Diagnostics.StopWatch），结果令人困惑。不仅LINQ代码比简单的排序要快，而且它比只对列表进行单次循环且没有任何操作的单个foreach/for循环也要快（顺带一提，我认为编译器应该能够发现并完全删除这些操作）。

如果我们在同一程序执行中生成新的随机数List并再次运行LINQ代码，则性能将增加数千倍。空循环的性能当然相同。

那么，这里到底发生了什么？是LINQ使用并行处理来优化普通循环吗？这些结果怎么可能呢？LINQ使用快速排序，其运行时间为n*log(n)，根据定义已经比n慢了。

第二次运行时的性能飞跃是怎么回事？

我们对这些结果感到困惑和好奇，并希望从社区中获得一些澄清性见解，以满足我们自己的好奇心。

- Pedery

12

请贴上一些代码。 - Kirk Woll

1

也许你可以分享一下你的测试？ - brian chandley

12

请发布您的代码。您可能没有考虑到延迟执行。 (Deferred execution)。 - Matthew Flaschen

我非常有兴趣看到那段代码并自己尝试一下...但你说它甚至比一个空循环更快，这强烈暗示你在代码中没有在正确的位置进行计时，正如Matthew Flaschen的评论所述。 - Andrew Barber

1

"Linq使用快速排序，其运行时间为nlog(n)，根据定义已经比n慢。但这并不完全正确。nlog(n)在渐进意义下比n慢，但常数因素可能会导致在实践中，n*log(n)算法在某些数据集上比线性算法更快。" - Chris Schmich

显示剩余4条评论

3个回答

1

我建议当你的算法不够完美（或者你的代码存在问题）时，LINQ 才比“普通循环”更快。所以如果你没有编写高效的排序算法等，使用 LINQ 进行排序会比你更快。

LINQ 通常与普通循环的速度“一样快”或“足够接近”，并且编码/调试/阅读起来更简单。这是它的优点——而不是执行速度。

如果它比空循环执行得更快，那么你肯定做错了什么。最有可能的情况是，如评论中所建议的那样，你没有考虑延迟执行，因此 LINQ 语句实际上并没有执行。

- Kirk Broadhurst

正如我在上面的评论中所说，我们打印了数据集并且所有的都似乎没问题。 - Pedery

你需要在秒表停止之前将其打印出来。然而，打印太慢了 - 最好将其转储到列表中。 - Kirk Broadhurst

呵呵，将我写的任何东西与BCL中的任何内容进行比较，是的，我的所有代码都不完美。 :O - Christopher Painter

1

如果您没有启用“优化代码”进行编译，那么您可能会看到这种行为。（这肯定可以解释为什么空循环没有被删除。）

然而，支持LINQ的代码是已经编译好的代码的一部分，这肯定已经被优化了（由JIT、NGen或类似工具进行优化）。

- Zooba

+1 好观点！我忘记检查计算机的VS默认设置，以优化代码。 - Pedery

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tvanfosson · Accepted Answer

毫无疑问，您并没有实际执行查询，只是定义了它。LINQ构造了一个表达式树，直到执行需要遍历枚举的操作时才会实际评估。尝试在LINQ查询中添加ToList()或Count()操作，以强制评估查询。

根据您的评论，我预计这与您所做的类似。注意: 我没有花时间确定查询是否尽可能高效; 我只想要一些查询来说明代码可能如何构造。

var dataset = ...

var watch = Stopwatch.StartNew();

var query = dataset.Where( d => dataset.Count( i => i == d ) > 1 );

watch.Stop();  // timer stops here

foreach (var item in query) // query is actually evaluated here
{
   ... print out the item...
}