cosa è più veloce nel trovare elemento con proprietà di valore massimo

Question

Comunemente, per trovare elemento con la proprietà del valore massimo mi piace questo

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

ma è buon modo dal punto di vista delle prestazioni? Forse dovrei fare qualcosa del genere?

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

Answer 1

Entrambe le soluzioni non sono molto efficienti. La prima soluzione consiste nell'ordinare l'intera collezione. La seconda soluzione richiede due volte di attraversare la raccolta. Ma puoi trovare l'oggetto con il valore massimo della proprietà in una volta senza raccolta di ordinamento. C'è l'estensione MaxBy nella libreria MoreLINQ. Oppure si può implementare stessa funzionalità:

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; 
    } 
} 

L'uso è semplice:

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

Answer 2

andrò con Max dal momento che è specificamente progettato per questo scopo. Ordinare per trovare il valore Max sembra essere troppo.

Inoltre, non vorrei usare Where per trovare il massimo, ma Single - dato quello che ci serve qui non è che un valore Single.

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

Oppure, in alternativa utilizzando First (se la raccolta contiene i duplicati del valore massimo)

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

Oppure, utilizzando MoreLINQ (come suggerito da Kathi), si potrebbe fare con MaxBy:

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

Controllare questo post, in risposta Jon Skeet.

Answer 3

L'elemento massimo con una funzione specifica può essere trovato anche mediante le due funzioni seguenti.

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)); 
    } 
} 

La soluzione sopra funziona come segue; il primo sovraccarico di ArgMax prende come argomento un comparatore che associa entrambe le istanze di T a un tipo che implementa la comparabilità; un massimo di questi viene restituito. Il secondo overload prende una sequenza come argomento e semplicemente aggrega la prima funzione. Questa è la formulazione più generica, riutilizzabile dal framework e strutturalmente solida per la ricerca massima di cui sono a conoscenza; la ricerca del minimo può essere implementata nello stesso modo modificando il confronto nella prima funzione.

Answer 4

Sorting è N * log (N) mentre Max ha N solo la complessità del tempo, in modo da Max è più veloce. Quello che stai cercando è ArgMax funzione che Linq non fornisce, quindi suggerisco attuazione, ad esempio:

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"); 
    } 
    } 

Così si può mettere semplicemente

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