Ich habe vor kurzem angefangen, LINQ ziemlich oft zu verwenden, und ich habe keine Erwähnung der Laufzeitkomplexität für eine der LINQ-Methoden gesehen. Offensichtlich spielen hier viele Faktoren eine Rolle. Beschränken wir die Diskussion daher auf den einfachen IEnumerable
LINQ-to-Objects-Anbieter. Nehmen wir weiter an, dass jede Func
als Selektor / Mutator / etc. übergebene Operation eine billige O (1) -Operation ist.
Es scheint offensichtlich , dass alle die Single-Pass - Operationen ( Select
, Where
, Count
, Take/Skip
, Any/All
, etc.) O (n) sein, da sie nur einmal die Sequenz gehen muß; obwohl auch dies der Faulheit unterliegt.
Bei den komplexeren Operationen ist es düsterer. die Set-wie Operatoren ( Union
, Distinct
, Except
, etc.) arbeitet mit GetHashCode
der Standardeinstellung (afaik), so scheint es vernünftig , sie verwenden eine Hash-Tabelle intern, so dass diese Operationen O (n) als auch im Allgemeinen zu übernehmen. Was ist mit den Versionen, die ein verwenden IEqualityComparer
?
OrderBy
würde eine Sortierung benötigen, also schauen wir uns höchstwahrscheinlich O (n log n) an. Was ist, wenn es bereits sortiert ist? Wie wäre es, wenn ich OrderBy().ThenBy()
beiden den gleichen Schlüssel sage und gebe?
Ich konnte sehen GroupBy
(und Join
) entweder Sortieren oder Hashing verwenden. Welches ist es?
Contains
wäre O (n) auf a List
, aber O (1) auf a HashSet
- prüft LINQ den zugrunde liegenden Container, um festzustellen, ob er die Dinge beschleunigen kann?
Und die eigentliche Frage - bisher habe ich davon ausgegangen, dass die Operationen performant sind. Kann ich mich jedoch darauf verlassen? STL-Container geben beispielsweise die Komplexität jeder Operation klar an. Gibt es ähnliche Garantien für die LINQ-Leistung in der .NET-Bibliotheksspezifikation?
Weitere Frage (als Antwort auf Kommentare):
Hatte nicht wirklich über Overhead nachgedacht, aber ich hatte nicht erwartet, dass es für einfache Linq-to-Objects sehr viel geben würde. In der CodingHorror-Veröffentlichung geht es um Linq-to-SQL, bei dem ich verstehen kann, dass das Parsen der Abfrage und das Erstellen von SQL zusätzliche Kosten verursachen. Gibt es ähnliche Kosten auch für den Objects-Anbieter? Wenn ja, ist es anders, wenn Sie die deklarative oder funktionale Syntax verwenden?
Antworten:
Es gibt sehr, sehr wenige Garantien, aber einige Optimierungen:
Erweiterungsmethoden , die einen Index den Zugriff verwenden, wie
ElementAt
,Skip
,Last
oderLastOrDefault
, prüft , ob die zugrunde liegenden Typ implementiert , um zu sehenIList<T>
, so dass Sie erhalten , O (1) Zugang anstelle von O (N).Die
Count
Methode sucht nach einerICollection
Implementierung, sodass diese Operation O (1) anstelle von O (N) ist.Distinct
,GroupBy
Join
Glaube, und ich auch die Set-Aggregationsverfahren (Union
,Intersect
undExcept
) Verwendung Hashing, so dass sie nahe an O (N) sein sollten anstelle von O (N²).Contains
prüft auf eineICollection
Implementierung, daher kann es O (1) sein, wenn die zugrunde liegende Sammlung auch O (1) ist, wie z. B. aHashSet<T>
, dies hängt jedoch von der tatsächlichen Datenstruktur ab und ist nicht garantiert. Hash-Sets überschreiben dieContains
Methode, deshalb sind sie O (1).OrderBy
Methoden verwenden eine stabile Quicksortierung, daher handelt es sich um einen Durchschnittsfall von O (N log N).Ich denke, das deckt die meisten, wenn nicht alle integrierten Erweiterungsmethoden ab. Es gibt wirklich nur sehr wenige Leistungsgarantien. Linq selbst wird versuchen, effiziente Datenstrukturen zu nutzen, aber es ist kein freier Durchgang, potenziell ineffizienten Code zu schreiben.
quelle
IEqualityComparer
Überlastungen?IEqualityComparer
, kann ich nicht begründen, dass dies die asymptotische Komplexität beeinflusst.EqualityComparer
Geräte nichtGetHashCode
so gut realisiert wieEquals
; Aber das macht natürlich Sinn.Orderby().ThenBy()
stillN logN
oder ist es(N logN) ^2
oder so ähnlich?Ich habe lange gewusst, dass das
.Count()
zurückkehrt,.Count
wenn die Aufzählung eine istIList
.Aber ich war immer ein bisschen müde über die Laufzeit - Komplexität der Set - Vorgänge:
.Intersect()
,.Except()
,.Union()
.Hier ist die dekompilierte BCL-Implementierung (.NET 4.0 / 4.5) für
.Intersect()
(meine Kommentare):Schlussfolgerungen:
IEqualityComparer<T>
auch übereinstimmen muss.)Der Vollständigkeit halber sind hier die Implementierungen für
.Union()
und.Except()
.Spoiler-Alarm: Auch sie haben eine O (N + M) -Komplexität.
quelle
Alles, worauf Sie sich wirklich verlassen können, ist, dass die Enumerable-Methoden für den allgemeinen Fall gut geschrieben sind und keine naiven Algorithmen verwenden. Es gibt wahrscheinlich Dinge von Drittanbietern (Blogs usw.), die die tatsächlich verwendeten Algorithmen beschreiben, aber diese sind nicht offiziell oder in dem Sinne garantiert, wie es STL-Algorithmen sind.
Zur Veranschaulichung hier der reflektierte Quellcode (mit freundlicher Genehmigung von ILSpy) für
Enumerable.Count
von System.Core:Wie Sie sehen können, ist es eine Anstrengung, die naive Lösung zu vermeiden, einfach jedes Element aufzuzählen.
quelle
Enumerable.Count
sie nicht iteriert, es sei denn, es gibt keine offensichtliche Alternative. Wie hätten Sie es weniger naiv gemacht?Ich habe gerade einen Reflektor ausgebrochen und sie überprüfen den zugrunde liegenden Typ, wenn er
Contains
aufgerufen wird.quelle
Die richtige Antwort lautet "es kommt darauf an". Dies hängt davon ab, welcher Typ die zugrunde liegende IEnumerable ist. Ich weiß, dass für einige Sammlungen (wie Sammlungen, die ICollection oder IList implementieren) spezielle Codepfade verwendet werden. Es wird jedoch nicht garantiert, dass die tatsächliche Implementierung etwas Besonderes bewirkt. Ich weiß zum Beispiel, dass ElementAt () einen Sonderfall für indizierbare Sammlungen hat, ähnlich wie Count (). Im Allgemeinen sollten Sie jedoch wahrscheinlich die O (n) -Leistung im ungünstigsten Fall annehmen.
Im Allgemeinen glaube ich nicht, dass Sie die Art von Leistungsgarantien finden werden, die Sie möchten. Wenn Sie jedoch auf ein bestimmtes Leistungsproblem mit einem linq-Operator stoßen, können Sie es immer nur für Ihre bestimmte Sammlung neu implementieren. Es gibt auch viele Blogs und Erweiterungsprojekte, die Linq auf Objekte erweitern, um diese Art von Leistungsgarantien hinzuzufügen. Weitere Leistungsvorteile finden Sie unter Indizierter LINQ, der den Operator-Satz erweitert und erweitert.
quelle