Quali garanzie ci sono sulla complessità in fase di esecuzione (Big-O) dei metodi LINQ?

Question

Recentemente ho iniziato ad usare LINQ un bel po ', e non ho davvero visto alcuna menzione di run-time la complessità per uno dei metodi di LINQ. Ovviamente, ci sono molti fattori in gioco qui, quindi cerchiamo di limitare la discussione al fornitore di pianura IEnumerable LINQ to Objects. Inoltre, supponiamo che qualsiasi Func passato come selettore/mutatore/ecc. Sia un'operazione O (1) economica.

Appare evidente che tutte le operazioni single-pass (Select, Where, Count, Take/Skip, Any/All, ecc) sarà O (n), in quanto solo bisogno di percorrere la sequenza una volta; anche se questo è soggetto alla pigrizia.

Le cose sono più torbida per le operazioni più complesse; gli operatori set-like (Union, Distinct, Except, ecc.) funzionano utilizzando GetHashCode per impostazione predefinita (afaik), quindi sembra ragionevole supporre che stiano utilizzando internamente una tabella hash, rendendo anche queste operazioni O (n), in generale. Che dire delle versioni che utilizzano uno IEqualityComparer?

OrderBy avrebbe bisogno di una specie, quindi molto probabilmente stiamo guardando O (n log n). Cosa succede se è già stato ordinato? Che ne dici se io dico OrderBy().ThenBy() e fornire la stessa chiave per entrambi?

Ho potuto vedere GroupBy (e Join) utilizzando l'ordinamento o l'hashing. Cos'è questo?

Contains sarebbe O (n) su un List, ma O (1) su un HashSet - fa controllare LINQ il contenitore sottostante per vedere se può accelerare le cose?

E la vera domanda - finora, ho preso sulla fede che le operazioni sono performante. Tuttavia, posso fare affidamento su quello? I contenitori STL, ad esempio, specificano chiaramente la complessità di ogni operazione. Esistono garanzie simili sulle prestazioni LINQ nelle specifiche della libreria .NET?

Altre domande (in risposta ai commenti):
Non avevo davvero pensato a spese generali, ma non mi aspettavo che ci fosse molto per i semplici Linq-to-Objects. Il post di CodingHorror parla di Linq-to-SQL, dove posso capire l'analisi della query e fare in modo che SQL aggiunga costi: c'è un costo simile anche per il fornitore di oggetti? Se è così, è diverso se stai usando la sintassi dichiarativa o funzionale?

Answer 1

ci sono pochissime garanzie, ma ci sono alcune ottimizzazioni: metodi

• estensione che utilizzano l'accesso indicizzato, come ElementAt, Skip, Last o LastOrDefault, verificherà indipendentemente dal fatto che il tipo sottostante implementa IList<T>, in modo da ottenere l'accesso O (1) anziché O (N).

• I controlli Count metodo per un ICollection attuazione, in modo che questa operazione è O (1) invece di O (N).

• Distinct, GroupByJoin, e ritengo anche i metodi set-aggregazione (Union, Intersect e Except) usa l'hashing, così che dovrebbe essere vicino a O (N) invece di O (n²).

• Contains controlla per un ICollection attuazione, quindi è può O (1) se la raccolta sottostante è anche O (1), quale un HashSet<T>, ma questo è dipende dalla struttura dati effettivi e non è garantita. I set di hash sovrascrivono il metodo Contains, ecco perché sono O (1).

• OrderBy metodi utilizzano un quicksort stabile, quindi sono O (N log N) nel caso medio.

Penso che riguardi la maggior parte se non tutti i metodi di estensione incorporati. Ci sono davvero pochissime garanzie sulle prestazioni; Linq stesso cercherà di sfruttare strutture di dati efficienti ma non è un passaggio libero per scrivere codice potenzialmente inefficiente.

Answer 2

Tutto ciò che si può realmente contare è che i metodi Enumerable sono ben scritti per il caso generale e non utilizzano algoritmi ingenui. Probabilmente ci sono cose di terze parti (blog, ecc.) Che descrivono gli algoritmi effettivamente in uso, ma questi non sono ufficiali o garantiti nel senso che sono gli algoritmi STL.

Per illustrare, ecco il codice sorgente di riflesso (per gentile concessione di ILSpy) per Enumerable.Count da 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; 
    } 
} 

Come si può vedere, va a un certo sforzo per evitare la soluzione ingenua del semplice enumerazione ogni elemento

Answer 3

ho appena scoppiata riflettore e fanno controllare il tipo sottostante quando Contains è chiamato.

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

La risposta corretta è "dipende". dipende da che tipo è il sottostante IEnumerable. so che per alcune raccolte (come le raccolte che implementano ICollection o IList) ci sono speciali codepath che vengono usati, tuttavia l'implementazione effettiva non è garantita per fare qualcosa di speciale. per esempio, so che ElementAt() ha un caso speciale per le collezioni indicizzabili, analogamente a Count(). Ma in generale dovresti probabilmente assumere la peggiore performance O (n).

In generale, non penso che si possa trovare il tipo di garanzie sulle prestazioni desiderate, anche se si incontra un particolare problema di prestazioni con un operatore linq, è sempre possibile reimplementarlo per la propria raccolta specifica. Inoltre ci sono molti blog e progetti di estensibilità che estendono Linq agli oggetti per aggiungere questo tipo di garanzie sulle prestazioni. controlla Indexed LINQ che si estende e aggiunge all'operatore set per maggiori prestazioni.

Answer 5

ho da tempo che .Count() restituisce .Count se l'enumerazione è un IList.

Ma ero sempre un po 'stanco della complessità di runtime delle operazioni di Set: .Intersect(), .Except(), .Union().

Ecco il BCL decompilato (.NET 4.0/4.5) attuazione per .Intersect() (commenti mio):

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

Conclusioni:

• le prestazioni sono O (M + N)
• l'attuazione non significa approfittare quando le collezioni sono già insiemi. (Potrebbe non essere necessariamente semplice, perché il utilizzato IEqualityComparer<T> deve anche corrispondere.)

Per completezza, ecco le implementazioni per .Union() e .Except().

Avviso spoiler: anche loro hanno O (N + M) complessità.

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