Quale raccolta .NET fornisce la ricerca più veloce

Question

Ho 60k elementi che devono essere controllati rispetto a un elenco di ricerca 20k. Esiste un oggetto di raccolta (ad esempio List, HashTable) che fornisce un metodo eccezionalmente veloce Contains()? O dovrò scrivere il mio? In altre parole, è il metodo predefinito Contains() solo scansionare ogni elemento o utilizza un algoritmo di ricerca migliore.

foreach (Record item in LargeCollection) 
{ 
    if (LookupCollection.Contains(item.Key)) 
    { 
     // Do something 
    } 
} 

Nota. L'elenco di ricerca è già ordinato.

Answer 1

Nel caso più generale, considerare System.Collections.Generic.HashSet come la struttura di dati del cavallo di lavoro "Contiene" predefinita, poiché è necessario un tempo costante per valutare Contains.

La risposta effettiva a "Qual è la raccolta di ricerche più veloce" dipende dalle dimensioni dei dati, dall'ordinanza, dal costo di hashing e dalla frequenza di ricerca.

Answer 2

Se non avete bisogno di ordine, provare HashSet<Record> (di nuovo da 3,5 NET)

Se non, utilizza un List<Record> e chiamare BinarySearch.

Answer 3

Avete considerato List.BinarySearch(item)?

Hai detto che la tua vasta raccolta è già stata ordinata, quindi questa sembra l'occasione perfetta? Un hash sarebbe sicuramente il più veloce, ma questo comporta i suoi problemi e richiede molto più overhead per l'archiviazione.

Answer 4

Se non si è preoccupati di cigolare ogni singolo bit di prestazioni, il suggerimento di utilizzare una ricerca hash o binaria è solido. I tuoi set di dati non sono abbastanza grandi da rendere questo problema il 99% delle volte.

Ma se questo solo una delle migliaia di volte lo farai e le prestazioni sono critiche (e dimostrate inaccettabili usando HashSet/binary search), potresti sicuramente scrivere il tuo algoritmo che ha fatto il giro degli elenchi ordinati facendo confronti come sei andato Ogni lista dovrebbe essere percorsa al massimo una volta e nei casi patologici non sarebbe male (una volta percorsa questa rotta probabilmente si scoprirà che il confronto, supponendo che sia una stringa o altro valore non integrale, sarebbe la vera spesa e che ottimizzando quello sarebbe il prossimo passo).

Answer 5

Se è possibile ordinare i tuoi articoli, allora c'è un modo molto più veloce per fare questo, quindi fare ricerche chiave in un hashtable o b-tree. Anche se gli oggetti non sono ordinabili, non puoi comunque metterli in un b-tree.

In ogni caso, se ordinate ordinatamente entrambi gli elenchi, si tratta solo di percorrere l'elenco di ricerca in ordine.

Walk lookup list 
    While items in check list <= lookup list item 
    if check list item = lookup list item do something 
    Move to next lookup list item 

Answer 6

Se stai usando Net 3.5, è possibile rendere il codice più pulito utilizzando:

foreach (Record item in LookupCollection.Intersect(LargeCollection)) 
{ 
    //dostuff 
} 

io non ho Net 3.5 qui e quindi questo è non testati. Si basa su un metodo di estensione. Non è che LookupCollection.Intersect(LargeCollection) probabilmente non è lo stesso di LargeCollection.Intersect(LookupCollection) ... quest'ultimo è probabilmente molto più lento.

Questo presuppone LookupCollection è un HashSet

Answer 7

tenere entrambe le liste X e Y in modo ordinato.

Se x = y, eseguire l'operazione, se x < y, anticipo x, se y < x, avanzare y fino a quando una lista è vuota.

Il tempo di esecuzione di questa intersezione è proporzionale min (dimensione (x), dimensione (y))

Non eseguire un ciclo .Contains(), questo è proporzionale x * y che è molto peggio.

Answer 8

Si dovrebbe leggere this blog che la velocità ha verificato diversi tipi diversi di raccolte e metodi per ciascuna utilizzando sia tecniche singole che multi-thread.

In base ai risultati, una ricerca binaria su una lista e una lista ordinata erano i migliori artisti che eseguivano costantemente il collo in collo quando guardavano qualcosa come un "valore".

Quando si utilizza una raccolta che consente "chiavi", il dizionario, ConcurrentDictionary, Hashset e HashTables hanno ottenuto il miglior risultato complessivo.