Хороший способ получить ключ самого высокого значения словаря в C#
Я пытаюсь получить ключ максимального значения в Dictionary<string, double> results
.
это то, что у меня есть до сих пор:
double max = results.Max(kvp => kvp.Value);
return results.Where(kvp => kvp.Value == max).Select(kvp => kvp.Key).First();
8 ответов:
Я думаю, что это самый читаемый O(n) ответ с использованием стандартного LINQ.
var max = results.Aggregate((l, r) => l.Value > r.Value ? l : r).Key;
edit: объяснение для CoffeeAddict
Aggregate
это имя LINQ для общеизвестной функциональной концепции раза
он перебирает каждый элемент набора и применяет любую функцию, которую вы предоставляете.
Здесь функция, которую я предоставляю, является функцией сравнения, которая возвращает большее значение.
Во время цикла,Aggregate
запоминает результат возврата от последнего раз он вызвал мою функцию. Он подает это в мою функцию сравнения как переменную l
. Переменная r
- это текущий выбранный элемент.
поэтому после того, как aggregate зациклился на всем наборе, он возвращает результат с самого последнего раза, когда он вызвал мою функцию сравнения. Затем я прочитал .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;
прочитав различные предложения, я решил проверить их и поделиться результатами.
протестирован код:
// 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 компактный и гибкий.
возможно, это не очень хорошее использование для LINQ. Я вижу 2 полных сканирования словаря с использованием решения LINQ (1, чтобы получить max, а затем еще один, чтобы найти 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;
вы можете сортировать словарь с помощью 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;
Как насчет того, чтобы делать это параллельно, используя блокировку.Обмен на потокобезопасность:) имейте в виду, что блокируется.Exchange будет работать только со ссылочным типом.(т. е. пара struct или key value (если она не завернута в класс) не будет работать для хранения максимального значения.
вот пример из моего кода:
//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);
}
});
маленький метод расширения:
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;