Bei LINQ to [Ihren bevorzugten Anbieter hier einfügen] handelt es sich um eine Frage zum Suchen oder Filtern von speicherinternen Sammlungen.
Ich weiß, dass LINQ (oder Erweiterungsmethoden für Suchen / Filtern) in Objekten funktioniert, die IEnumerable oder IEnumerable<T> implementieren. Die Frage ist: wegen der Art der Aufzählung, ist jede Abfrage Komplexität mindestens O (n) ?
Zum Beispiel:
%Vor% In diesem Fall wird jeder Algorithmus mindestens O (n) annehmen, es sei denn, list ist in Bezug auf 'something' geordnet. In diesem Fall sollte die Suche O (log (n)) : Es sollte eine binäre Suche sein. Wenn ich jedoch richtig verstehe, wird diese Abfrage durch Enumeration aufgelöst, also sollte list wurde vorher bestellt.
Auch bei Parallelisierung ist es immer noch O (n). Der konstante Faktor wäre unterschiedlich (abhängig von Ihrer Anzahl an Kernen), aber wenn n variiert, würde die Gesamtzeit immer noch linear variieren.
Natürlich könnten Sie Ihre eigenen Implementierungen der verschiedenen LINQ-Operatoren über Ihre eigenen Datentypen schreiben, aber sie wären nur in sehr spezifischen Situationen geeignet - Sie müssten sicher sein, dass das Prädikat nur auf der Basis des Operators funktioniert optimierte Aspekte der Daten. Zum Beispiel, wenn Sie eine Liste von Personen haben, die nach Alter sortiert ist, wird es Ihnen nicht mit einer Abfrage helfen, die versucht, jemanden mit einem bestimmten Namen zu finden:)
Um das Prädikat zu untersuchen, müssten Sie anstelle von Delegaten Ausdrucksbäume verwenden, und das Leben würde viel schwieriger werden.
Ich vermute, dass ich normalerweise neue Methoden hinzufügen würde, die es offensichtlich machen, dass Sie die indizierte / geordnete / was auch immer Art des Datentyps verwenden und welche immer angemessen funktionieren wird. Sie können natürlich nicht einfach diese zusätzlichen Methoden aus Abfrageausdrücken aufrufen, aber Sie können immer noch LINQ mit Punktnotation verwenden.
Ja, der generische Fall ist immer O (n), wie Sklivvz sagte.
Es gibt jedoch viele LINQ-Methoden, bei denen das Objekt, das IEnumerable implementiert, tatsächlich z. ICollektion. (Ich habe das für IEnumerable.Contains zumindest gesehen.)
In der Praxis bedeutet dies, dass LINQ IEnumerable.Contains die schnellen HashSet.Contains aufruft, wenn IEnumerable zum Beispiel ein HashSet ist.
%Vor%Sie können reflector verwenden, um genau zu überprüfen, wie die LINQ-Methoden definiert sind. So habe ich das herausgefunden.
Oh, und auch LINQ enthält die Methoden IEnumerable.ToDictionary (weist den Schlüssel einem einzelnen Wert zu) und IEnumerable.ToLookup (weist den Schlüssel mehreren Werten zu). Diese Wörterbuch- / Nachschlagetabelle kann einmal erstellt und mehrmals verwendet werden, wodurch einige LINQ-intensive Codes um Größenordnungen beschleunigt werden können.
Ja, das muss es sein, denn die einzige Möglichkeit, auf ein Mitglied eines IEnumerable zuzugreifen, ist die Verwendung seiner Methoden, also O (n).
Es scheint ein klassischer Fall zu sein, in dem sich die Sprachdesigner dafür entschieden haben, Performance gegen Allgemeingültigkeit einzutauschen.
Tags und Links c# linq performance complexity-theory