Guter Weg, um den Schlüssel mit dem höchsten Wert eines Wörterbuchs in C # zu erhalten

77

Ich versuche, den Schlüssel des Maximalwerts in der zu erhalten Dictionary<string, double> results.

Das habe ich bisher:

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

Da dies jedoch etwas ineffizient erscheint, habe ich mich gefragt, ob es einen besseren Weg gibt, dies zu tun.

Arda Xi
quelle
2
Soll Ihr Wörterbuch <double, string> sein oder ist das rückwärts?
Stephan
1
Du hast recht, es ist <string, double>. Korrigiert.
Arda Xi
Warum haben Sie eine .Wählen Sie nach wo? Ich bin nicht so sicher mit LINQ, nur neugierig
PositiveGuy
1
@CoffeeAddict the .Select ermöglicht ihm die "Projektion". Hier konvertiert er das KeyValuePair in nur einen Schlüssel. Er hätte diesen Teil weglassen und einfach schreiben können .First().Key;, um stattdessen den Schlüssel zu bekommen.
dss539
@ dss539 Ah, ein bisschen spät, aber du hast recht. Das wäre effizienter.
Arda Xi

Antworten:

135

Ich denke, dies ist die am besten lesbare O (n) -Antwort mit Standard-LINQ.

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

edit: Erklärung für CoffeeAddict

Aggregateist der LINQ-Name für das allgemein bekannte Funktionskonzept Fold

Es durchläuft jedes Element der Menge und wendet jede von Ihnen bereitgestellte Funktion an. Hier ist die von mir bereitgestellte Funktion eine Vergleichsfunktion, die den größeren Wert zurückgibt. AggregateErinnert sich während der Schleife an das Rückgabeergebnis vom letzten Aufruf meiner Funktion. Es speist dies als Variable in meine Vergleichsfunktion ein l. Die Variable rist das aktuell ausgewählte Element.

Nachdem das Aggregat die gesamte Menge durchlaufen hat, gibt es das Ergebnis des letzten Aufrufs meiner Vergleichsfunktion zurück. Dann habe ich das .KeyMitglied daraus gelesen , weil ich weiß, dass es ein Wörterbucheintrag ist

Hier ist eine andere Sichtweise [Ich garantiere nicht, dass dies kompiliert wird;)]

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;
dss539
quelle
3
+1 dss539: Ich hatte einen Juckreiz im Gehirn, als hätte es eine Möglichkeit geben sollen, dies mit LINQ zu tun. Nett!
JMarsch
40

Nachdem ich verschiedene Vorschläge gelesen hatte, beschloss ich, sie zu bewerten und die Ergebnisse zu teilen.

Der getestete Code:

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

Die Ergebnisse:

Average Seconds Test 1 = 2.6
Average Seconds Test 2 = 4.4
Average Seconds Test 3 = 11.2
Average Seconds Test 4 = 11.2

Dies dient nur dazu, eine Vorstellung von ihrer relativen Leistung zu geben.

Wenn Ihre Optimierung "foreach" am schnellsten ist, LINQ jedoch kompakt und flexibel ist.

WhoIsRich
quelle
5
+1, weil du dir die Zeit genommen hast, es auf die Bank zu setzen. Wie unterscheiden sich Test 3 und 4? Sie erzeugen die gleiche MSIL, nicht wahr?
dss539
1
Ich habe gerade überprüft und Sie sind richtig, Test 3 und 4 produzieren den gleichen MSIL-Code :)
WhoIsRich
11

Vielleicht ist dies keine gute Verwendung für LINQ. Ich sehe 2 vollständige Scans des Wörterbuchs mit der LINQ-Lösung (1, um das Maximum zu erhalten, und ein weiterer, um das KVP zu finden, um die Zeichenfolge zurückzugeben.

Sie könnten es in einem Durchgang mit einem "altmodischen" Foreach tun:


KeyValuePair<string, double> max = new KeyValuePair<string, double>(); 
foreach (var kvp in results)
{
  if (kvp.Value > max.Value)
    max = kvp;
}
return max.Key;

JMarsch
quelle
1
Ich weiß, dass es zum gleichen Ergebnis führt, aber ich habe festgestellt, dass dies besser lesbar ist:var max = default(KeyValuePair<string, double>);
ChaosPandion
2
Du hast recht; Das OP hatte einen O (2n) -Algorithmus unter Verwendung von see. Siehe meine Antwort für ein O (n) mit LINQ.
dss539
4
+1 zum Reduzieren der Iterationen. Sie sollten max.Value wahrscheinlich mit double.MinValue initialisieren, um sicherzustellen, dass Sie ein max finden, auch wenn es negativ ist.
Chris Taylor
halte es einfach :) klassische Suchalgorithmen sind immer verfügbar. Sie müssen nicht glauben, dass es schwierig sein wird.
Davut Gürbüz
7

Dies ist eine schnelle Methode. Es ist O (n), was optimal ist. Das einzige Problem, das ich sehe, ist, dass es das Wörterbuch zweimal anstatt nur einmal durchläuft.

Sie können es einmal mit MaxBy von morelinq über das Wörterbuch iterieren .

results.MaxBy(kvp => kvp.Value).Key;
Mark Byers
quelle
Aggregatekann auch für den gleichen Effekt verwendet werden.
dss539
5

Sie können das Wörterbuch sortieren, indem Sie OrderBy (zum Auffinden des Mindestwerts) oder OrderByDescending (zum Auffinden des Höchstwerts) verwenden und dann das erste Element abrufen. Es ist auch hilfreich, wenn Sie das zweite max / min-Element suchen müssen

Holen Sie sich den Wörterbuchschlüssel nach maximalem Wert:

double min = results.OrderByDescending(x => x.Value).First().Key;

Holen Sie sich den Wörterbuchschlüssel nach Mindestwert:

double min = results.OrderBy(x => x.Value).First().Key;

Holen Sie sich den Wörterbuchschlüssel nach dem zweiten Maximalwert:

double min = results.OrderByDescending(x => x.Value).Skip(1).First().Key;

Holen Sie sich den Wörterbuchschlüssel nach dem zweiten Mindestwert:

double min = results.OrderBy(x => x.Value).Skip(1).First().Key;
Geograph
quelle
1
Es scheint, dass OrderBymehr Berechnungen durchgeführt werden, als wirklich benötigt werden.
Babak.Abad
Ja. Die Sortierung ist O (n * log (n)) und das Min / Max-Element ist O (n).
Zar Shardan
3

Kleine Erweiterungsmethode:

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

Dann:

int keyOfMax = myDictionary.GetMaxValuePair().Key;

kamyker
quelle
2

Guck dir diese an:

result.Where (x => x.Value == result.Values.Max ()). Wählen Sie (x => x.Key) .ToList ()

Vineet Agarwal
quelle
0

Wie wäre es mit einer parallelen Verwendung von Interlocked.Exchange für die Thread-Sicherheit :) Beachten Sie, dass Interlocked.Exchange nur mit einem Referenztyp funktioniert (dh ein Struktur- oder Schlüsselwertpaar (sofern es nicht in eine Klasse eingeschlossen ist) funktioniert nicht der Maximalwert.

Hier ist ein Beispiel aus meinem eigenen Code:

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

BEARBEITEN (Code aktualisiert, um mögliche Rennbedingungen oben zu vermeiden):

Hier ist ein robusteres Muster, das auch die parallele Auswahl eines Min-Werts zeigt. Ich denke, dies behebt die in den Kommentaren unten erwähnten Bedenken hinsichtlich einer möglichen Rennbedingung:

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);
  }
});
Jake Drew
quelle
Ich bin mir ziemlich sicher, dass dieses Beispiel eine Rennbedingung hat. Zwischen dem Vergleichen des Maximalwerts mit dem aktuellen Wert und dem Austauschen dieser Werte hätte ein anderer Thread möglicherweise dasselbe tun und bereits einen besseren Wert in maxValue umwandeln können, der dann durch den schlechteren Wert des aktuellen Threads beeinträchtigt wird.
dss539
Ich habe die Antwort mit einer robusteren Lösung aktualisiert, die meiner Meinung nach die potenzielle Rennbedingung berücksichtigt.
Jake Drew
Ich denke, du hast recht. So dachte ich daran, das Rennen zu lösen. Ich frage mich, ob eine Lese- / Schreibsperre eine bessere Leistung hätte. +1 für das Update
dss539
0

Meine Version basiert auf der aktuellen Enumerable.Max-Implementierung mit einem optionalen Vergleicher:

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

Anwendungsbeispiel:

    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");
    }
Zar Shardan
quelle
-4

Ich denke, mit den Standard-LINQ-Bibliotheken ist dies so schnell wie möglich.

ist_lion
quelle