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.
c#
linq
dictionary
max
Arda Xi
quelle
quelle
.First().Key;
, um stattdessen den Schlüssel zu bekommen.Antworten:
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
Aggregate
ist der LINQ-Name für das allgemein bekannte Funktionskonzept FoldEs 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.
Aggregate
Erinnert sich während der Schleife an das Rückgabeergebnis vom letzten Aufruf meiner Funktion. Es speist dies als Variable in meine Vergleichsfunktion einl
. Die Variabler
ist 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
.Key
Mitglied daraus gelesen , weil ich weiß, dass es ein Wörterbucheintrag istHier 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;
quelle
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.
quelle
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;
quelle
var max = default(KeyValuePair<string, double>);
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 .
quelle
Aggregate
kann auch für den gleichen Effekt verwendet werden.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;
quelle
OrderBy
mehr Berechnungen durchgeführt werden, als wirklich benötigt werden.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;
quelle
Guck dir diese an:
result.Where (x => x.Value == result.Values.Max ()). Wählen Sie (x => x.Key) .ToList ()
quelle
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); } });
quelle
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"); }
quelle
Ich denke, mit den Standard-LINQ-Bibliotheken ist dies so schnell wie möglich.
quelle