在C语言中获得字典最高值的键的好方法#

我认为这是最可读的O(N)答案使用标准的LINQ。

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

编辑:咖啡豆说明

Aggregate 是常见功能概念的LINQ名称 Fold

它在集合的每个元素上循环,并应用您提供的任何函数。 这里,我提供的函数是一个比较函数,它返回更大的值。 循环时, 骨料 记住上次调用函数时返回的结果。它将这个作为变量输入到比较函数中 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;

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

测试代码:

// 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是紧凑和灵活的。

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

你可以用“老式”前臂一次完成:

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

这是一种快速的方法。它是O(n),这是最优的。我看到的唯一问题是它对字典进行两次迭代而不是一次。

您可以使用 MaxBy 从 morelinq .

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

您可以使用orderby(对于find min value)或orderbyDescending(对于max value)对字典进行排序,然后获取第一个元素。当您需要查找第二个max/min元素时,它也会有所帮助。

按最大值获取字典键:

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;

小扩展方法:

public static KeyValuePair<K, V> GetMaxValuePair<K,V>(this Dictionary<K, V> source)
    where V : IComparable
{
    KeyValuePair<K, V> maxPair = source.First();
    foreach (KeyValuePair<K, V> pair in source)
    {
        if (pair.Value.CompareTo(maxPair.Value) > 0)
            maxPair = pair;
    }
    return maxPair;
}

然后:

int keyOfMax = myDictionary.GetMaxValuePair().Key;

如何使用interlocked.exchange进行并行操作以确保线程安全:)请记住,interlocked.exchange只能与引用类型一起工作。(即,结构或键值对(除非包装在类中)将无法保存最大值。

下面是我自己代码中的一个示例:

//Parallel O(n) solution for finding max kvp in a dictionary...
ClassificationResult maxValue = new ClassificationResult(-1,-1,double.MinValue);
Parallel.ForEach(pTotals, pTotal =>
{
    if(pTotal.Value > maxValue.score)
    {
        Interlocked.Exchange(ref maxValue, new                
            ClassificationResult(mhSet.sequenceId,pTotal.Key,pTotal.Value)); 
    }
});

编辑(更新代码以避免上述可能的竞争条件):

这里有一个更健壮的模式,它也显示了并行选择一个最小值。我认为这解决了以下评论中提到的关于可能的比赛条件的问题:

int minVal = int.MaxValue;
Parallel.ForEach(dictionary.Values, curVal =>
{
  int oldVal = Volatile.Read(ref minVal);
  //val can equal anything but the oldVal
  int val = ~oldVal;

  //Keep trying the atomic update until we are sure that either:
  //1. CompareExchange successfully changed the value.
  //2. Another thread has updated minVal with a smaller number than curVal.
  //   (in the case of #2, the update is no longer needed)
  while (oldval > curVal && oldval != val)
  {
    val = oldval;
    oldval = Interlocked.CompareExchange(ref minVal, curVal, oldval);
  }
});

我认为使用标准的LINQ库是最快的。