space complexity of a simple linq(to objects) query

Question

I have;

var maxVal = l.TakeWhile(x=>x < val).Where(x=>Matches(x)).Max();

How much space does this need ? Does linq build up a list of the above Where() condition, or is Max() just iterating through the IEnumerable keeping track of what is the current Max() ?

And where can I find more info about this, besides asking on SO f

Answer 1

I have verified with Reflector that each of Enumerable.TakeWhile, Enumerable.Where and Enumerable.Max run in constant space. Consequently, this entire query should run in constant space. Not surprising, considering TakeWhile and Where are speced to use deferred execution + streaming. Max does not use deferred execution, but only needs to store 'max so far' and the enumerator on the source enumerable.

Answer 2

According to the Reflector Max() method iterates through the enumerable.

And where can I find more info about this, besides asking on SO f

You can use Reflector to look at the implementation of any .NET assembly.

Answer 3

Reflector is your friend.

In particular, you can take a look at Linq to Objects extension methods in the Enumerable class in System.Linq.

The above are using iterations, so they use the whatever space the enumerators takes up - usually O(1). Max() is O(1) space.

However, keep in mind that nothing stops a developer from writing an enumerator that takes up more than constant space. E.g. traversing a tree may require O(log n) space. This is the case e.g. for SortedDictionary<K,V> and SortedSet<K,V>.

So it partially depends on what l is in your code.

Answer 4

The only thing offered by Enumerable that I've found doesn't run in constant space is ToList(), for obvious reasons.

With some enumerations, this is inefficient, in that you already have a space complexity above constant (typically O(n) as you are storing the items) and that the collection in question offers a mechanism with lower time complexity. If you are creating such a collection yourself it makes sense to offer your own versions of the extensions offered by Enumerable. For example, if you have a collection that is inherently sorted you should be able to offer Min() and Max() in better than O(n) complexity (whether it is O(1), O(ln) or something else would depend on what way that sorting was kept). Since instance methods override extension methods (when called on an expression of the object type rather than the instance type) then with no difference to the coder using your object, you will offer better efficiency.