CODEWITHSUNDEEP
c#linqcomplexity-theorysql-order-by
Avish
Avish

Reputation: 4626

How to find the first item according to a specific ordering using LINQ in O(n)?

Suppose I have a list of items (e.g., Posts) and I want to find the first item according to some non-trivial ordering (e.g., PublishDate and then CommentsCount as a tie-breaker). The natural way to do this with LINQ is like this:

posts.OrderBy(post => post.PublishDate).ThenBy(post => post.CommentsCount).First()

However, the micro-optimizer in me is worried that calling OrderBy actually costs me O(n*lgn) for sorting the entire list, when all I really need is an O(n) find-minimum operation.

So, is LINQ smart enough to return something from OrderBy() that knows how to optimize subsequent First() calls? If not, what's a better way to do this out-of-the-box? (I can always write my own FindMinimumItem implementation but that seems like overkill).

Upvotes: 8

Views: 372

Answers (3)

Guffa
Guffa

Reputation: 700562

The sorting is smart in the way that it will only do the ThenBy on the first group from the OrderBy, but the OrderBy still has to sort all items before it can return the first group.

You can use the Aggregate method to get the first post according to a custom comparison:

Post lowest =
  posts.Aggregate((Post)null,
    (x, y) =>
      x == null
      || y.PublishDate < x.PublishDate
      || (y.PublishDate == x.PublishDate && y.CommentsCount < x.CommentsCount)
      ? y : x
  );

(Assuming that you are using LINQ to Objects of course.)

Upvotes: 2

Jon Skeet
Jon Skeet

Reputation: 1502106

Is this in SQL or LINQ to Objects? If it's the latter, you probably want MinBy from MoreLINQ; your statement as written will indeed sort and then take the first item.

And yes, it's a shame that it doesn't include this (and similar things like DistinctBy) out of the box.

EDIT: I see your question has now changed; MoreLINQ doesn't support a compound comparison like that. In MiscUtil I have code to create a compound IComparer<T> - you could pass that into MinBy using the identity function as the key selector. Feel free to add a feature request for a MinBy which takes a source and an IComparer<T> without a key selector :)

Upvotes: 2

fortran
fortran

Reputation: 76077

Usually that is a max or min (I don't know the how is it called in LinQ), given a specific key; sorting and getting the first or last seems overkill in any language or framework.

Upvotes: 0

Related Questions