Perché IEnumerable slow e List è veloce?

È venuto attraverso questo codice.

var dic = new Dictionary(); for(int i=0; i f.Value.StartsWith("1")).Select(f => f.Key);//.ToList(); //uncomment for fast results Console.WriteLine(list.GetType()); var list2 = dic.Where(f => list.Contains(f.Key)).ToList(); Console.WriteLine(list2.Count()) 

Quindi, quando .ToList () viene commentato, è lento, quando non è – è veloce. Riproducibile qui Come si potrebbe spiegare questo? Devo sempre rendere tutto ToList () per garantire la velocità (cioè in quali circostanze IEnumerable sarebbe più preferibile)? Nota Sto parlando solo di linq per gli oggetti, so linq per la pigrizia e tutto il resto.

Questo a causa dell’esecuzione posticipata : quando commentate ToList , l’enumerazione viene prodotta valutando la sequenza di filtri per ciascun elemento nel dizionario. Quando ToList una ToList , tuttavia, la sequenza viene “materializzata” in memoria, quindi tutte le valutazioni vengono eseguite esattamente una volta.

La logica dietro al secondo Where senza ToList presenta così:

 // The logic is expanded for illustration only. var list2 = new List>(); foreach (var d in dict) { var list = new List(); // This nested loop does the same thing on each iteration, // redoing n times what could have been done only once. foreach (var f in dict) { if (f.Value.StartsWith("1")) { list.Add(f.Key); } } if (list.Contains(d.Key)) { list2.Add(d); } } 

La logica con ToList è simile alla seguente:

 // The list is prepared once, and left alone var list = new List(); foreach (var f in dict) { if (f.Value.StartsWith("1")) { list.Add(f.Key); } } var list2 = new List>(); // This loop uses the same list in all its iterations. foreach (var d in dict) { if (list.Contains(d.Key)) { list2.Add(d); } } 

Come puoi vedere, ToList trasforma un programma O(n^2) con due cicli nidificati di dimensione n in O(2*n) con due cicli sequenziali di dimensione n ciascuno.

LINQ utilizza l’ esecuzione posticipata .
A meno che non si chiami .ToList() , i risultati di una query non vengono mai memorizzati da nessuna parte; al contrario, reiterera la query ogni volta che iterate i risultati.

Normalmente, questo è molto più veloce; di solito non c’è motivo di memorizzare prima tutti i risultati in memoria.

Tuttavia, il tuo codice ripetutamente itera la query; una volta per ogni chiamata al callback di Where() .

Dovresti sostituire quella linea con una chiamata Join() e senza ToList() , che sarà più veloce di entrambi gli approcci.

Perché quando non si ha la chiamata .ToList() , l’istanza list2 itererà attraverso l’intera list enumerabile per ogni voce nel dizionario. Quindi vai da O (n) a O (n ^ 2) se usi l’esecuzione differita.

È causato da un’esecuzione differita. IEnumerable non deve essere una raccolta statica. Generalmente si tratta di una fonte di dati ( dic nel tuo caso) + tutti i metodi e le espressioni (Where, Contains, ecc.) Che portano al set finale.

.ToList () esegue tutti questi metodi ed espressioni e genera il risultato finale.

Quindi, nel caso in cui tu usi ToList (), genera un elenco .NET standard (array di interi) e fa tutte le operazioni su quell’elenco.

Se non si chiama ToList () (o qualsiasi altro metodo To), IEnumerable può essere enumerato più volte.