Trova () vs. enumerazione negli elenchi

Question

Sto lavorando con una base di codice in cui è necessario cercare frequentemente gli elenchi per un singolo elemento.

È più veloce usare un Predicato e Trova () che fare manualmente un elenco sull'Elenco?

ad esempio:

string needle = "example";
FooObj result = _list.Find(delegate(FooObj foo) {
    return foo.Name == needle;
});

vs.

string needle = "example";
foreach (FooObj foo in _list)
{
    if (foo.Name == needle)
        return foo;
}

Sebbene siano equivalenti in termini di funzionalità, sono equivalenti anche in termini di prestazioni?

Answer 1

Non sono equivalenti nelle prestazioni. Il metodo Find () richiede un metodo (in questo caso delegato) invocazione per ogni elemento nell'elenco. L'invocazione del metodo non è gratuita ed è relativamente costosa rispetto a un confronto in linea. La versione foreach non richiede invocazioni di metodi aggiuntivi per oggetto.

Detto questo, non sceglierei l'uno o l'altro in base alle prestazioni fino a quando non ho effettivamente profilato il mio codice e ho scoperto che questo era un problema. Non ho ancora trovato il sovraccarico di questo scenario per essere un "percorso caldo". problema per il codice che ho scritto e uso molto questo modello con Trova e altri metodi simili.

Answer 2

Se la ricerca nell'elenco è troppo lenta così com'è, probabilmente puoi fare di meglio di una ricerca lineare. Se riesci a mantenere ordinato l'elenco, puoi utilizzare una ricerca binaria per trovare l'elemento in O (lg n) time.

Se stai cercando un lotto intero , considera di sostituire tale elenco con un dizionario per indicizzare i tuoi oggetti per nome.

Answer 3

Tecnicamente, le prestazioni di runtime della versione delegata saranno leggermente peggiori rispetto all'altra versione, ma nella maggior parte dei casi sarebbe difficile trovare una differenza.

Di maggiore importanza (IHMO) è la prestazione del tempo in codice di poter scrivere quello che vuoi, piuttosto che come lo desideri. Questo fa una grande differenza nella manutenibilità.

Questo codice originale:

string needle = "example";
foreach (FooObj foo in _list)
{
    if (foo.Name == needle)        
        return foo;
}

richiede a qualsiasi manutentore di leggere il codice e capire che stai cercando un elemento particolare.

Questo codice

string needle = "example";
return _list.Find(
    delegate(FooObj foo) 
    {
        return foo.Name == needle;
    });

chiarisce che stai cercando un elemento particolare, più veloce da capire.

Infine, questo codice, usando le funzionalità di C # 3.0:

string needle = "example";
return _list.Find( foo => foo.Name == needle);

fa esattamente la stessa cosa, ma in una riga è ancora più veloce da leggere e capire (beh, una volta capito espressioni lambda , comunque).

In breve, dato che le prestazioni delle alternative sono quasi uguali, scegli quella che semplifica la lettura e la manutenzione del codice.

Answer 4

" Sto lavorando con una base di codice in cui elenchi deve essere cercato frequentemente per un singolo elemento "

È meglio cambiare la struttura dei dati in Dizionario anziché Elenco per ottenere prestazioni migliori

Answer 5

Una domanda simile è stata posta per List.ForEach vs. foreach-iteration ( foreach vs someList.Foreach () {} ).

In quel caso List.ForEach è stato un po 'più veloce.

Answer 6

Come sottolineato da Jared, ci sono differenze.

Ma, come sempre, non preoccuparti se non sai che è un collo di bottiglia. E se si tratta di un collo di bottiglia, probabilmente perché gli elenchi sono grandi, nel qual caso dovresti considerare di usare una ricerca più veloce - una tabella hash o un albero binario, o anche solo ordinare l'elenco e fare una ricerca binaria ti darà il log (n) prestazioni che avranno un impatto molto maggiore rispetto all'ottimizzazione del case lineare.