CODEWITHSUNDEEP
linqlinq-extensions
Martin
Martin

Reputation: 2971

Will First() perform the OrderBy()?

Is there any difference in (asymptotic) performance between

var a = Orders.OrderBy(order => order.Date).First()

and

var y = Orders.Where(order => order.Date == Orders.Min(x => x.Date)).ToList();

i.e. will First() perform the OrderBy()? I'm guessing no. MSDN says enumerating the collection via foreach och GetEnumerator does but the phrasing does not exclude other extensions.

Upvotes: 12

Views: 12834

Answers (4)

Eamon Nerbonne
Eamon Nerbonne

Reputation: 48066

A few things:

  • OrderBy() orders from small to large, so your two alternatives return different elements
  • Where() is typically lazy, so your second expression doesn't actually do any computation at all - not until used.
  • In principle, the behavior in question depends on the query provider. For example, you might indeed expect the sql-server linq query provider to deal with this differently than the IEnumerable query provider. A query provider might choose to have the return value of "OrderBy" be sufficiently specialized such that calling First() on it recognizes (either at compile or run-time) that it's running on an ordered enumerable and instead of sorting, opts to return the (first) minimum element.
  • Specifically for the IEnumerable<T> provider, OrderBy happens to return an enumerable that fully buffers and sorts the input each time the first element is retrieved - so, in the common basic Linq-to-objects case, OrderBy().First() is comparable to OrderBy().ToArray().

Remeber that linq is just a bunch of function names - each provider may choose to implement these differently, so the above only holds for the System.Linq IEnumerable query provider, and not necessarily others.

Upvotes: 11

TomTom
TomTom

Reputation: 62101

It does not. THAT BEING SAID - naturally the orderby will execute the moment someone tries to actually GET the first element.

But as you said, the conditions may be further defined. As such, no - it does not execute at that moment.

Upvotes: 0

Guffa
Guffa

Reputation: 700362

The First method will perform the OrderBy (that is, given that the First method is executed of course). When the First method pulls the first item from the result of the OrderBy, it will have to sort all the items to find out which one is the first one.

Depending on where and how the query is run (i.e. if the query engine can't optimise around it), the second query can perform quite badly. If Orders.Max is evaluated once for each item in Orders, it becomes an O(n*n) operation, which is pretty bad.

There is a functional difference also, the second query can return more than one item if there are duplicate dates.

Upvotes: 6

Klaus Byskov Pedersen
Klaus Byskov Pedersen

Reputation: 120937

First will return the first entry of the IEnumerable passed to it. Since the IEnumerable passed to First is the result of OrderBy your question can be rephrased to "Does OrderBy work", and, yes it does.

First cannot defer the execution of OrderBy because it returns the result right away. For example:

        var numbers = new int[] { 9, 3, 4, 6, 7 };

        var num = numbers.First();
        Console.WriteLine(num);

        num = numbers.OrderBy(i => i).First();
        Console.WriteLine(num);

        Console.ReadLine();

Upvotes: 6

Related Questions