Does LINQ try to solve things in one pass?

Say we have list.Where(p=>p.Number > n).Select(p=> p.Name).Where(n=> n.StartsWith(a)).ToList(); will this be ran one pass algorithm or it will be 3 passes?

Jon Skeet
people
quotationmark

It will build up the list in one pass, due to the way that LINQ streams the data.

For example, take this:

var query = list.Where(p => p.Number > n);

That in itself doesn't look at any of the elements of the list. Instead, it remembers the list you're looking at, and when you start iterating over query, each time you ask for the next element, it will check the elements of the list in turn until it finds a match - then stop. For example:

using (var iterator = query.GetEnumerator())
{
    iterator.MoveNext(); // This will look for the first match
    Console.WriteLine(iterator.Current);

    iterator.MoveNext(); // This will continue from just after the first match
}

Each of the operations works that way - so by the time you've got:

var query = list.Where(...)
                .Select(...)
                .Where(...);

... when you ask for the first item within query, it will chain back up (so the last Where will ask the result of Select, which will ask the result of the first Where, which will ask the list) and keep going until it's got a result. Then when you ask for the next item, that will ask the result of Select for the next item, etc.

ToList builds up a List<T> from all the items in its source, immediately - it's eager in that sense (rather than the other operators here which are lazy). But the original list itself will still only be iterated over once.

For a lot more detail on how LINQ to Objects works - including a sample implementation - you might want to read my Edulinq blog series.

people

See more on this question at Stackoverflow