LINQ: Ottieni elemento con il più alto di due/più valori

Question

Ho una lista in cui ogni elemento contiene due valori (V1 e V2). Quello di cui ho bisogno è l'elemento con V1 e V2 più alti (priorità per V1).

ho provato due approcci:

1. OrderByDescending e ThenByDescending, poi prendere il primo elemento:

   list.OrderByDescending(e => e.V1).ThenByDescending(e => e.V2).First(); 
   

2. Selezionare gli elementi con grande V1, quindi selezionare il primo elemento con il più grande V2 da questo enumerabile:

   var maxV1 = l.Where(e => e.V1 == l.Max(e => e.V1)); 
   maxV1.First(e => e.V2 == maxV1.Max(e1 => e1.V2)); 
   

Entrambi (nel mio caso d'uso) richiedono una buona quantità di tempo e non sono soddisfatto di nessuna delle mie soluzioni.

La lista stessa non contiene molti elementi, non più di 100. Ma ce ne sono molti.

Esiste un'altra soluzione, preferibilmente più efficiente, rispetto a quello che ho già provato? O devo ripensare l'intera architettura?

Modifica: Ho dimenticato di menzionare che ci sono più variabili in ogni elemento che potrebbero essere utilizzate per selezionare il valore più alto. Quale viene utilizzato dipende da un parametro. Pertanto, l'ordinamento preliminare utilizzando raccolte ordinate non comporta alcun vantaggio.

Answer 1

non LINQ (ho preso System.Drawing.Point struct per questo esempio): Esempio

static Point GetHighestXY(Point[] points) 
    { 
     Point max = default(Point); 
     for (int i = 0; i < points.Length; i++) 
     { 
      if (points[i].X < max.X) continue; 
      if (points[i].X > max.X) { max = points[i]; } 
      else { if (points[i].Y > max.Y) max = points[i]; } 
     } 
     return max; 
    } 

Usage:

 Point[] pts = 
     { 
      new Point(55, 8), 
      new Point(55, 10), 
      new Point(10, 10), 
      new Point(22, 11), 
      new Point(16, 33),     
      new Point(4, 104) 
     }; 

     Point max = GetHighestXY(pts); 

     Console.WriteLine("X : {0} Y : {1} ", max.X, max.Y);  

risultati:

Answer 2

È possibile utilizzare GroupBy, quindi ordinare questo V1-V2 da gruppo:

var highestItemByV1V2 = list.GroupBy(x => x.V1) 
    .OrderByDescending(g => g.Key) 
    .Select(g => g.OrderByDescending(x => x.V2).First()) 
    .First(); 

Si dovrebbe anche memorizzare il valore massimo invece di usarlo come espressione nella query, altrimenti sarà evaulated sempre. Quindi questo è più efficiente:

var highestV1 = list.Max(x => x.V1); 
var maxObj = list.Where(x => x.V1 == highestV1).OrderByDescending(x => x.V2).First(); 

Tuttavia, il vostro primo approccio dovrebbe funzionare bene, è semplice ed efficace:

list.OrderByDescending(e => e.V1).ThenByDescending(e => e.V2).First(); 

Quindi, che tipo di problema di prestazioni avete? Forse stai sbagliando nel posto sbagliato o chiami questo codice troppo spesso. Considera di memorizzarli già ordinati, per esempio in un SortedList. Penso che uno SortedDictionary sia anche more efficient in questo caso.

La classe generica SortedDictionary<TKey, TValue> è un binario di ricerca albero con O (log n) di recupero, dove n è il numero di elementi nel dizionario . A tale proposito, è simile alla classe generica SortedList<TKey, TValue>. Le due classi hanno modelli di oggetti simili, ed entrambi hanno O (log n) recupero. Dove i due classi differiscono è in uso della memoria e la velocità di inserimento e rimozione:

• SortedList<TKey, TValue> utilizza meno memoria SortedDictionary<TKey, TValue>.
• SortedDictionary<TKey, TValue> ha operazioni di inserimento e rimozione più veloci per dati non ordinati: O (log n) in contrapposizione a O (n) per SortedList<TKey, TValue>.
• Se l'elenco viene popolato tutti insieme da dati ordinati, SortedList<TKey, TValue> è più veloce di SortedDictionary<TKey, TValue>.

Ecco una possibile implementazione utilizzando un SortedDictionary<double, SortedSet<Obj>>:

SortedDictionary<double, SortedSet<Obj>> sortedLookup = 
    new SortedDictionary<double, SortedSet<Obj>>(); // key is V1 and value all items with that value 

internal class ObjV2Comparer : IComparer<Obj> 
{ 
    public int Compare(Obj x, Obj y) 
    { 
     return x.V2.CompareTo(y.V2); 
    } 
} 

private static readonly ObjV2Comparer V2Comparer = new ObjV2Comparer(); 

public void Add(Obj obj) 
{ 
    SortedSet<Obj> set; 
    bool exists = sortedLookup.TryGetValue(obj.V1, out set); 
    if(!exists) 
     set = new SortedSet<Obj>(V2Comparer); 
    set.Add(obj); 
    sortedLookup[obj.V1] = set; 
} 
public Obj GetMaxItem() 
{ 
    if (sortedLookup.Count == 0) return null; 
    Obj maxV1Item = sortedLookup.Last().Value.Last(); 
    return maxV1Item; 
} 

Obj è la classe che contiene V1 e V2, ho presunto che V1 è un tipo primitivo come double. GetMaxItem è il metodo che restituisce il max-item.

---

Se V1eV2 può contenere duplicati si potrebbe provare questo approccio, in cui la chiave di ogni SortedDictionary è il valore V1 e il valore è un altro SortedDictionary con il tasto V2 e tutti gli oggetti correlati.

SortedDictionary<double, SortedDictionary<double, List<Obj>>> sortedLookup = 
    new SortedDictionary<double, SortedDictionary<double, List<Obj>>>(); 

public void Add(Obj obj) 
{ 
    SortedDictionary<double, List<Obj>> value; 
    bool exists = sortedLookup.TryGetValue(obj.V1, out value); 
    if(!exists) 
    { 
     value = new SortedDictionary<double, List<Obj>>(){{obj.V2, new List<Obj>{obj}}}; 
     sortedLookup.Add(obj.V1, value); 
    } 
    else 
    { 
     List<Obj> list; 
     exists = value.TryGetValue(obj.V2, out list); 
     if (!exists) 
      list = new List<Obj>(); 
     list.Add(obj); 
     value[obj.V2] = list; 
     sortedLookup[obj.V1] = value; 
    } 
} 

public Obj GetMaxItem() 
{ 
    if (sortedLookup.Count == 0) return null; 
    Obj maxV1Item = sortedLookup.Last().Value.Last().Value.Last(); 
    return maxV1Item; 
} 

Answer 3

Come sempre, se vuoi solo il valore massimo, non c'è bisogno di fare alcun ordinamento - Aggregate è O (n):

var maxByBoth = items.Aggregate(
    (bestSoFar, current) => 
     { 
      if (current.V1 > bestSoFar.V1) 
       return current; 
      if (current.V1 == bestSoFar.V1 && current.V2 > bestSoFar.V2) 
       return current; 
      return bestSoFar; 
     });