What is faster in finding element with property of maximum value

Question

Commonly, to find element with property of max value I do like this

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

But is it good way from performance point of view? 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

Sorting is N * log (N) while Max has N only time complexity, so Max is faster. What you're looking for is ArgMax function which Linq doesn't provide, so I suggest implementing it, e.g:

  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 put it simply

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

Answer 2

Both solutions are not very efficient. First solution involves sorting whole collection. Second solution requires traversing collection two times. But you can find item with max property value in one go without sorting collection. There is MaxBy extension in MoreLINQ library. Or you can implement 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;
    }
}

Usage is simple:

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

Answer 3

I will go with Max since it is specifically designed for that purpose. Sorting to find Max value seems to be too much.

Also, I wouldn't use Where for finding the max, but Single - since what we need here is but a Single value.

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 max value)

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

Or, using MoreLINQ (as suggested by Kathi), you could do it with MaxBy:

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

Check this post, on answer by Jon Skeet.

Answer 4

The maximum element under some specified function can also be found by means of 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; the first overload of ArgMax takes a comparator as an argument which maps both instances of T to a type which implements comparability; a maximum of these is returned. The second overload takes a sequence as an argument and simply aggregates the first function. This is the most generic, framework-reusing and structurally sound formulation for maximum search I am aware of; searching the minimum can be implemented in the same way by changing the comparison in the first function.

Answer 5

I'm a little bit surprised that no one mentioned the Aggregate method. Aggregate lets you iterate a collection and return an aggregate value.

An ArgMax function can be implemented in this way:

var maxItem = collection.Aggregate((max, next) => next.Property.CompareTo(max.Property) > 0 ? next : max);

This function will iterate all over the collection and aggregate the item that has the largest Property. This implementation is O(N) which is good.

Please note that the Property getter (or the compared value in general) is called 2N times so don't do this when the value computation is heavy. You can avoid this with another iteration over the array or use the @Sergey Berezovskiy answer which suits all the cases.

But if you need it for simple values, this is a one-line efficient solution