c# - LINQ:获取具有两个/多个值中最高值的元素

Question

我有一个列表，其中每个元素包含两个值(V1 和 V2)。我需要的是具有最高 V1 和最高 V2(优先 V1)的元素。

我尝试了两种方法:

1. OrderByDescending 和 ThenByDescending，然后取第一个元素:

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

2. 选择具有最大 V1 的元素，然后从此枚举中选择具有最大 V2 的第一个元素:

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

两者(在我的用例中)都需要相当多的时间，而且我对我的任何一个解决方案都不满意。

列表本身包含的元素并不多，不超过100个。但是有很多。

有没有比我已经尝试过的更有效的解决方案？还是我必须重新考虑整个架构？

编辑:我忘了提到每个元素中有更多变量可用于选择最高值。使用哪一个取决于参数。因此，使用已排序集合进行预排序不会带来任何好处。

Answer 1

您可以使用 GroupBy ，然后按 V2 对这个 V1 组进行排序:

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

您还应该存储最大值而不是将其用作查询中的表达式，否则它将始终被计算。所以这样效率更高:

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

但是，您的第一种方法应该表现良好，它简单高效:

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

那么您遇到了什么样的性能问题？也许您看错了地方，或者您过于频繁地调用此代码。考虑存储它们已经排序，例如。在 SortedList .我认为 SortedDictionary 是偶数 more efficient在这种情况下。

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>使用的内存少于 SortedDictionary<TKey, TValue> .
• SortedDictionary<TKey, TValue>对于未排序的数据具有更快的插入和删除操作:O(log n) 而不是 SortedList<TKey, TValue> 的 O(n) .
• 如果列表是从排序后的数据一次性填充的，SortedList<TKey, TValue>比 SortedDictionary<TKey, TValue> 快.

这是使用 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是你的类包含 V1和 V2 , 我假设 V1是原始类型，如 double . GetMaxItem是返回最大项的方法。

---

如果V1 和 V2可以包含重复项，您可以尝试这种方法，其中每个 SortedDictionary 的键是V1 value 和 value 是另一个 SortedDictionary与 V2 -key 和所有相关对象。

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