Я пытаюсь получить ключ максимального значения в Dictionary<string, double> results.
Это то, что у меня есть до сих пор:
double max = results.Max(kvp => kvp.Value);
return results.Where(kvp => kvp.Value == max).Select(kvp => kvp.Key).First();
Однако, поскольку это кажется немного неэффективным, мне было интересно, есть ли лучший способ сделать это.
Я думаю, что это самый читаемый ответ O (n) с использованием стандартного LINQ.
var max = results.Aggregate((l, r) => l.Value > r.Value ? l : r).Key;
edit: объяснение для 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;
Прочитав различные предложения, я решил сравнить их и поделиться результатами.
Проверенный код:
// 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;
Это быстрый метод. Это O (n), что является оптимальным. Единственная проблема, которую я вижу, заключается в том, что она выполняет итерацию по словарю дважды, а не только один раз.
Вы можете сделать это, итерации по словарю один раз, используя MaxBy из morelinq.
results.MaxBy(kvp => kvp.Value).Key;
Вы можете сортировать словарь, используя OrderBy (для определения значения min) или 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;
Получить ключ словаря вторым значением min:
double min = results.OrderBy(x => x.Value).Skip(1).First().Key;
Маленький метод расширения:
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;
Как сделать это параллельно с помощью 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);
}
});
Моя версия основана на текущей реализации Enumerable.Max с дополнительным компаратором:
public static TSource MaxValue<TSource, TConversionResult>(this IEnumerable<TSource> source, Func<TSource, TConversionResult> function, IComparer<TConversionResult> comparer = null)
{
comparer = comparer ?? Comparer<TConversionResult>.Default;
if (source == null) throw new ArgumentNullException(nameof(source));
TSource max = default;
TConversionResult maxFx = default;
if ( (object)maxFx == null) //nullable stuff
{
foreach (var x in source)
{
var fx = function(x);
if (fx == null || (maxFx != null && comparer.Compare(fx, maxFx) <= 0)) continue;
maxFx = fx;
max = x;
}
return max;
}
//valuetypes
var notFirst = false;
foreach (var x in source)
{
var fx = function(x);
if (notFirst)
{
if (comparer.Compare(fx, maxFx) <= 0) continue;
maxFx = fx;
max = x;
}
else
{
maxFx = fx;
max = x;
notFirst = true;
}
}
if (notFirst)
return max;
throw new InvalidOperationException("Sequence contains no elements");
}
Пример использования:
class Wrapper
{
public int Value { get; set; }
}
[TestMethod]
public void TestMaxValue()
{
var dictionary = new Dictionary<string, Wrapper>();
for (var i = 0; i < 19; i++)
{
dictionary[$"s:{i}"] = new Wrapper{Value = (i % 10) * 10 } ;
}
var m = dictionary.Keys.MaxValue(x => dictionary[x].Value);
Assert.AreEqual(m, "s:9");
}
Я думаю, что с помощью стандартных библиотек LINQ это так же быстро, как вы можете.