wake-up-neo.com

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

Ich habe vor kurzem angefangen, LINQ ziemlich oft zu verwenden, und ich habe bei keiner der LINQ-Methoden wirklich eine Erwähnung der Laufzeitkomplexität 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, die als Selektor/Mutator/etc. übergeben wird, eine billige O(1) Operation ist.

Es ist offensichtlich, dass alle Operationen mit einem Durchgang (Select, Where, Count, Take/Skip, Any/All Usw.) ausgeführt werden sei O (n), da sie die Sequenz nur einmal durchlaufen müssen; obwohl auch dies faulheit unterliegt.

Für komplexere Operationen sind die Dinge trüber; Die set-ähnlichen Operatoren (Union, Distinct, Except usw.) arbeiten standardmäßig mit GetHashCode (afaik) Sie verwenden intern eine Hash-Tabelle und führen diese Operationen O(n) im Allgemeinen auch aus. Was ist mit den Versionen, die ein IEqualityComparer verwenden?

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() sage und für beide den gleichen Schlüssel gebe?

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

Contains wäre O(n) auf einem List, aber O(1) auf einem HashSet - prüft LINQ der zugrunde liegende Container, um zu sehen, ob es Dinge beschleunigen kann?

Und die eigentliche Frage: Bisher habe ich davon ausgegangen, dass die Operationen erfolgreich sind. Darauf kann ich mich jedoch verlassen? Beispielsweise geben STL-Container die Komplexität jedes Vorgangs eindeutig an. Gibt es ähnliche Garantien für die LINQ-Leistung in der .NET-Bibliotheksspezifikation?

Weitere Fragen (als Antwort auf Kommentare):
Hatte nicht wirklich über Overhead nachgedacht, aber ich hatte nicht erwartet, dass es sehr viel für einfache Linq-to-Objects geben würde. In dem CodingHorror-Beitrag geht es um Linq-to-SQL, wo ich verstehen kann, dass das Parsen der Abfrage und das Durchführen von SQL zusätzliche Kosten verursachen würde. Gibt es auch ähnliche Kosten für den Objektanbieter? Wenn ja, ist es anders, wenn Sie die deklarative oder funktionale Syntax verwenden?

108
tzaman

Es gibt nur sehr wenige Garantien, aber einige Optimierungen:

  • Erweiterungsmethoden, die indizierten Zugriff verwenden, z. B. ElementAt, Skip, Last oder LastOrDefault, prüfen, ob der zugrunde liegende Typ implementiert _IList<T>_, so dass Sie O(1) Zugriff anstelle von O (N) erhalten.

  • Die Methode Count sucht nach einer Implementierung von ICollection, sodass diese Operation O(1) anstelle von O (N) ist.

  • Distinct, GroupByJoin und meiner Meinung nach auch die Mengenaggregationsmethoden (Union, Intersect und Except ) verwende Hashing, daher sollten sie in der Nähe von O(N) anstelle von O (N²) liegen.

  • Contains sucht nach einer ICollection - Implementierung. Es ist also kann O(1), wenn die zugrunde liegende Auflistung auch O (1) ist ), z. B. _HashSet<T>_, dies hängt jedoch von der tatsächlichen Datenstruktur ab und kann nicht garantiert werden. Hash-Sätze überschreiben die Methode Contains, daher sind sie O (1).

  • OrderBy -Methoden verwenden eine stabile Quicksortierung, daher handelt es sich um O (N log N) -Durchschnittsfälle.

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

107
Aaronaught

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 Sachen von Drittanbietern (Blogs usw.), die die tatsächlich verwendeten Algorithmen beschreiben, aber diese sind nicht offiziell oder garantiert in dem Sinne, wie es STL-Algorithmen sind.

Zur Veranschaulichung hier der reflektierte Quellcode (mit freundlicher Genehmigung von ILSpy) für Enumerable.Count von 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, ist es ein gewisser Aufwand, die naive Lösung zu vermeiden, einfach jedes Element aufzuzählen.

8
Marcelo Cantos

Ich habe lange gewusst, dass .Count().Count zurückgibt, wenn die Aufzählung ein IList ist.

Aber ich war immer ein bisschen müde von der Laufzeitkomplexität der Set-Operationen: .Intersect(), .Except(), .Union().

Hier ist die dekompilierte BCL (.NET 4.0/4.5) -Implementierung 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 den Vorteil nicht , wenn die Sammlungen bereits festgelegt sind. (Dies ist möglicherweise nicht unbedingt einfach, da der verwendete IEqualityComparer<T> ebenfalls übereinstimmen muss.)

Der Vollständigkeit halber hier die Implementierungen für .Union() und .Except().

Spoiler-Alarm: Auch sie haben 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;
  }
}
8

Ich habe gerade den Reflektor ausgebrochen 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);
}
3
ChaosPandion

Die richtige Antwort lautet "es kommt darauf an". Dies hängt davon ab, um welchen Typ es sich bei der zugrunde liegenden IEnumerable handelt. Ich weiß, dass für einige Sammlungen (wie Sammlungen, die ICollection oder IList implementieren) spezielle Codepfade verwendet werden. Es ist jedoch nicht garantiert, dass die tatsächliche Implementierung etwas Besonderes bewirkt. Ich weiß zum Beispiel, dass ElementAt () einen Sonderfall für indizierbare Auflistungen hat, ähnlich wie Count (). Aber im Allgemeinen sollten Sie wahrscheinlich den schlimmsten Fall annehmen O(n) Leistung.

Im Allgemeinen glaube ich nicht, dass Sie die Art von Leistungsgarantien finden werden, die Sie wollen, aber wenn Sie mit einem Linq-Operator auf ein bestimmtes Leistungsproblem stoßen, können Sie es immer nur für Ihre bestimmte Sammlung neu implementieren. Es gibt auch viele Blogs und Erweiterungsprojekte, die Linq to Objects erweitern, um diese Art von Leistungsgarantien hinzuzufügen. check out Indexed LINQ erweitert und erweitert den Operator-Set, um weitere Leistungsvorteile zu erzielen.

3
luke