.NET: come verificare in modo efficiente l'unicità in un elenco <string> di 50.000 elementi?

Question

In alcuni codici di libreria, ho una lista che può contenere 50.000 elementi o più.

I chiamanti della libreria possono richiamare i metodi che determinano l'aggiunta di stringhe all'elenco. Come faccio a verificare in modo efficiente l'univocità delle stringhe aggiunte?

Attualmente, appena prima di aggiungere una stringa, analizzo l'intero elenco e confronta ogni stringa con la stringa da aggiungere. Questo inizia a mostrare problemi di scala superiori a 10.000 elementi.

Farò un punto di riferimento, ma mi interessa l'intuizione.

• se sostituire l'elenco <> con un dizionario <>, sarà ContainsKey() essere sensibilmente più veloce come la lista cresce fino a 10.000 articoli e oltre?
• se differisco il controllo di unicità fino a quando non sono stati aggiunti tutti gli elementi, sarà più veloce? A quel punto avrei bisogno di controllare ogni elemento contro ogni altro elemento, ancora un n ^^ 2 operazione.

---

EDIT

Alcuni risultati di base di riferimento. Ho creato una classe astratta che espone 2 metodi: Fill and Scan. Riempi semplicemente la raccolta con n elementi (ne ho usati 50.000). Scansione esegue la scansione della lista m volte (ho usato 5000) per vedere se è presente un determinato valore. Quindi ho creato un'implementazione di quella classe per List e un'altra per HashSet.

Le stringhe utilizzate erano lunghe uniformemente 11 caratteri e generate casualmente tramite un metodo nella classe astratta.

Un micro-benchmark di base.

Hello from Cheeso.Tests.ListTester 
filling 50000 items... 
scanning 5000 items... 
Time to fill: 00:00:00.4428266 
Time to scan: 00:00:13.0291180 

Hello from Cheeso.Tests.HashSetTester 
filling 50000 items... 
scanning 5000 items... 
Time to fill: 00:00:00.3797751 
Time to scan: 00:00:00.4364431 

Così, per le stringhe di quella lunghezza, HashSet è circa 25x più veloce di lista, durante la scansione di unicità. Inoltre, per questa dimensione di raccolta, HashSet ha zero penalità su Elenco quando si aggiungono elementi alla raccolta.

I risultati sono interessanti e non validi. Per ottenere risultati validi, avrei bisogno di fare intervalli di riscaldamento, prove multiple, con selezione casuale dell'implementazione. Ma sono fiducioso che ciò sposterebbe la barra solo leggermente.

Grazie a tutti.

EDIT2

Dopo aver aggiunto la randomizzazione e multple prove, HashSet supera costantemente lista in questo caso, di circa 20x.

Questi risultati non sono necessariamente validi per stringhe di lunghezza variabile, oggetti più complessi o dimensioni di raccolta diverse.

Answer 1

È necessario utilizzare la classe HashSet<T>, progettata specificamente per ciò che si sta facendo.

Answer 2

Utilizzare HashSet<string> anziché List<string>, quindi dovrebbe scalare molto bene.

Answer 3

Ho letto che il dizionario < è implementato come un array associativo. In alcuni linguaggi (non necessariamente correlati a .NET), gli indici di stringa vengono memorizzati come una struttura ad albero che si biforca su ciascun nodo in base al carattere nel nodo. Si prega di consultare http://en.wikipedia.org/wiki/Associative_arrays.

Una struttura di dati simile è stata ideata da Aho e Corasick nel 1973 (credo). Se si memorizzano 50.000 stringhe in tale struttura, non importa quante stringhe si stanno memorizzando. Importa più la lunghezza delle stringhe. Se hanno circa la stessa lunghezza, probabilmente non vedrai mai un rallentamento nelle ricerche perché l'algoritmo di ricerca è lineare in fase di esecuzione rispetto alla lunghezza della stringa che stai cercando. Anche per un albero rosso-nero o un albero AVL, il tempo di esecuzione della ricerca dipende più dalla lunghezza della stringa che si sta cercando, piuttosto che dal numero di elementi nell'indice. Tuttavia, se si sceglie di implementare le proprie chiavi di indice con una funzione di hash, ora si incorre nel costo di hashing della stringa (che sarà O (m), m = lunghezza della stringa) e anche della ricerca della stringa nell'indice, che sarà probabilmente dell'ordine di O (log (n)), n = numero di elementi nell'indice.

modifica: non sono un guru .NET. Altre persone più esperte suggeriscono un'altra struttura. Vorrei prendere la parola sul mio.

edit2: la tua analisi è un po 'spenta per confrontare l'unicità. Se si utilizza una struttura o un dizionario di hashing, non sarà un'operazione O (n^2) a causa del ragionamento che ho postato sopra. Se continui a utilizzare un elenco, sei corretto che sia O (n^2) * (lunghezza massima di una stringa nell'insieme) poiché devi esaminare ogni elemento dell'elenco ogni volta.

Answer 4

Dalle mie prove, HashSet<string> basta poco rispetto al List<string> :)

Answer 5

Ha la funzione Contains(T) non funziona per voi?

Answer 6

Forse fuori tema, ma se si desidera scalare serie di stringhe univoche molto grandi (milioni +) in un modo indipendente dalla lingua, è possibile controllare Bloom Filters.