好的方法来获得在C#中的字典的最高价值的关键

我试图得到在Dictionary<string, double> results的最大值的关键。

这是我迄今为止:

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

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

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

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

编辑:CoffeeAddict的解释

Aggregate是通常已知的function概念折叠的LINQ名称

它遍历该集合的每个元素,并应用您提供的任何函数。 在这里,我提供的函数是一个比较函数,返回更大的值。 在循环时, Aggregate记住上次调用我的函数的返回结果。 它把它作为variableslinput到我的比较函数中。 variablesr是当前选定的元素。

所以在聚合遍历整个集合之后,它返回最后一次调用我的比较函数的结果。 然后我从中读取.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; 

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

testing的代码:

 // 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 

这只是给他们的相对performance的一个想法。

如果您的优化“foreach”是最快的,但LINQ是紧凑和灵活的。

也许这对LINQ来说并不好用。 我看到使用LINQ解决scheme的字典的2完整扫描(1获得最大值,然后另一个findkvp返回string。

你可以通过一个“老式”的foreach来做到这一点:

KeyValuePair<string, double> max = new KeyValuePair<string, double>(); foreach (var kvp in results) { if (kvp.Value > max.Value) max = kvp; } return max.Key;
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),这是最佳的。 我看到的唯一问题是它遍历字典两次而不是一次。

你可以通过使用来自morelinq的 MaxBy来迭代字典。

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

您可以使用OrderBy(查找最小值)或OrderByDescending(最大值)对字典进行sorting,然后获取第一个元素。 当你需要find第二个最大/最小元素时,它也有帮助

通过最大值获取字典密钥:

 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; 

如何做并行使用Interlocked.Exchange线程安全:)请记住,Interlocked.Exchange只能使用引用types(即一个结构或键值对(除非包装在类中)将无法保持最大值。

以下是我自己的代码示例:

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

编辑(更新的代码,以避免可能的比赛情况):

这是一个更强大的模式,也显示了并行select最小值。 我认为这解决了下面评论中提到的关于可能的竞争条件的担忧:

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

小扩展方法:

 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;

我想使用标准的LINQ库,这是尽可能快的。