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

120

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 IEnumerableLINQ-to-Objects-Anbieter. Nehmen wir weiter an, dass jede Funcals 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 GetHashCodeder 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?

OrderBywü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?

Containswä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?

Zaman
quelle
Obwohl ich Ihre Frage nicht wirklich beantworten kann, möchte ich darauf hinweisen, dass der größte Teil der Leistung im Vergleich zur Kernfunktionalität im Allgemeinen "Overhead" ist. Dies ist natürlich nicht der Fall, wenn Sie sehr große Datenmengen (> 10.000 Elemente) haben, also bin ich neugierig, in welchem ​​Fall Sie wissen möchten.
Henri
2
Betreff: "Ist es anders, wenn Sie die deklarative oder funktionale Syntax verwenden?" - Der Compiler übersetzt die deklarative Syntax in die funktionale Syntax, sodass sie identisch sind.
John Rasch
"STL-Container geben die Komplexität jeder Operation klar an" .NET-Container geben auch die Komplexität jeder Operation klar an. Linq-Erweiterungen ähneln STL-Algorithmen, nicht STL-Containern. Genau wie beim Anwenden eines STL-Algorithmus auf einen STL-Container müssen Sie die Komplexität der Linq-Erweiterung mit der Komplexität der .NET-Containeroperationen kombinieren, um die resultierende Komplexität ordnungsgemäß zu analysieren. Dies schließt die Berücksichtigung von Vorlagenspezialisierungen ein, wie in der Antwort von Aaronaught erwähnt.
Timbo
Eine zugrunde liegende Frage ist, warum Microsoft nicht mehr besorgt war, dass eine IList <T> -Optimierung von begrenztem Nutzen sein würde, da sich ein Entwickler auf undokumentiertes Verhalten verlassen müsste, wenn sein Code davon abhängen würde, um performant zu sein.
Edward Brey
AsParallel () in der resultierenden Mengenliste; sollte Ihnen ~ O (1) <O (n)
Latenz

Antworten:

121

Es gibt sehr, sehr wenige Garantien, aber einige Optimierungen:

  • Erweiterungsmethoden , die einen Index den Zugriff verwenden, wie ElementAt, Skip, Lastoder LastOrDefault, prüft , ob die zugrunde liegenden Typ implementiert , um zu sehen IList<T>, so dass Sie erhalten , O (1) Zugang anstelle von O (N).

  • Die CountMethode sucht nach einer ICollectionImplementierung, sodass diese Operation O (1) anstelle von O (N) ist.

  • Distinct, GroupBy JoinGlaube, und ich auch die Set-Aggregationsverfahren ( Union, Intersectund Except) Verwendung Hashing, so dass sie nahe an O (N) sein sollten anstelle von O (N²).

  • Containsprüft auf eine ICollectionImplementierung, daher kann es O (1) sein, wenn die zugrunde liegende Sammlung auch O (1) ist, wie z. B. a HashSet<T>, dies hängt jedoch von der tatsächlichen Datenstruktur ab und ist nicht garantiert. Hash-Sets überschreiben die ContainsMethode, 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.

Aaronaught
quelle
Wie wäre es mit den IEqualityComparerÜberlastungen?
Zaman
@tzaman: Was ist mit ihnen? Wenn Sie keinen wirklich ineffizienten Brauch verwenden IEqualityComparer, kann ich nicht begründen, dass dies die asymptotische Komplexität beeinflusst.
Aaronaught
1
Oh, richtig. Ich hatte EqualityComparerGeräte nicht GetHashCodeso gut realisiert wie Equals; Aber das macht natürlich Sinn.
Zaman
2
@imgen: Schleifenverknüpfungen sind O (N * M), was für nicht verwandte Mengen auf O (N²) verallgemeinert wird. Linq verwendet Hash-Joins, die O (N + M) sind und auf O (N) verallgemeinert werden. Das setzt eine halbwegs anständige Hash-Funktion voraus, aber das ist in .NET schwer zu vermasseln.
Aaronaught
1
ist Orderby().ThenBy()still N logNoder ist es (N logN) ^2oder so ähnlich?
M. Kazem Akhgary 20.
10

Ich habe lange gewusst, dass das .Count()zurückkehrt, .Countwenn die Aufzählung eine ist IList.

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):

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 ist O (M + N)
  • Die Implementierung nutzt nicht aus , wenn die Sammlungen bereits festgelegt sind . (Es muss nicht unbedingt einfach sein, da das verwendete 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.

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;
  }
}
Cristian Diaconescu
quelle
8

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.Countvon System.Core:

// 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, ist es eine Anstrengung, die naive Lösung zu vermeiden, einfach jedes Element aufzuzählen.

Marcelo Cantos
quelle
Das ganze Objekt zu durchlaufen, um Count () zu erhalten, wenn es sich um eine IEnnumerable handelt, scheint mir ziemlich naiv zu sein ...
Zonko
4
@ Zonko: Ich verstehe deinen Standpunkt nicht. Ich habe meine Antwort geändert, um zu zeigen, dass Enumerable.Countsie nicht iteriert, es sei denn, es gibt keine offensichtliche Alternative. Wie hätten Sie es weniger naiv gemacht?
Marcelo Cantos
Ja, die Methoden werden in Anbetracht der Quelle am effizientesten implementiert. Der effizienteste Weg ist jedoch manchmal ein naiver Algorithmus, und man sollte bei der Verwendung von linq vorsichtig sein, da er die tatsächliche Komplexität von Aufrufen verbirgt. Wenn Sie mit der zugrunde liegenden Struktur der Objekte, die Sie bearbeiten, nicht vertraut sind, können Sie leicht die falschen Methoden für Ihre Anforderungen verwenden.
Zonko
@MarceloCantos Warum werden Arrays nicht behandelt? Es ist das gleiche für ElementAtOrDefault Verfahren referencesource.microsoft.com/#System.Core/System/Linq/...
Freshblood sorgt
@ Frischblut Sie sind. (Arrays implementieren ICollection.) Sie kennen ElementAtOrDefault jedoch nicht. Ich vermute, Arrays implementieren auch ICollection <T>, aber mein .Net ist heutzutage ziemlich verrostet.
Marcelo Cantos
3

Ich habe gerade einen Reflektor ausgebrochen und sie überprüfen den zugrunde liegenden Typ, wenn er Containsaufgerufen 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);
}
ChaosPandion
quelle
3

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.

Luke
quelle