linq - 为什么这个 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 的:

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)，这会慢几个数量级。