Buena manera de obtener la clave del valor más alto de un diccionario en C#

Después de leer varias sugerencias, decidí compararlas y compartir los resultados.

El código probado:

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

Los resultados:

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

Esto es solo para dar una idea de su rendimiento relativo.

Si su optimización 'foreach' es más rápida, pero LINQ es compacta y flexible.

Tal vez esto no es un buen uso para LINQ. Veo 2 escaneos completos del diccionario usando la solución LINQ (1 para obtener el máximo, luego otro para encontrar el kvp para devolver la cadena.

Podrías hacerlo en 1 pasada con un foreach "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;

Este es un método rápido. Es O (n), que es óptimo. El único problema que veo es que itera sobre el diccionario dos veces en lugar de solo una vez.

Puedes hacerlo iterando sobre el diccionario una vez usando MaxBy de morelinq.

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

Puede ordenar el diccionario usando OrderBy (para buscar el valor mínimo) o OrderByDescending (para el valor máximo) y luego obtener el primer elemento. También ayuda cuando necesita encontrar segundo elemento max / min

Obtener la clave del diccionario por valor máximo:

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

Obtener la clave del diccionario por valor mínimo:

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

Obtener la clave del diccionario por segundo valor máximo:

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

Obtener la clave del diccionario por segundo valor mínimo:

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

Qué tal hacerlo en paralelo usando Entrelazado.Cambio por la seguridad del hilo:) Tenga en cuenta que entrelazado.Exchange solo funcionará con un tipo de referencia.(es decir, un par de valor de estructura o clave (a menos que esté envuelto en una clase) no funcionará para mantener el valor máximo.

Aquí hay un ejemplo de mi propio código:

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

EDITAR (Código actualizado para evitar una posible condición de carrera anterior):

Aquí hay un patrón más robusto que también muestra la selección de un valor mínimo en paralelo. Me creo que esto aborda las preocupaciones mencionadas en los comentarios a continuación con respecto a una posible condición de carrera:

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

Método de extensión pequeña:

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

Entonces:

int keyOfMax = myDictionary.GetMaxValuePair().Key;

Creo que usar las bibliotecas LINQ estándar es lo más rápido que puedes hacer.