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）的事實被提及 - 這更可信。在這個帖子中給出的是O（m^2）的循環中使用Concat - 我不認爲這是一個特別令人震驚的發現，因爲你會期望許多調用會增加複雜度！

Richard的後續行動是建議推遲Concat操作，直到需要時爲止，通過存儲迭代器列表，然後從第一個開始移動，然後在耗盡時移動到下一個，這是非常有道理的 - 但是，對於'光線使用'而言，Concat不會有問題。