Sep
12
Why does the last line hang?
IEnumerable<int> empty = Enumerable.Empty<int>(); for (int i = 0; i < 40; i++) { empty = empty.Concat(empty); } int[] emptyArray = empty.ToArray();
Answer in the comments section. 
For a slightly harder challenge, check out the next puzzle.
Tags: LINQ
Feed
Twitter
Subscribe by email
Hi Igor!
Concat() execution is deferred, so each call to Concat() returns a decorated IEnumerable instance; by Concat()ing the collection to itself 40 times, you end up with a tree of (I believe) 40! unique collection instances that must be traversed during the call to ToArray().
jimbo
Actually it doesn’t hang on the last line. The problem is with the Concat operation. If you decrease the for-loop iteration to something smaller (like 10) the code snippet will execute and emptyArray will be the equivalent to Enumerable.Empty or {int[0]}. The Concat operations slows things down exponentially and in the end you’ll end up with an OutOfMemoryException. Why ? I don’t have a clue…yet
Instead of
empty = empty.Concat(empty)
just have
empty.Concat(empty)
it will run fine. Still trying to figure out why…
Got it; I think…
Enumerable.Concat has a parameter (first) which is the first sequence to concatinate which is itself. Because of this you get massive recursion that’s why it appears to hang. Am I correct ?
It doesn’t hang; it just takes an unreasonably long time.
You end up with a “tree” with only 41 distinct node objects (the original empty Enumerable, plus 40 Concat decorators), which is why there’s no risk of an OutOfMemoryException. But the second node down serves double duty — it’s both the left and the right child of the top node. The third node down serves quadruple duty, the fourth 8x, the fifth 16x, etc.
ToArray() has to traverse the entire tree, and it’s not visiting 40 objects — it’s visiting all 2,199,023,255,551 nodes in the tree (2^41 – 1). Even a “for” loop with that many iterations will take longer than most of us are willing to wait.
It’s not the 40 layers of decorators that kill you, it’s the fact that every single layer (except the first) is visited more than once, which takes you into exponential time.
Those are some good answers. Joe, yours is particularly accurate.
Now, what about the other puzzle? Still no answer there.
[…] you enjoyed this article, check out these LINQ puzzles. Also, read my article on the 7 tricks to simplify your programs with […]