What is faster in finding an element with a property of maximum value

Question

Usually, to find an element with the max value property, I like it

var itemWithMaxPropValue = collection.OrderByDescending(x => x.Property).First(); 

But is it good in terms of performance? Maybe I should do something like this?

 var maxValOfProperty = collection.Max(x => x.Property); var itemWithMaxPropValue = collection .Where(x => x.Property == maxValueOfProperty).First(); 

Answer 1

Both solutions are not very effective. The first solution involves sorting the entire collection. The second solution requires collecting the collection twice. But you can find the item with the maximum property value at a time without sorting the collection. There is a MaxBy extension in the MoreLINQ library. Or you can implement the same functionality:

 public static TSource MaxBy<TSource, TProperty>(this IEnumerable<TSource> source, Func<TSource, TProperty> selector) { // check args using (var iterator = source.GetEnumerator()) { if (!iterator.MoveNext()) throw new InvalidOperationException(); var max = iterator.Current; var maxValue = selector(max); var comparer = Comparer<TProperty>.Default; while (iterator.MoveNext()) { var current = iterator.Current; var currentValue = selector(current); if (comparer.Compare(currentValue, maxValue) > 0) { max = current; maxValue = currentValue; } } return max; } } 

The use is simple:

 var itemWithMaxPropValue = collection.MaxBy(x => x.Property); 

Answer 2

Sort is N * log (N) , and Max has N only temporary complexity, so Max is faster. What you are looking for is an ArgMax function that Linq does not provide, so I suggest implementing it, for example:

  public static class EnumerableExtensions { public static T ArgMax<T, K>(this IEnumerable<T> source, Func<T, K> map, IComparer<K> comparer = null) { if (Object.ReferenceEquals(null, source)) throw new ArgumentNullException("source"); else if (Object.ReferenceEquals(null, map)) throw new ArgumentNullException("map"); T result = default(T); K maxKey = default(K); Boolean first = true; if (null == comparer) comparer = Comparer<K>.Default; foreach (var item in source) { K key = map(item); if (first || comparer.Compare(key, maxKey) > 0) { first = false; maxKey = key; result = item; } } if (!first) return result; else throw new ArgumentException("Can't compute ArgMax on empty sequence.", "source"); } } 

So you can just say

  var itemWithMaxPropValue = collection .ArgMax(x => x.Property); 

Answer 3

I will go with Max , as it is specially designed for this purpose. The sort to find the Max value seems too big.

Also, I would not use Where to find max, but Single - since we only need the Single value here.

 var maxValOfProperty = collection.Max(x => x.Property); var itemWithMaxPropValue = collection .Single(x => x.Property == maxValueOfProperty); 

Or, alternatively, using First (if the collection contains duplicates of the maximum value)

 var maxValOfProperty = collection.Max(x => x.Property); var itemWithMaxPropValue = collection .First(x => x.Property == maxValueOfProperty); 

Or, using MoreLINQ (as suggested by Kathi ), you can do this with MaxBy :

 var itemWithMaxPropValue = collection.MaxBy(x => x.Property); 

Mark the message , reply to Jon Skeet .

Answer 4

The maximum element in a given function can also be found using the following two functions.

 static class Tools { public static T ArgMax<T, R>(T t1, T t2, Func<T, R> f) where R : IComparable<R> { return f(t1).CompareTo(f(t2)) > 0 ? t1 : t2; } public static T ArgMax<T, R>(this IEnumerable<T> Seq, Func<T, R> f) where R : IComparable<R> { return Seq.Aggregate((t1, t2) => ArgMax<T, R>(t1, t2, f)); } } 

The solution above works as follows; first overload ArgMax takes a comparator as an argument that maps both instances of T to a type that implements comparability; returns maximum. The second overload takes the sequence as an argument and simply aggregates the first function. This is the most general, fundamental, reuse and structurally sound formulation for the maximum search that I know of; minimum search can be implemented in a similar way by changing the comparison in the first function.