C #에서 Dictionary의 가장 높은 값의 키를 얻는 좋은 방법

C #에서 Dictionary의 가장 높은 값의 키를 얻는 좋은 방법

---

.NET Framework에서 최대 값의 키를 얻으려고합니다 Dictionary<string, double> results.

이것이 내가 지금까지 가지고있는 것입니다.

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

그러나 이것은 약간 비효율적으로 보이므로 더 나은 방법이 있는지 궁금합니다.

---

나는 이것이 표준 LINQ를 사용하는 가장 읽기 쉬운 O (n) 대답이라고 생각합니다.

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

편집 : CoffeeAddict에 대한 설명

Aggregate일반적으로 알려진 기능 개념 Fold 의 LINQ 이름입니다.

세트의 각 요소를 반복하고 제공하는 모든 기능을 적용합니다. 여기서 제가 제공하는 함수는 더 큰 값을 반환하는 비교 함수입니다. 루핑하는 동안 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에 적합하지 않을 수 있습니다. LINQ 솔루션을 사용하여 사전에 대한 2 개의 전체 스캔이 표시됩니다 (1 개는 최대 값을 얻고 다른 하나는 kvp를 찾아 문자열을 반환합니다.

"구식"foreach를 사용하여 1 회 통과 할 수 있습니다.

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)입니다. 내가 보는 유일한 문제는 사전을 한 번이 아니라 두 번 반복한다는 것입니다.

morelinq의 MaxBy 를 사용하여 사전을 한 번 반복 할 수 있습니다 .

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

---

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;

---

작은 확장 방법 :

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

편집 (위의 가능한 경쟁 조건을 피하기 위해 업데이트 된 코드) :

다음은 최소값을 병렬로 선택하는 것을 보여주는보다 강력한 패턴입니다. 나는 이것이 가능한 경쟁 조건에 관한 아래 의견에 언급 된 우려를 해결한다고 생각합니다.

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

---

I think using the standard LINQ Libraries this is as fast as you can go.

참고URL : https://stackoverflow.com/questions/2805703/good-way-to-get-the-key-of-the-highest-value-of-a-dictionary-in-c-sharp