为什么这个LINQ这么慢？

Question

任何人都可以解释为什么下面的第三个查询比其他查询慢几个数量级,因为它不应该比按顺序执行前两个更长时间？

var data = Enumerable.Range(0, 10000).Select(x => new { Index = x, Value = x + " is the magic number"}).ToList();
var test1 = data.Select(x => new { Original = x, Match = data.Single(y => y.Value == x.Value) }).Take(1).Dump();
var test2 = data.Select(x => new { Original = x, Match = data.Single(z => z.Index == x.Index) }).Take(1).Dump();
var test3 = data.Select(x => new { Original = x, Match = data.Single(z => z.Index == data.Single(y => y.Value == x.Value).Index) }).Take(1).Dump();

编辑:我已经在原始数据生成中添加了.ToList(),因为我不希望任何重复生成的数据使问题蒙上阴影.

我只是试图理解为什么这个代码如此缓慢,而不是寻找更快的替代方案,除非它对此问题有所了解.我想如果Linq被懒惰地评估,我只是在寻找第一项(Take(1))然后test3's:

data.Select(x => new { Original = x, Match = data.Single(z => z.Index == data.Single(y => y.Value == x.Value).Index) }).Take(1);

可以减少到:

data.Select(x => new { Original = x, Match = data.Single(z => z.Index == 1) }).Take(1)

在O(N)中,数据的第一项在内部Single()对数据进行一次完整扫描后成功匹配,剩下的Single()再次扫描数据.所有O(N)仍然如此.

它显然是以更长时间的方式处理,但我真的不明白如何或为什么.

Test3需要几秒钟的时间来运行,所以我认为我们可以安全地假设如果您的答案具有10 ^ 16的数字,那么您在某个地方就犯了一个错误.

Answer 1

前两个"测试"是相同的,都很慢.第三个增加了另一个整体缓慢程度.

这里的前两个LINQ语句本质上是二次的.由于"匹配"元素可能需要遍历整个"数据"序列以便找到匹配项,因此当您在整个范围内前进时,该元素的时间长度将逐渐变长.例如,第10000个元素将强制引擎迭代原始序列的所有10000个元素以找到匹配,从而使其成为O(N ^ 2)运算.

"test3"操作将这一点带到一个全新的痛苦程度,因为它在第二个单元中"平方"O(N ^ 2)操作 - 迫使它在第一个单元之上进行另一个二次运算 - 这将是成为一项庞大的业务.

每次你使用匹配进行data.Single(...),你正在进行O(N ^ 2)操作 - 第三次测试基本上变成O(N ^ 4),这将慢几个数量级.