Хороший способ получить ключ самого высокого значения словаря в C # - PullRequest
Новая
       6

Хороший способ получить ключ самого высокого значения словаря в C #

67 голосов
/ 10 мая 2010

Я пытаюсь получить ключ максимального значения в Dictionary<string, double> results.

Это то, что я имею до сих пор: 

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

Однако, поскольку это кажется немного неэффективным, мне было интересно, есть ли лучший способ сделать это.

Ответы [ 8 ]

123 голосов
/ 11 мая 2010

Я думаю, что это самый читаемый ответ O (n) с использованием стандартного LINQ. 

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

редактировать: объяснение CoffeeAddict

Aggregate - это название LINQ для общеизвестной функциональной концепции Fold

Он проходит по каждому элементу набора и применяет любую функцию, которую вы предоставляете. Здесь функция, которую я предоставляю, является функцией сравнения, которая возвращает большее значение. Зацикливаясь, 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;
35 голосов
/ 07 января 2011

После прочтения различных предложений я решил сравнить их и поделиться результатами.

Проверенный код: 

// 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 компактен и гибок.

11 голосов
/ 10 мая 2010

Может быть, это не очень хорошее применение для LINQ. Я вижу 2 полных сканирования словаря с использованием решения LINQ (1, чтобы получить максимум, затем другой, чтобы найти kvp, чтобы вернуть строку.

Вы можете сделать это за 1 проход со старомодным foreach: 


KeyValuePair<string, double> max = new KeyValuePair<string, double>(); 
foreach (var kvp in results)
{
  if (kvp.Value > max.Value)
    max = kvp;
}
return max.Key;
6 голосов
/ 10 мая 2010

Это быстрый метод. Это O (n), что является оптимальным. Единственная проблема, которую я вижу, заключается в том, что он выполняет итерацию по словарю дважды, а не один раз.

Вы можете выполнить итерацию по словарю один раз, используя MaxBy из morelinq . 

results.MaxBy(kvp => kvp.Value).Key;
2 голосов
/ 28 февраля 2017

Вы можете отсортировать словарь, используя OrderBy (для поиска минимального значения) или OrderByDescending (для максимального значения), а затем получить первый элемент. Это также помогает, когда вам нужно найти второй элемент 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;
1 голос
/ 13 июня 2017

Маленький метод расширения: 

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;

0 голосов
/ 16 апреля 2014

Как насчет того, чтобы сделать это параллельно, используя 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);
  }
});
0 голосов
/ 10 мая 2010

Я думаю, что при использовании стандартных библиотек LINQ это так быстро, как вы можете.

...