Does LINQ try to solve things in one pass?

Question

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?

Say we have a state exam and students are asked to solve a simple algorithmic task that can be solved via C# LINQ in one nice, simple query. Yet if they can not prove in runs in one pass it will be considered unoptimal solution and students will get bad grades. — Rella, Aug 29 '14 at 17:31
Note that there is a similar question re Linq2SQL: will the resulting query be performed using a single `SELECT` statement? For simple queries like your example, if they can be converted to an SQL query the answer is, yes. But some [complex](http://stackoverflow.com/q/22816591/256431) [queries](http://stackoverflow.com/q/12264751/256431) do not do this, and I don't know if any guarantee is given. — Mark Hurd, Aug 30 '14 at 03:27

Servy · Answer 1 · 2014-08-29T17:37:33.800

list would only be iterated once in that code, not 3 times.

Of course, if you want to test if any arbitrary query iterates the source multiple times it's easy enough to test experimentally, just create an IEnumerable that throws an exception when you attempt to iterate it multiple times:

public static IEnumerable<T> ThereCanBeOnlyOne<T>(this IEnumerable<T> source)
{
    return new SingleEnumerable<T>(source);
}

private class SingleEnumerable<T> : IEnumerable<T>
{
    private bool hasRun = false;
    private IEnumerable<T> wrapped;
    public SingleEnumerable(IEnumerable<T> wrapped)
    {
        this.wrapped = wrapped;
    }
    public IEnumerator<T> GetEnumerator()
    {
        if (hasRun)
            throw new InvalidOperationException(
                "Sequence cannot be enumerated multilpe times");
        else
        {
            hasRun = true;
            return wrapped.GetEnumerator();
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Now you can just write:

list.ThereCanBeOnlyOne()
    .Where(p=>p.Number > n)
    .Select(p=> p.Name)
    .Where(n=> n.StartsWith(a))
    .ToList();

If the code throws an exception, you tried to iterate the underlying list multiple times. If not, you didn't.

score 6 · Accepted Answer · answered Aug 29 '14 at 17:32

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.

Does LINQ try to solve things in one pass?

2 Answers2