Jakie są gwarancje dotyczące złożoności w czasie wykonywania (Big-O) metod LINQ?

Niedawno zacząłem używać LINQ całkiem sporo i tak naprawdę nie widziałem żadnej wzmianki o złożoności czasu wykonywania żadnej z metod LINQ. Oczywiście w grę wchodzi wiele czynników, więc ograniczmy dyskusję do zwykłego IEnumerabledostawcy LINQ-to-Objects. Dalej, załóżmy, że każda Funcprzekazana jako selektor / mutator / itp. Jest tanią operacją O (1).

Jest oczywiste, że wszystkie te operacje są jedno-przepływowe ( Select, Where, Count, Take/Skip, Any/All, etc.), można O (N), ponieważ wystarczy chodzić sekwencję raz; chociaż nawet to podlega lenistwu.

W przypadku bardziej złożonych operacji sytuacja jest bardziej mętna; zestaw podobny operatorów ( Union, Distinct, Except, itd.), praca przy użyciu GetHashCodedomyślnie (AFAIK), więc wydaje się rozsądne, aby założyć, że używasz hash-table wewnętrznie, co czyni te operacje O (n), jak również, w ogóle. A co z wersjami, które używają IEqualityComparer?

OrderBypotrzebowałby sortowania, więc najprawdopodobniej patrzymy na O (n log n). A jeśli jest już posortowane? A jeśli powiem OrderBy().ThenBy()i podam ten sam klucz do obu?

Widziałem GroupBy(i Join) używając sortowania lub mieszania. Który to jest?

Containsbyłoby O (n) na a List, ale O (1) na a HashSet- czy LINQ sprawdza podstawowy kontener, aby sprawdzić, czy może przyspieszyć działanie?

I prawdziwe pytanie - do tej pory wierzyłem, że operacje są skuteczne. Czy mogę jednak na to liczyć? Na przykład kontenery STL jasno określają złożoność każdej operacji. Czy istnieją podobne gwarancje wydajności LINQ w specyfikacji biblioteki .NET?

Więcej pytań (w odpowiedzi na komentarze): Tak
naprawdę nie myślałem o narzutach, ale nie spodziewałem się, że będzie wiele dla prostych Linq-to-Objects. W poście CodingHorror jest mowa o Linq-to-SQL, w którym rozumiem, że analizowanie zapytania i tworzenie SQL zwiększyłoby koszty - czy dostawca obiektów ma podobny koszt? Jeśli tak, czy jest inaczej, jeśli używasz składni deklaratywnej lub funkcjonalnej?

Gwarancji jest bardzo, bardzo niewiele, ale jest kilka optymalizacji:

• Rozszerzenie metod, które używają indeksowanego dostępu, takie jak ElementAt, Skip, Lastlub LastOrDefault, sprawdzi, czy zaistniałych typu narzędzi IList<T>, aby uzyskać O (1) Dostęp zamiast O (n).

• Do Countkontroli sposobu do ICollectionrealizacji tak, że ta operacja jest O (1) zamiast O (n).

• Distinct, GroupBy JoinI wierzę również sposoby zestaw agregacji ( Union, Intersecti Except) stosowanie hashowania, więc powinny być zbliżone do O (N) zamiast O (N²).

• Containssprawdza ICollectionimplementację, więc może to być O (1), jeśli bazowa kolekcja jest również O (1), na przykład a HashSet<T>, ale zależy to od faktycznej struktury danych i nie jest gwarantowane. Hash sety przesłaniają Containsmetodę, dlatego mają wartość O (1).

• OrderBy metody używają stabilnego szybkiego sortowania, więc są średnim przypadkiem O (N log N).

Myślę, że obejmuje to większość, jeśli nie wszystkie, wbudowane metody rozszerzające. Naprawdę jest bardzo niewiele gwarancji wydajności; Sam Linq spróbuje wykorzystać wydajne struktury danych, ale nie jest to wolny przebieg do napisania potencjalnie nieefektywnego kodu.

Od dawna wiem, że .Count()zwraca, .Countjeśli wyliczenie to IList.

Ale zawsze byłem nieco zmęczony o złożoności czasu wykonywania operacji Set: .Intersect(), .Except(), .Union().

Oto dekompilowana implementacja BCL (.NET 4.0 / 4.5) dla .Intersect()(moje komentarze):

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;
  }
}

Wnioski:

• wydajność to O (M + N)
• implementacja nie odnosi korzyści, gdy kolekcje są już ustawione . (To niekoniecznie musi być proste, ponieważ użyte IEqualityComparer<T>również musi pasować).

Aby uzyskać kompletność, oto implementacje dla .Union()i .Except().

Uwaga spoiler: one również mają złożoność O (N + M) .

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;
  }
}

Wszystko, na co możesz naprawdę liczyć, to to, że metody Enumerable są dobrze napisane dla ogólnego przypadku i nie będą używać naiwnych algorytmów. Prawdopodobnie istnieją materiały osób trzecich (blogi itp.), Które opisują faktycznie używane algorytmy, ale nie są one oficjalne ani gwarantowane w takim sensie, jak algorytmy STL.

Aby to zilustrować, oto odzwierciedlony kod źródłowy (dzięki uprzejmości ILSpy) Enumerable.Countz 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;
    }
}

Jak widać, trzeba się postarać, aby uniknąć naiwnego rozwiązania polegającego na prostym wyliczeniu każdego elementu.

Właśnie wyłamałem reflektor i sprawdzają podstawowy typ, kiedy Containszostanie wywołany.

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);
}

Prawidłowa odpowiedź brzmi „to zależy”. zależy to od typu bazowego IEnumerable. Wiem, że w przypadku niektórych kolekcji (takich jak kolekcje, które implementują ICollection lub IList) są używane specjalne ścieżki kodowe, jednak rzeczywista implementacja nie gwarantuje nic specjalnego. na przykład wiem, że ElementAt () ma specjalny przypadek dla indeksowanych kolekcji, podobnie jak Count (). Ale generalnie powinieneś prawdopodobnie założyć wydajność O (n) w najgorszym przypadku.

Ogólnie rzecz biorąc, nie sądzę, abyś znalazł taki rodzaj gwarancji wydajności, jaki chcesz, ale jeśli napotkasz konkretny problem z wydajnością z operatorem linq, zawsze możesz go ponownie zaimplementować do swojej konkretnej kolekcji. Istnieje również wiele blogów i projektów rozszerzających, które rozszerzają Linq na Objects w celu dodania tego rodzaju gwarancji wydajności. sprawdź indeksowane LINQ, które rozszerza i dodaje do zestawu operatora, aby uzyskać więcej korzyści związanych z wydajnością.