In-Memory-LINQ Leistung

Question

Mehr als über LINQ to [Ihre Lieblingsanbieter hier einfügen], ist diese Frage über die Suche oder Filtern von In-Memory-Sammlungen.

Ich weiß, LINQ (oder Suchen / Filtern von Erweiterungsmethoden) arbeitet in Objekten Umsetzung IEnumerable oder IEnumerable<T>. Die Frage ist: wegen der Art der Aufzählung ist jede Abfrage Komplexität zumindest O (n)

?

Zum Beispiel:

var result = list.FirstOrDefault(o => o.something > n);

In diesem Fall nimmt jeder Algorithmus mindestens O (n) , es sei denn list in Bezug auf 'something' bestellt wird, wobei in diesem Fall die Suche nehmen sollte O (log (n)) : es sollte eine binäre Suche sein. Allerdings Wenn ich richtig verstehe, wird diese Abfrage durch Aufzählung aufgelöst werden, so sollte es dauern O (n) , auch in list vorher bestellt wurde.

• Gibt es etwas, was ich tun kann eine Abfrage in O (log (n)) ?
lösen
• Wenn ich Leistung will, sollte ich Array.Sort und Array.BinarySearch?

Answer 1

Auch bei Parallelisierung, es ist immer noch O (n). Der konstante Faktor würde unterschiedlich sein (je nach Anzahl der Kerne), sondern als n die Gesamtzeit variierte würde noch linear variieren.

Natürlich können Sie Ihre eigenen Implementierungen der verschiedenen LINQ-Operatoren über Ihre eigenen Datentypen schreiben, aber sie würden nur in ganz bestimmten Situationen sinnvoll sein - würden Sie sicher wissen, haben, daß das Prädikat nur auf das operierte optimierte Aspekte der Daten. Zum Beispiel, wenn Sie eine Liste von Leuten haben, die nach Alter geordnet sind, ist es Ihnen nicht mit einer Abfrage nicht helfen, die jemanden mit einem bestimmten Namen zu finden versucht:)

, um das Prädikat zu untersuchen, müssten Sie Ausdruck Bäume verwenden, anstatt der Delegierten, und das Leben wäre viel schwieriger geworden.

Ich vermute, ich würde normalerweise neue Methoden hinzufügen, die es auf der Hand, dass Sie die indiziert / bestellt / welche Art auch immer vom Datentyp verwenden, und welche immer in geeigneter Weise arbeiten. Sie konnten nicht leicht, diese zusätzlichen Methoden von Abfrageausdrücken aufrufen, natürlich, aber man kann immer noch LINQ mit Punktnotation.

Answer 2

Ja, der allgemeine Fall ist immer O (n), wie Sklivvz sagte.

Doch viele LINQ Methoden Sonderfall für, wenn das Objekt IEnumerable Implementierung zum Beispiel tatsächlich implementiert ICollection. (Ich habe dies zumindest für IEnumerable.Contains gesehen.)

In der Praxis bedeutet dies, dass LINQ IEnumerable.Contains die schnellen HashSet.Contains zum Beispiel Anrufe, wenn die IEnumerable tatsächlich ein HashSet ist.

IEnumerable<int> mySet = new HashSet<int>();

// calls the fast HashSet.Contains because HashSet implements ICollection.
if (mySet.Contains(10)) { /* code */ }

Sie Reflektor verwenden können, genau zu prüfen, wie die LINQ Methoden definiert sind, das ist, wie ich das herausgefunden.

Oh, und auch LINQ enthält Methoden IEnumerable.ToDictionary (Karten Schlüssel zum Einzelwert) und IEnumerable.ToLookup (Karten Taste, um mehrere Werte). Dieses Wörterbuch / Lookup-Tabelle einmal erstellt und mehrfach verwendet werden können, was einige LINQ intensiven Code um Größenordnungen beschleunigen kann.

Answer 3

Ja, es hat zu sein, weil die einzige Möglichkeit, ein beliebiges Mitglied einer IEnumerable des Zugreifens durch die Verwendung seiner Methoden ist, was bedeutet, O (n).

Es scheint wie ein klassischer Fall, in dem die Sprachdesigner entschieden Leistung für Allgemeinheit zu handeln.