LINQ: Get element with highest of two/multiple values

Question

I have a list where each element contains two values (V1 and V2). What I need is the element with the highest V1 and highest V2 (prioritizing V1).

I have tried two approaches:

1. OrderByDescending and ThenByDescending, then take the first element:

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

2. Select elements with biggest V1, then select the first element with the biggest V2 from this enumerable:

   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'm not satisfied with either of my solutions.

The list itself doesn't contain a lot of elements, not more than 100. But there are a lot of them.

Is there another, preferably more efficient, solution than what I've already tried? Or do I have to rethink the whole architecture?

Edit: I forgot to mention that there are more variables in each element which might be used to select the highest value. Which one is used depends on a parameter. So pre sorting using sorted collections doesn't net any benefits.

Answer 1

You can use GroupBy, 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 store the max value instead of using it as expression in the query, otherwise it will be evaulated always. So this 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 perform well, it's simple and efficient:

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

So what kind of performance issue do you have? Maybe you are loooking at the wrong place or you call this code too often. Consider to store them already sorted, f.e. in a SortedList. I think that a SortedDictionary is even more efficient in this case.

The SortedDictionary<TKey, TValue> generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this respect, it is similar to the SortedList<TKey, TValue> generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

• SortedList<TKey, TValue> uses less memory than SortedDictionary<TKey, TValue>.
• SortedDictionary<TKey, TValue> has faster insertion and removal operations for unsorted data: O(log n) as opposed to O(n) for SortedList<TKey, TValue>.
• If the list is populated all at once from sorted data, SortedList<TKey, TValue> is faster than SortedDictionary<TKey, TValue>.

Here is a possible implementation using a 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 have presumed that V1 is a primitive type like double. GetMaxItem is the method that returns the max-item.

---

If V1 and V2 can contain duplicates you could try this approach, where the key of each SortedDictionary is the V1 value and the value is another SortedDictionary with the V2-key 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 2

Non-LINQ (I took System.Drawing.Point struct for this example):

    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 3

As always, if you just want the maximum value, there's 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;
        });