Welche Garantien gibt es für die Laufzeitkomplexität (Big-O) der LINQ-Methoden?

Question

Ich habe vor kurzem begonnen, LINQ ziemlich zu verwenden, und ich habe wirklich keine Laufzeit-Komplexität für irgendeine der LINQ-Methoden erwähnt. Offensichtlich spielen hier viele Faktoren eine Rolle. Lassen Sie uns die Diskussion daher auf den einfachen LINQ to Objects-Provider beschränken. Nehmen wir weiterhin an, dass jede Func, die als Selektor/Mutator/etc. übergeben wird, eine billige O (1) -Operation ist.

Es scheint offensichtlich, dass alle Single-Pass-Operationen (Select, Where, Count, Take/Skip, Any/All usw.) O (n) sein, da sie brauchen nur die Sequenz gehen einmal; obwohl auch dies der Faulheit unterliegt.

Die Dinge sind düsterer für die komplexeren Operationen; die set-like Operatoren (Union, Distinct, Except, usw.) arbeiten standardmäßig mit GetHashCode (afaik), so dass es vernünftig anzunehmen scheint, dass sie intern eine Hashtabelle verwenden, wodurch diese Operationen auch O (n) sind. Im Algemeinen. Was ist mit den Versionen, die eine IEqualityComparer verwenden?

OrderBy würde eine Sortierung benötigen, also betrachten wir am wahrscheinlichsten O (n log n). Was ist, wenn es schon sortiert ist? Wie wäre es wenn ich sage OrderBy().ThenBy() und den gleichen Schlüssel für beide?

Ich konnte GroupBy (und Join) entweder Sortieren oder Hashing sehen. Welches ist es?

Contains würde O (n) auf einem List, aber O (1) auf einem HashSet sein - nicht überprüft LINQ die zugrunde liegenden Container zu sehen, ob es die Sache beschleunigen kann?

Und die eigentliche Frage - bis jetzt habe ich es auf dem Glauben genommen, dass die Operationen performant sind. Aber kann ich darauf bauen? Zum Beispiel legen STL-Container die Komplexität jeder Operation klar fest. Gibt es ähnliche Garantien für die LINQ-Leistung in der .NET-Bibliotheksspezifikation?

Weitere Frage (als Reaktion auf Kommentare):
Hatte nicht wirklich über Overhead gedacht, aber ich habe nicht erwartet, dass es sehr viel für einfache Linq-to-Objects zu sein. Der CodingHorror Post spricht über Linq-to-SQL, wo ich verstehen kann, die Abfrage zu analysieren und SQL würde Kosten hinzufügen - gibt es ähnliche Kosten für den Objects-Provider zu? Wenn ja, ist es anders, wenn Sie die deklarative oder funktionale Syntax verwenden?

Answer 1

Es gibt sehr, sehr wenige Garantien, aber es gibt ein paar Optimierungen:

• Erweiterungsmethoden, die einen Index den Zugriff verwenden, wie ElementAt, Skip, Last oder LastOrDefault, prüft, ob der zugrunde liegende Typ IList<T> implementiert oder nicht, sodass Sie O (1) -Zugriff anstelle von O (N) erhalten.

• Die Count Methode prüft auf eine ICollection Implementierung, so dass diese Operation O (1) anstelle von O (N) ist.

• Distinct, GroupByJoin, und ich glaube, auch die Set-Aggregationsverfahren (Union, Intersect und Except) verwenden Hashing, so sollten sie auf O (N) anstelle von O (N²) in der Nähe sein.

• Contains Kontrollen für eine ICollection Umsetzung, so dass es kann werden, um O (1), wenn der zugrunde liegende Sammel auch O (1) ist, wie ein HashSet<T>, aber dies ist, hängt von der Struktur tatsächlichen Daten und ist nicht garantiert. Hash-Sätze überschreiben die Contains-Methode, deshalb sind sie O (1).

• OrderBy Methoden verwenden einen stabilen Quicksort, so dass sie O (N log N) durchschnittlichen Fall sind.

Ich denke, dass die meisten, wenn nicht alle der integrierten Erweiterungsmethoden deckt. Es gibt wirklich sehr wenige Leistungsgarantien; Linq selbst wird versuchen, effiziente Datenstrukturen zu nutzen, aber es ist kein freier Durchgang, um potentiell ineffizienten Code zu schreiben.

Answer 2

Alles, worauf Sie wirklich bauen können, ist, dass die Enumerable-Methoden für den allgemeinen Fall gut geschrieben sind und keine naiven Algorithmen verwenden. Es gibt wahrscheinlich Sachen von Drittanbietern (Blogs usw.), die die tatsächlich verwendeten Algorithmen beschreiben, aber diese sind nicht offiziell oder in dem Sinne garantiert, dass STL-Algorithmen dies sind.

zu, hier ist das reflektierte Quellcode (mit freundlicher Genehmigung von ILSpy) für Enumerable.Count von System.Core zu illustrieren:

// System.Linq.Enumerable 
public static int Count<TSource>(this IEnumerable<TSource> source) 
{ 
    checked 
    { 
     if (source == null) 
     { 
      throw Error.ArgumentNull("source"); 
     } 
     ICollection<TSource> collection = source as ICollection<TSource>; 
     if (collection != null) 
     { 
      return collection.Count; 
     } 
     ICollection collection2 = source as ICollection; 
     if (collection2 != null) 
     { 
      return collection2.Count; 
     } 
     int num = 0; 
     using (IEnumerator<TSource> enumerator = source.GetEnumerator()) 
     { 
      while (enumerator.MoveNext()) 
      { 
       num++; 
      } 
     } 
     return num; 
    } 
} 

Wie Sie sehen können, geht es bis zu einem gewissen Aufwand die naive Lösung einfach zu vermeiden Aufzählen jedes Element.

Answer 3

Ich brach gerade Reflektor und sie überprüfen den zugrunde liegenden Typ, wenn Contains aufgerufen wird.

public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value) 
{ 
    ICollection<TSource> is2 = source as ICollection<TSource>; 
    if (is2 != null) 
    { 
     return is2.Contains(value); 
    } 
    return source.Contains<TSource>(value, null); 
} 

Answer 4

Die richtige Antwort ist "es kommt darauf an". Es hängt davon ab, welcher Typ das zugrunde liegende IEnumerable ist. Ich weiß, dass für einige Sammlungen (wie Sammlungen, die ICollection oder IList implementieren), spezielle Codepatches verwendet werden, aber die tatsächliche Implementierung ist nicht garantiert, etwas Besonderes zu tun. zum Beispiel weiß ich, dass ElementAt() einen speziellen Fall für indexierbare Sammlungen hat, ähnlich wie Count(). Aber im Allgemeinen sollten Sie wahrscheinlich die schlechteste O (n) Leistung annehmen.

Im Allgemeinen glaube ich nicht, dass Sie die Art von Leistungsgarantien finden werden, die Sie wollen, wenn Sie jedoch ein bestimmtes Leistungsproblem mit einem linq-Operator haben, können Sie es für Ihre bestimmte Sammlung immer einfach neu implementieren. Außerdem gibt es viele Blogs und Erweiterbarkeitsprojekte, die Linq auf Objekte erweitern, um diese Leistungsgarantien hinzuzufügen. Auschecken Indexed LINQ, die erweitert und fügt dem Operator für mehr Leistung Vorteile gesetzt.

Answer 5

Ich weiß seit langem, dass .Count().Count zurückgibt, wenn die Aufzählung ein IList ist.

Aber ich war immer etwas müde über die Laufzeit Komplexität der Set-Operationen: .Intersect(), .Except(), .Union().

Hier ist die dekompilierte BCL (.NET 4.0/4.5) Durchführung für .Intersect() (Kommentare von mir):

private static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer) 
{ 
    Set<TSource> set = new Set<TSource>(comparer); 
    foreach (TSource source in second)     // O(M) 
    set.Add(source);         // O(1) 

    foreach (TSource source in first)      // O(N) 
    { 
    if (set.Remove(source))        // O(1) 
     yield return source; 
    } 
} 

Schlussfolgerungen:

• die Leistung O (M + N)
• die Umsetzung hat nicht ausnutzen, wenn die Sammlungen bereits sind setzt. (Es kann nicht unbedingt einfach sein, weil die verwendete IEqualityComparer<T> auch übereinstimmen muss.)

Für Vollständigkeit, hier sind die Implementierungen für .Union() und .Except().

Spoiler Warnung: sie haben auch O (N + M) Komplexität.

private static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer) 
{ 
    Set<TSource> set = new Set<TSource>(comparer); 
    foreach (TSource source in first) 
    { 
    if (set.Add(source)) 
     yield return source; 
    } 
    foreach (TSource source in second) 
    { 
    if (set.Add(source)) 
     yield return source; 
    } 
} 


private static IEnumerable<TSource> ExceptIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer) 
{ 
    Set<TSource> set = new Set<TSource>(comparer); 
    foreach (TSource source in second) 
    set.Add(source); 
    foreach (TSource source in first) 
    { 
    if (set.Add(source)) 
     yield return source; 
    } 
}