在C#中获取Dictionary最高值的关键的好方法

Question

我正试图获得最大值的关键Dictionary<string, double> results.

这是我到目前为止:

double max = results.Max(kvp => kvp.Value);
return results.Where(kvp => kvp.Value == max).Select(kvp => kvp.Key).First();

但是,由于这似乎有点低效,我想知道是否有更好的方法来做到这一点.

Answer 1

我认为这是使用标准LINQ的最易读的O(n)答案.

var max = results.Aggregate((l, r) => l.Value > r.Value ? l : r).Key;

编辑:CoffeeAddict的解释

Aggregate是众所周知的功能概念Fold的LINQ名称

它遍历集合的每个元素并应用您提供的任何功能.这里,我提供的函数是一个返回更大值的比较函数.循环时,Aggregate记住上次调用函数时的返回结果.它将此作为变量提供给我的比较函数l.变量r是当前选定的元素.

因此,在聚合循环遍及整个集合之后,它将从最后一次调用我的比较函数时返回结果.然后我读了.Key它的成员,因为我知道它是一个字典条目

这是另一种看待它的方法[我不保证这个编译;)]

var l = results[0];
for(int i=1; i<results.Count(); ++i)
{
    var r = results[i];
    if(r.Value > l.Value)
        l = r;        
}
var max = l.Key;

Answer 2

在阅读了各种建议之后,我决定对它们进行基准测试并分享结果.

测试的代码:

// TEST 1

for (int i = 0; i < 999999; i++)
{
  KeyValuePair<GameMove, int> bestMove1 = possibleMoves.First();
  foreach (KeyValuePair<GameMove, int> move in possibleMoves)
  {
    if (move.Value > bestMove1.Value) bestMove1 = move;
  }
}

// TEST 2

for (int i = 0; i < 999999; i++)
{
  KeyValuePair<GameMove, int> bestMove2 = possibleMoves.Aggregate((a, b) => a.Value > b.Value ? a : b);
}

// TEST 3

for (int i = 0; i < 999999; i++)
{
  KeyValuePair<GameMove, int> bestMove3 = (from move in possibleMoves orderby move.Value descending select move).First();
}

// TEST 4

for (int i = 0; i < 999999; i++)
{
  KeyValuePair<GameMove, int> bestMove4 = possibleMoves.OrderByDescending(entry => entry.Value).First();
}

结果:

Average Seconds Test 1 = 2.6
Average Seconds Test 2 = 4.4
Average Seconds Test 3 = 11.2
Average Seconds Test 4 = 11.2

这只是为了了解它们的相对表现.

如果您的优化'foreach'是最快的,但LINQ是紧凑和灵活的.

Answer 3

也许这对LINQ来说不是很好用.我看到使用LINQ解决方案对字典进行了2次完整扫描(1获取最大值,然后另一次查找kvp以返回字符串.

你可以用一个"老式"的foreach一次性完成它:

KeyValuePair<string, double> max = new KeyValuePair<string, double>(); 
foreach (var kvp in results)
{
  if (kvp.Value > max.Value)
    max = kvp;
}
return max.Key;

Answer 4

您可以使用 OrderBy（用于查找最小值）或 OrderByDescending（用于最大值）对字典进行排序，然后获取第一个元素。当您需要找到第二个最大/最小元素时，它也有帮助

通过最大值获取字典键：

double min = results.OrderByDescending(x => x.Value).First().Key;

通过最小值获取字典键：

double min = results.OrderBy(x => x.Value).First().Key;

通过第二个最大值获取字典键：

double min = results.OrderByDescending(x => x.Value).Skip(1).First().Key;

通过第二个最小值获取字典键：

double min = results.OrderBy(x => x.Value).Skip(1).First().Key;

Answer 5

这是一种快速的方法.它是O(n),这是最佳的.我看到的唯一问题是它遍历字典两次而不是一次.

你可以做到这一点通过遍历字典一次MaxBy从morelinq.

results.MaxBy(kvp => kvp.Value).Key;