Bon moyen d'obtenir la clé de la plus haute valeur d'un dictionnaire en C #

Question

J'essaie d'obtenir la clé de la valeur maximale dans les Dictionary<string, double> results .

Voici ce que j'ai jusqu'à présent:

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

Cependant, comme cela semble un peu inefficace, je me demandais s'il existait un meilleur moyen de le faire.

Answer 1

Je pense que c'est le plus lisible O(n) réponse standard en utilisant LINQ.

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

edit: explication pour CoffeeAddict

Aggregate est le LINQ pour le nom communément appelé concept fonctionnel Fois

Il passe en boucle sur chaque élément de l'ensemble et s'applique quelle que soit la fonction que vous fournissez. Ici, la fonction que j'offre est une fonction de comparaison qui renvoie la plus grande valeur. Alors que le bouclage, Aggregate se souvient de la déclaration de résultat de la dernière fois qu'il appelle ma fonction. Il se nourrit de cela dans ma fonction de comparaison comme variable l. La variable r est l'élément actuellement sélectionné.

Ainsi, après agrégées en boucle sur l'ensemble de la série, elle renvoie le résultat de la dernière fois, il a appelé ma fonction de comparaison. Puis j'ai lu l' .Key membre de partir parce que je sais que c'est une entrée de dictionnaire

Voici une autre façon de voir les choses [je ne garantis pas que cette compile ;) ]

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

Answer 2

Après avoir lu diverses suggestions, j'ai décidé de les comparer et de partager les résultats.

Le code testé:

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

Les resultats:

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

Ceci est juste pour donner une idée de leur performance relative.

Si votre optimisation 'foreach' est la plus rapide, mais LINQ est compact et flexible.

Answer 3

Peut-être que ce n'est pas une bonne utilisation de LINQ. Je vois 2 analyses complètes du dictionnaire en utilisant la solution LINQ (1 pour obtenir le maximum, puis une autre pour trouver le kvp pour retourner la chaîne.

Vous pouvez le faire en 1 seul passage avec un for old "old fashioned":

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

C'est une méthode rapide. C'est O (n), ce qui est optimal. Le seul problème que je vois, c'est qu'il parcourt le dictionnaire deux fois au lieu d'une seule fois.

Vous pouvez le faire en parcourant le dictionnaire une fois en utilisant MaxBy de morelinq .

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

Answer 5

Pourquoi ne pas le faire en parallèle en utilisant Interlocked.Exchange pour la sécurité des threads :) Gardez à l’esprit que Interlocked.Exchange fonctionnera uniquement avec un type de référence (c’est-à-dire une paire clé / structure (sauf si elle est encapsulée dans une classe) ne fonctionnera pas. la valeur max.

Voici un exemple de mon propre code:

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

Jake Drew www.jakemdrew.com