Prestazioni LINQ in memoria

Question

Più che su LINQ per [inserire qui il tuo provider preferito], questa domanda riguarda la ricerca o il filtraggio di raccolte in memoria.

So che LINQ (o cerca / filtra i metodi di estensione) funziona negli oggetti che implementano IEnumerable o IEnumerable<T>. La domanda è: a causa della natura dell'enumerazione, ogni complessità della query è almeno O(n)?

Ad esempio:

var result = list.FirstOrDefault(o => o.something > n);

In questo caso, ogni algoritmo impiegherà almeno O (n) a meno che list sia ordinato rispetto a 'something', nel qual caso la ricerca dovrebbe richiedere O (log (n)) : dovrebbe essere una ricerca binaria. Tuttavia, se ho capito bene, questa query verrà risolta tramite l'enumerazione, quindi dovrebbe richiedere O (n) , anche in <=> era stata precedentemente ordinata.

• C'è qualcosa che posso fare per risolvere una query in O (log (n)) ?
• Se voglio prestazioni, dovrei usare Array.Sort e Array.BinarySearch?

Answer 1

Anche con la parallelizzazione, è ancora O (n). Il fattore costante sarebbe diverso (a seconda del numero di core) ma, poiché variava, il tempo totale varierebbe comunque in modo lineare.

Ovviamente, potresti scrivere le tue implementazioni dei vari operatori LINQ sui tuoi tipi di dati, ma sarebbero appropriate solo in situazioni molto specifiche - dovresti sapere con certezza che il predicato operava solo sul aspetti ottimizzati dei dati. Ad esempio, se hai un elenco di persone ordinate per età, non ti aiuterà con una query che cerca di trovare qualcuno con un nome particolare :)

Per esaminare il predicato, dovresti usare gli alberi delle espressioni invece dei delegati e la vita diventerebbe molto più difficile.

Sospetto che normalmente aggiungerei nuovi metodi che rendono ovvio che stai usando la natura indicizzata / ordinata / qualunque sia il tipo di dati e che funzionerà sempre in modo appropriato. Ovviamente non puoi facilmente invocare quei metodi extra dalle espressioni di query, ma puoi comunque usare LINQ con la notazione a punti.

Answer 2

Sì, il caso generico è sempre O (n), come ha detto Sklivvz.

Tuttavia, molti metodi LINQ rappresentano un caso particolare quando l'oggetto che implementa IEnumerable implementa effettivamente, ad es. ICollection. (L'ho visto per IEnumerable.Contains almeno.)

In pratica ciò significa che LINQ IEnumerable.Contains chiama il veloce HashSet.Contains, ad esempio, se IEnumerable in realtà è un HashSet.

IEnumerable<int> mySet = new HashSet<int>();

// calls the fast HashSet.Contains because HashSet implements ICollection.
if (mySet.Contains(10)) { /* code */ }

Puoi usare il riflettore per verificare esattamente come sono definiti i metodi LINQ, ecco come l'ho capito.

Oh, e anche LINQ contiene i metodi IEnumerable.ToDictionary (associa la chiave al singolo valore) e IEnumerable.ToLookup (associa la chiave a più valori). Questa tabella di dizionario / ricerca può essere creata una volta e utilizzata più volte, il che può accelerare il codice ad alta intensità di LINQ per ordini di grandezza.

Answer 3

Sì, lo è, perché l'unico modo per accedere a qualsiasi membro di un IEnumerable è usando i suoi metodi, il che significa O (n).

Sembra un caso classico in cui i progettisti del linguaggio hanno deciso di scambiare prestazioni per generalità.