Concat performance

I was reading a blog post on msdn about iterators which talks about about how Concat has O(m^2开发者_StackOverflow) performance where m is the length of the first IEnumerable. One of the comments, by richard_deeming on the second page, provides some sample code which he says is much faster. I don't really understand why it's faster and was hoping someone could explain it to me.

Thanks.

---

He's simply saying that instead of using Concat to create an iterator which is actually equivalent to creating an iterator over:

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

which is caused by:

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

create a list of iterators you need and return each of those iterators you created previously.

This way you're not ending up with a lot of stacked iterators in the first collection of elements.

Also it's worth mentioning that the claim about O(m^2) is not "really right". It's true in this specific case, but this is like saying + is O(m^2) when you're calculating (((a+b)+c)+d)... case. It's the specific usage pattern that makes it O(m^2).

---

I don't think the blog post is saying that Concat is O(m^2), at least, it shouldn't be - at one point the fact that Concat is O(m+n) is mentioned - and this is much more believeable. It's the use of Concat in a loop as given on that post that is O(m^2) - and I don't think that this is a particularly shocking finding as you'd expect many calls to multiply up the complexity!

Richard's follow-up is suggesting deferring the Concat operations until they're needed, by storing a list of iterators, and then moving through each of these starting from the first, then when that's exhausted, moving on to the next, which makes perfect sense - however, for 'light usage' Concat as-is would be fine.