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

Question

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

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

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

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

Answer 1

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

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

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

Aggregate является LI Имя NQ для общеизвестной функциональной концепции 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; 

Answer 2

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

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

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

Answer 3

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

Answer 4

Возможно, это не подходит для 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; 
 

Answer 5

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

Код испытания:

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

Answer 6

Как сделать это параллельно с помощью 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)); 
    } 
}); 

EDIT (обновление кода, чтобы избежать возможного состояния гонки выше):

Вот более прочный шаблон, который также показывает выбор минимального значения параллельно. Я думаю, что это решает проблемы, упомянутые в комментариях ниже относительно возможного состояния гонки:

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

Answer 7

Вы можете сортировать словарь с помощью OrderBy (для поиска минимального значения) или OrderByDescending (для максимального значения), то получить первый элемент. Это также поможет, если вам нужно найти вторую макс/мин элемент

Получить ключ словаря на максимальном значении:

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; 

Answer 8

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

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;