CODEWITHSUNDEEP
c#algorithmlinqbig-o
dance2die
dance2die

Reputation: 36895

Does LINQ First/FirstOrDefault iterate the whole enumerable?

Context:

I have a variable numbers of type IEnumerable<int>.
I want to check if numbers are in ascending order.

Algorithm

So I was getting the first element storing it in prev and wanted to check that against next subsequent numbers.

// numbers can contain "10, 20, 60, 50"
IEnumerable<int> numbers = TraverseInOrder(root);
int prev = numbers.FirstOrDefault();
foreach (var curr in numbers.Skip(1))
{
    if (curr < prev) return false;
    prev = curr;
}
return true;

Question I am setting the value of prev using numbers.FirstOrDefault() and also skipping one element(numbers.Skip(1)) in foreach to start from next element.

So for following codes, 

numbers.FirstOrDefault()
numbers.Skip(1)

Am I enumerating the numbers twice O(2N)? Meaning FirstOrDefault iterate the whole list?
-or-
Is it still O(N)? (O(1) constant time for FirstOrDefault + O(N) for Skip(1))

Upvotes: 2

Views: 3545

Answers (3)

Damien_The_Unbeliever
Damien_The_Unbeliever

Reputation: 239646

I would subtly change your technique so that you don't need to know (although other answers address what you've specifically asked for):

IEnumerable<int> numbers = TraverseInOrder(root);
int prev = 0;
bool first = true;
foreach (var curr in numbers)
{
    if (!first && curr < prev) return false;
    prev = curr;
    first = false;
}
return true;

Now you know (even without reading the documentation!) that this code will only iterate the enumerable once.

Upvotes: 2

Lucas Trzesniewski
Lucas Trzesniewski

Reputation: 51330

It's a bit subtle.

Enumerable.FirstOrDefault won't enumerate the whole sequence, as there's no point in doing that. Here's the implementation:

public static TSource FirstOrDefault<TSource>(this IEnumerable<TSource> source) {
    if (source == null) throw Error.ArgumentNull("source");
    IList<TSource> list = source as IList<TSource>;
    if (list != null) {
        if (list.Count > 0) return list[0];
    }
    else {
        using (IEnumerator<TSource> e = source.GetEnumerator()) {
            if (e.MoveNext()) return e.Current;
        }
    }
    return default(TSource);
}

You get an optimized version if the underlying sequence is an IList<T>, but otherwise an enumeration will be started.

Now imagine your IEnumerable<T> is actually an Entity Framework IQueryable<T> which represents a database query. What this means is that your code will still execute the query twice.

Better avoid enumerating IEnumerable<T> sequences multiple times as a rule of thumb. If you know that enumerating your sequence is cheap, you should use a more descriptive type, like ICollection<T> or IReadOnlyCollection<T>.

Upvotes: 6

peteski
peteski

Reputation: 1523

FirstOrDefault() isn't iterating the whole collection.

IEnumerable and order

Just do:

var moreNumbers = numbers.ToList();
// ...stuff with the list.

Upvotes: -1

Related Questions