Ich habe eine Klasse wie diese:
public class MyClass
{
public int Value { get; set; }
public bool IsValid { get; set; }
}
Tatsächlich ist es viel größer, aber dies schafft das Problem (Verrücktheit) neu.
Ich möchte die Summe von erhalten Value
, wo die Instanz gültig ist. Bisher habe ich zwei Lösungen dafür gefunden.
Der erste ist dieser:
int result = myCollection.Where(mc => mc.IsValid).Select(mc => mc.Value).Sum();
Der zweite ist jedoch folgender:
int result = myCollection.Select(mc => mc.IsValid ? mc.Value : 0).Sum();
Ich möchte die effizienteste Methode erhalten. Zuerst dachte ich, dass der zweite effizienter sein würde. Dann fing der theoretische Teil von mir an zu sagen: "Nun, einer ist O (n + m + m), der andere ist O (n + n). Der erste sollte mit mehr Invaliden besser abschneiden, während der zweite besser abschneiden sollte mit weniger". Ich dachte, dass sie gleich gut abschneiden würden. EDIT: Und dann wies @Martin darauf hin, dass Where und Select kombiniert wurden, also sollte es eigentlich O (m + n) sein. Wenn Sie jedoch nach unten schauen, scheint dies nicht miteinander verbunden zu sein.
Also habe ich es auf die Probe gestellt.
(Es sind mehr als 100 Zeilen, daher dachte ich, es wäre besser, es als Kern zu veröffentlichen.)
Die Ergebnisse waren ... interessant.
Mit 0% Bindungstoleranz:
Die Skalen sprechen für Select
und Where
um ~ 30 Punkte.
How much do you want to be the disambiguation percentage?
0
Starting benchmarking.
Ties: 0
Where + Select: 65
Select: 36
Mit 2% Bindungstoleranz:
Es ist das gleiche, außer dass sie für einige innerhalb von 2% lagen. Ich würde sagen, das ist eine minimale Fehlerquote. Select
und Where
jetzt haben nur noch ~ 20 Punkte Vorsprung.
How much do you want to be the disambiguation percentage?
2
Starting benchmarking.
Ties: 6
Where + Select: 58
Select: 37
Mit 5% Bindungstoleranz:
Dies würde ich als meine maximale Fehlerquote bezeichnen. Es macht es ein bisschen besser für die Select
, aber nicht viel.
How much do you want to be the disambiguation percentage?
5
Starting benchmarking.
Ties: 17
Where + Select: 53
Select: 31
Mit 10% Bindungstoleranz:
Dies ist ein Ausweg aus meiner Fehlerquote, aber ich bin immer noch am Ergebnis interessiert. Weil es den Select
und Where
den 20-Punkte-Vorsprung gibt, den es schon eine Weile hat.
How much do you want to be the disambiguation percentage?
10
Starting benchmarking.
Ties: 36
Where + Select: 44
Select: 21
Mit 25% Bindungstoleranz:
Dies ist übrigens Weg aus meiner Fehlermarge, aber ich bin immer noch im Ergebnis interessiert, weil das Select
und Where
noch (fast) ihren 20 - Punkte - Vorsprung halten. Es scheint, als würde es in einigen wenigen Punkten übertroffen, und genau das gibt ihm die Führung.
How much do you want to be the disambiguation percentage?
25
Starting benchmarking.
Ties: 85
Where + Select: 16
Select: 0
Nun, ich nehme an, dass der 20 - Punkte - Vorsprung aus der Mitte kam, wo sie beide gebunden sind , zu erhalten , um die gleiche Leistung. Ich könnte versuchen, es zu protokollieren, aber es wäre eine ganze Menge Informationen, die ich aufnehmen müsste. Ein Diagramm wäre besser, denke ich.
Das habe ich also getan.
Es zeigt, dass die Select
Linie stabil bleibt (erwartet) und dass die Select + Where
Linie steigt (erwartet). Was mich jedoch verwundert, ist, warum es nicht mit dem Select
bei 50 oder früher übereinstimmt: Tatsächlich hatte ich früher als 50 erwartet, da ein zusätzlicher Enumerator für das Select
und erstellt werden musste Where
. Ich meine, das zeigt den 20-Punkte-Vorsprung, aber es erklärt nicht warum. Dies ist wohl der Hauptpunkt meiner Frage.
Warum verhält es sich so? Soll ich ihm vertrauen? Wenn nicht, sollte ich den anderen oder diesen verwenden?
Wie @KingKong in den Kommentaren erwähnt, können Sie auch die Sum
Überlastung verwenden, die ein Lambda benötigt. Meine beiden Optionen werden nun dahingehend geändert:
Zuerst:
int result = myCollection.Where(mc => mc.IsValid).Sum(mc => mc.Value);
Zweite:
int result = myCollection.Sum(mc => mc.IsValid ? mc.Value : 0);
Ich werde es etwas kürzer machen, aber:
How much do you want to be the disambiguation percentage?
0
Starting benchmarking.
Ties: 0
Where: 60
Sum: 41
How much do you want to be the disambiguation percentage?
2
Starting benchmarking.
Ties: 8
Where: 55
Sum: 38
How much do you want to be the disambiguation percentage?
5
Starting benchmarking.
Ties: 21
Where: 49
Sum: 31
How much do you want to be the disambiguation percentage?
10
Starting benchmarking.
Ties: 39
Where: 41
Sum: 21
How much do you want to be the disambiguation percentage?
25
Starting benchmarking.
Ties: 85
Where: 16
Sum: 0
Der zwanzig Punkte Vorsprung ist immer noch da, was bedeutet , es nicht mit dem zu tun hat Where
und Select
Kombination von @Marcin in den Kommentaren darauf hingewiesen.
Vielen Dank für das Lesen meiner Textwand! Wenn Sie interessiert sind, finden Sie hier die geänderte Version, die die von Excel aufgenommene CSV protokolliert.
mc.Value
sind.Where
+Select
verursacht keine zwei getrennten Iterationen über die Eingabesammlung. LINQ to Objects optimiert es in einer Iteration. Lesen Sie mehr auf meinem Blog-BeitragAntworten:
Select
iteriert einmal über den gesamten Satz und führt für jedes Element eine bedingte Verzweigung (Überprüfung auf Gültigkeit) und eine+
Operation durch.Where+Select
Erstellt einen Iterator, der ungültige Elemente überspringt (nichtyield
) und+
nur die gültigen Elemente ausführt .Die Kosten für a
Select
sind also:Und für
Where+Select
:Wo:
p(valid)
ist die Wahrscheinlichkeit, dass ein Element in der Liste gültig ist.cost(check valid)
sind die Kosten der Filiale, die die Gültigkeit überprüftcost(yield)
sind die Kosten für die Erstellung des neuen Status deswhere
Iterators, der komplexer ist als der einfache Iterator, den dieSelect
Version verwendet.Wie Sie sehen können,
n
ist dieSelect
Version für eine bestimmte Konstante, während dieWhere+Select
Version eine lineare Gleichung mitp(valid)
als Variable ist. Die tatsächlichen Kostenwerte bestimmen den Schnittpunkt der beiden Linien, und dacost(yield)
sie sich von diesen unterscheiden könnencost(+)
, schneiden sie sich nicht unbedingt beip(valid)
= 0,5.quelle
cost(append)
? Wirklich gute Antwort, betrachtet es aus einem anderen Blickwinkel als nur Statistiken.Where
erstellt nichts, gibt nur jeweils ein Element aus dersource
Sequenz zurück, wenn es nur das Prädikat füllt.IEnumerable.Select(IEnumerable, Func)
undIQueryable.Select(IQueryable, Expression<Func>)
. Sie haben Recht, dass LINQ "nichts" tut, bis Sie die Sammlung durchlaufen, was Sie wahrscheinlich gemeint haben.Hier finden Sie eine ausführliche Erklärung der Ursachen für die Zeitunterschiede.
Die
Sum()
Funktion fürIEnumerable<int>
sieht folgendermaßen aus:In C #
foreach
ist nur syntaktischer Zucker für die .Net-Version eines Iterators (nicht zu verwechseln mit ) . Der obige Code wird also tatsächlich in diesen übersetzt:IEnumerator<T>
IEnumerable<T>
Denken Sie daran, dass die beiden Codezeilen, die Sie vergleichen, die folgenden sind
Hier ist der Kicker:
LINQ verwendet die verzögerte Ausführung . Während es so aussieht ,
result1
als würde die Sammlung zweimal durchlaufen , wird sie tatsächlich nur einmal durchlaufen. DieWhere()
Bedingung wird tatsächlich währendSum()
des Aufrufs von angewendetMoveNext()
(Dies ist dank der Magie von möglichyield return
) .Dies bedeutet, dass für
result1
den Code innerhalb derwhile
Schleife,wird nur einmal für jeden Artikel mit ausgeführt
mc.IsValid == true
. Im Vergleich dazuresult2
wird dieser Code für jedes Element in der Sammlung ausgeführt. Deshalb istresult1
in der Regel schneller.(Beachten Sie jedoch, dass das Aufrufen der
Where()
Bedingung im InnerenMoveNext()
immer noch einen geringen Overhead hat. Wenn also die meisten / alle Elemente vorhanden sindmc.IsValid == true
,result2
ist dies tatsächlich schneller!)Hoffentlich ist jetzt klar, warum
result2
es normalerweise langsamer ist. Jetzt möchte ich erklären, warum ich in den Kommentaren angegeben habe, dass diese LINQ-Leistungsvergleiche keine Rolle spielen .Das Erstellen eines LINQ-Ausdrucks ist billig. Das Aufrufen von Delegatenfunktionen ist günstig. Das Zuweisen und Schleifen eines Iterators ist billig. Aber es ist noch billiger, diese Dinge nicht zu tun. Wenn Sie also feststellen, dass eine LINQ-Anweisung der Engpass in Ihrem Programm ist, wird sie meiner Erfahrung nach ohne LINQ immer schneller als jede der verschiedenen LINQ-Methoden.
Ihr LINQ-Workflow sollte also folgendermaßen aussehen:
Glücklicherweise sind LINQ-Engpässe selten. Engpässe sind selten. Ich habe in den letzten Jahren Hunderte von LINQ-Anweisungen geschrieben und am Ende <1% ersetzt. Und die meisten davon waren auf die schlechte SQL-Optimierung von LINQ2EF zurückzuführen, anstatt auf LINQs Schuld.
Also, wie immer, schreiben Sie klar und vernünftig Code zuerst, und warten , bis nach Ihnen Sorgen über Mikro-Optimierungen profiliert haben.
quelle
Lustige Sache. Wissen Sie, wie
Sum(this IEnumerable<TSource> source, Func<TSource, int> selector)
definiert ist? Es verwendetSelect
Methode!Eigentlich sollte alles fast gleich funktionieren. Ich habe selbst schnell recherchiert und hier sind die Ergebnisse:
Für folgende Implementierungen:
mod
bedeutet: Jede 1 vonmod
Elementen ist ungültig: Fürmod == 1
jedes Element ist ungültig, fürmod == 2
ungerade Elemente sind ungültig usw. Die Sammlung enthält10000000
Elemente.Und Ergebnisse für die Sammlung mit
100000000
Gegenständen:Wie Sie sehen können,
Select
undSum
Ergebnisse sind recht übergreifend konsistentemod
Werte. Jedochwhere
undwhere
+select
nicht.quelle
Ich vermute, dass die Version mit Where die Nullen herausfiltert und sie kein Thema für Sum sind (dh Sie führen die Addition nicht aus). Dies ist natürlich eine Vermutung, da ich nicht erklären kann, wie das Ausführen eines zusätzlichen Lambda-Ausdrucks und das Aufrufen mehrerer Methoden eine einfache Addition einer 0 übertrifft.
Ein Freund von mir schlug vor, dass die Tatsache, dass die 0 in der Summe aufgrund von Überlaufprüfungen schwere Leistungseinbußen verursachen könnte. Es wäre interessant zu sehen, wie sich dies im ungeprüften Kontext verhält.
quelle
unchecked
machen es ein kleines bisschen besser für dieSelect
.Wenn ich das folgende Beispiel durchführe, wird mir klar, dass das einzige Mal, wenn + Select Select übertreffen kann, tatsächlich darin besteht, eine gute Menge (ungefähr die Hälfte in meinen informellen Tests) der potenziellen Elemente in der Liste zu verwerfen. In dem kleinen Beispiel unten erhalte ich ungefähr die gleichen Zahlen aus beiden Proben, wenn das Where ca. 4mil Artikel aus 10mil überspringt. Ich lief in Release und ordnete die Ausführung von where + select vs select mit den gleichen Ergebnissen neu.
quelle
Select
?Wenn Sie Geschwindigkeit brauchen, ist es wahrscheinlich die beste Wahl, nur eine einfache Schleife zu machen. Und dabei
for
in der Regel besser alsforeach
(vorausgesetzt, Ihre Sammlung ist natürlich wahlfrei zugänglich).Hier sind die Timings, die ich erhalten habe, wenn 10% der Elemente ungültig sind:
Und mit 90% ungültigen Elementen:
Und hier ist mein Benchmark-Code ...
Übrigens stimme ich der Vermutung von Stilgar zu : Die relativen Geschwindigkeiten Ihrer beiden Fälle variieren je nach Prozentsatz der ungültigen Elemente, einfach weil die Anzahl der
Sum
zu erledigenden Aufgaben im Fall "Wo" unterschiedlich ist.quelle
Anstatt zu versuchen, dies anhand einer Beschreibung zu erklären, werde ich einen mathematischeren Ansatz wählen.
Angesichts des folgenden Codes, der ungefähr annähern sollte, was LINQ intern tut, sind die relativen Kosten wie folgt:
Nur auswählen:
Nd + Na
Wo + Auswählen:
Nd + Md + Ma
Um herauszufinden, wo sie sich kreuzen werden, müssen wir eine kleine Algebra machen:
Nd + Md + Ma = Nd + Na => M(d + a) = Na => (M/N) = a/(d+a)
Dies bedeutet, dass die Kosten eines Delegatenaufrufs ungefähr den Kosten einer Addition entsprechen müssen, damit der Wendepunkt bei 50% liegt. Da wir wissen, dass der tatsächliche Wendepunkt bei etwa 60% lag, können wir rückwärts arbeiten und feststellen, dass die Kosten für einen Delegatenaufruf für @ It'sNotALie tatsächlich etwa 2/3 der Kosten für eine Addition betrugen, was überraschend ist, aber das ist es seine Zahlen sagen.
quelle
Ich finde es interessant, dass sich MarcinJuraszeks Ergebnis von dem von It'sNotALie unterscheidet. Insbesondere beginnen die Ergebnisse von MarcinJuraszek mit allen vier Implementierungen am selben Ort, während sich die Ergebnisse von It'sNotALie in der Mitte kreuzen. Ich werde anhand der Quelle erklären, wie dies funktioniert.
Nehmen wir an, dass es Gesamtelemente gibt
n
, undm
gültige Elemente gibt.Die
Sum
Funktion ist ziemlich einfach. Es durchläuft nur den Enumerator: http://typedescriptor.net/browse/members/367300-System.Linq.Enumerable.Sum(IEnumerable%601)Nehmen wir der Einfachheit halber an, dass die Sammlung eine Liste ist. Sowohl Select als auch WhereSelect erstellen eine
WhereSelectListIterator
. Dies bedeutet, dass die tatsächlich generierten Iteratoren gleich sind. In beiden Fällen gibt es eineSum
Schleife über einen Iterator, dieWhereSelectListIterator
. Der interessanteste Teil des Iterators ist der MoveNext Methode.Da die Iteratoren gleich sind, sind die Schleifen gleich. Der einzige Unterschied besteht im Körper der Schleifen.
Der Körper dieser Lambdas hat sehr ähnliche Kosten. Die where-Klausel gibt einen Feldwert zurück, und das ternäre Prädikat gibt auch einen Feldwert zurück. Die select-Klausel gibt einen Feldwert zurück, und die beiden Zweige des ternären Operators geben entweder einen Feldwert oder eine Konstante zurück. Die kombinierte select-Klausel hat den Zweig als ternären Operator, aber WhereSelect verwendet den Zweig in
MoveNext
.Alle diese Operationen sind jedoch ziemlich billig. Die bisher teuerste Operation ist die Branche, in der uns eine falsche Vorhersage kosten wird.
Eine weitere teure Operation ist hier die
Invoke
. Das Aufrufen einer Funktion dauert viel länger als das Hinzufügen eines Werts, wie Branko Dimitrijevic gezeigt hat.Wiegen ist auch die überprüfte Ansammlung
Sum
. Wenn der Prozessor kein arithmetisches Überlaufflag hat, kann dies ebenfalls kostspielig sein.Daher sind die interessanten Kosten: ist:
n
+m
) * +m
* Aufrufenchecked+=
n
* Rufe +n
* aufchecked+=
Wenn also die Kosten für Invoke viel höher sind als die Kosten für die überprüfte Akkumulation, ist der Fall 2 immer besser. Wenn sie ungefähr gerade sind, sehen wir ein Gleichgewicht, wenn ungefähr die Hälfte der Elemente gültig ist.
Es sieht so aus, als ob auf dem System von MarcinJuraszek geprüft + = vernachlässigbare Kosten verursacht, aber auf den Systemen von It'sNotALie und Branko Dimitrijevic hat geprüftes + = erhebliche Kosten. Es sieht so aus, als wäre es das teuerste auf dem It'sNotALie-System, da der Break-Even-Punkt viel höher ist. Es sieht nicht so aus, als hätte jemand Ergebnisse von einem System veröffentlicht, bei dem die Akkumulation viel mehr kostet als der Aufruf.
quelle