How to find the first element in a specific order using LINQ in O (n)?

Question

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

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) to sort the entire list when I really need the O (n) find-minimum operation.

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

Answer 1

Sorting is smart in that it will only execute ThenBy in the first group from OrderBy , but OrderBy still needs to sort all the elements before it can return the first group.

You can use the Aggregate method to get the first message according to the user mapping:

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

(Suppose you use LINQ for objects, of course.)

Answer 2

Is it in SQL or LINQ for objects? If this is the last, you probably want MinBy from MoreLINQ ; your written expression really sorts and then takes the first element.

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

EDIT: I see that your question has now changed; MoreLINQ does not support this comparison. In MiscUtil I have code to create an IComparer<T> connection - you can pass this to MinBy using the authentication function as a key selector. Feel free to add a function request for MinBy , which takes the source and IComparer<T> without the key selector :)

Answer 3

This is usually max or min (I don’t know what it is called in LinQ), given a certain key; sorting and getting the first or last seems redundant in any language or framework.