Concat性能

Question

我在msdn上读了一篇关于迭代器的blog post，里面谈到了Concat如何具有O(m^2)性能，其中m是第一个IEnumerable的长度。其中一个评论是richard_deeming在第二页上提供的一些示例代码，他说这些代码要快得多。我真的不明白为什么它会更快，我希望有人能给我解释一下。

谢谢。

Answer 1

他只是简单地说，不是使用Concat来创建迭代器，这实际上等同于在上面创建迭代器：

...(((a+b)+c)+d)...

这是由以下原因引起的：

for (int i = 0; i < length; ++i)
    ones = ones.Concat(list); 

创建所需的迭代器列表，并返回之前创建的每个迭代器。

这样，您就不会在第一个元素集合中出现大量堆叠的迭代器。

此外，值得一提的是，关于O(m^2)的说法并不“真正正确”。在这种情况下是正确的，但这就像在计算(((a+b)+c)+d)...情况时说+是O(m^2)一样。正是特定的使用模式使其成为O(m^2)。

Answer 2

我不认为博客文章是说Concat是O(m^2)，至少它不应该是这样的--在某一点上提到了Concat是O(m+n) --这是更可信的。正如post中给出的在循环中使用Concat是O(m^2) -我不认为这是一个特别令人震惊的发现，因为你会期望许多调用增加复杂性！

Richard的后续工作是建议将Concat操作推迟到需要的时候，通过存储迭代器列表，然后从第一个迭代器开始遍历每个迭代器，然后在用完后继续执行下一个操作，这很有意义-但是，对于“轻度使用”Concat as-is是很好的。