为什么这个LINQ查询如此缓慢？

Question

为什么这个LINQ查询如此缓慢？

4

请问为什么第三个查询比前两个慢了几个数量级，明明不应该比按顺序执行前两个查询的时间长吗？

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)

在数据的第一项通过内部Single()函数进行一次完整扫描后成功匹配，留下剩余的Single()函数需要对数据再进行一次扫描。因此，仍然是O(N)时间复杂度。

显然，这种方式处理数据更加冗长，但我不太理解其如何或为何。

顺便提一下，Test3运行需要几秒钟的时间，因此如果你的答案中出现了10^16这个数字，我们可以安全地假定你在某个地方犯了错误。

- stovroz

可能是因为它需要完成更多数量级的工作，你为什么认为它不应该花费更长时间呢？ - NotMe

1

@Jay：他一定在使用LINQPad。这是一个将结果转储到结果窗格的内置方法。 - Dave Swersky

嗨，Jay。Dump只是一个LinqPad扩展方法，它将其发送到控制台。 - stovroz

你可以用 ToList() 替换 Dump() ，并在没有 LINQPad 的情况下观察到减速。 - Jay Bazuzi

我应该为笑了Take(1).Dump()感到羞耻吗？ - Chris

2个回答

1

已修复。

var data = Enumerable.Range(0, 10000)
  .Select(x => new { Index = x, Value = x + " is the magic number"})
  .ToList();

var forward = data.ToLookup(x => x.Index); 
var backward = data.ToLookup(x => x.Value);

var test1 = data.Select(x => new { Original = x,
  Match = backward[x.Value].Single()
} ).Take(1).Dump();
var test2 = data.Select(x => new { Original = x,
  Match = forward[x.Index].Single()
} ).Take(1).Dump();
var test3 = data.Select(x => new { Original = x,
  Match = forward[backward[x.Value].Single().Index].Single()
} ).Take(1).Dump();

在原始代码中，

data.ToList() 生成了10,000个实例（10^4）。
data.Select( data.Single() ).ToList() 生成了1亿个实例（10^8）。
data.Select( data.Single( data.Single() ) ).ToList() 生成了1000万亿个实例（10^16）。

Single和First是不同的。如果遇到多个实例，Single会抛出异常。Single必须完全枚举其源以检查多个实例。

- Amy B

如果原始代码可以在几秒钟内生成10^16个任何东西的实例，我将把我的电脑卖给NASA。 - stovroz

好的，在 dump 之前的 take(1) 将其截断到 10^12。 - Amy B

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

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

- Reed Copsey · Accepted Answer

第一和第二个“测试”是相同的，都很慢。第三个则增加了另一个完整级别的缓慢。

这里的前两个LINQ语句具有二次性质。由于您的“Match”元素可能需要遍历整个“data”序列才能找到匹配项，因此随着您在范围内进行进度，该元素所需时间的长度将逐渐变长。例如，第10000个元素将强制引擎迭代原始序列的所有10000个元素以查找匹配项，使其成为O（N ^ 2）操作。

“test3”操作将这种痛苦提升到了一个全新的水平，因为它在第二个单操作中“平方”了O（N ^ 2）操作 - 在第一个操作之上强制执行了另一个二次操作 - 这将是大量操作。

每次使用匹配项进行data.Single（...）时，您正在执行一个O（N ^ 2）操作 - 第三个测试基本上变成了O（N ^ 4），这将慢得多。