LINQ: get the item with the highest of two / more values

Question

I have a list in which each element contains two values ​​(V1 and V2). I need the item with the highest V1 and highest V2 (priority V1).

I tried two approaches:

• OrderByDescending and ThenByDescending, then take the first element:

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

• Select the items with the largest V1, then select the first item with the largest V2 from this enumerated:

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

Both (in my use case) require a fair amount of time, and I am not satisfied with any of my solutions.

The list itself does not contain many elements, not more than 100. But there are many of them.

Is there any other, preferably more effective, solution than what I have already tried? Or do I need to rethink the whole architecture?

Edit: I forgot to mention that each element has more variables that can be used to select the highest value. Which one depends on the parameter. Therefore, pre-sorting using sorted collections does not provide any benefits.

Answer 1

Non-LINQ (for this example, I used the System.Drawing.Point structure):

  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 example:

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

Result:

Answer 2

You can use GroupBy and then order this V1 group by V2:

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

You should also keep the maximum value instead of using it as an expression in a query, otherwise it will always be evacuated. Thus, it is more efficient:

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

However, your first approach should work well, it is simple and effective:

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

So what is your performance issue? Maybe you are looking at the wrong place or calling this code too often. Consider keeping them already sorted, i.e. in a SortedList . I think SortedDictionary even more efficient in this case.

The general class SortedDictionary<TKey, TValue> is a binary search tree with the extraction of O (log n), where n is the number of elements in the Dictionary. In this respect, it is similar to the general class SortedList<TKey, TValue> . The two classes have similar object models, and both have O (log n) extraction. Where the two classes differ from each other, memory usage and insert and delete speeds are:

• SortedList<TKey, TValue> uses less memory than SortedDictionary<TKey, TValue> .
• SortedDictionary<TKey, TValue> has a faster insert and delete operation for unsorted data: O (log n) as opposed to O (n) for SortedList<TKey, TValue> .
• If the list is populated immediately from the sorted data, SortedList<TKey, TValue> faster than SortedDictionary<TKey, TValue> .

Here is a possible implementation using 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 is your class that contains V1 and V2 , I assumed that V1 is a primitive type of type double . GetMaxItem is a method that returns max-item.

---

If V1 and V2 can contain duplicates, you can try this approach, where the key of each SortedDictionary is the value of V1 , and the value is another SortedDictionary with the key of V2 and all related objects.

 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

As always, if you just need the maximum value, there is no need to do any sorting - Aggregate is 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; });