Prestazioni di HashSet vs. List

Question

È chiaro che un rendimento di ricerca della classe HashSet<T> generica è superiore a quello della classe List<T> generica. Basta confrontare la chiave basata su hash con l'approccio lineare nella Equals() classe.

Tuttavia, il calcolo di una chiave hash può richiedere alcuni cicli della CPU, quindi per una piccola quantità di elementi la ricerca lineare può essere una vera alternativa a <=>.

La mia domanda: dov'è il pareggio?

Per semplificare lo scenario (ed essere onesti) supponiamo che la classe <=> usi il metodo <=> dell'elemento per identificare un oggetto.

Answer 1

Molte persone stanno dicendo che una volta raggiunta la dimensione in cui la velocità è in realtà una preoccupazione che HashSet<T> batterà sempre List<T>, ma ciò dipende da cosa stai facendo.

Supponiamo che tu abbia un <=> che avrà sempre e solo in media 5 elementi al suo interno. Su un gran numero di cicli, se un singolo elemento viene aggiunto o rimosso per ogni ciclo, potresti essere meglio usando un <=>.

Ho fatto un test per questo sulla mia macchina e, beh, deve essere molto piccolo per ottenere un vantaggio da <=>. Per un elenco di stringhe brevi, il vantaggio è scomparso dopo la dimensione 5, per gli oggetti dopo la dimensione 20.

1 item LIST strs time: 617ms
1 item HASHSET strs time: 1332ms

2 item LIST strs time: 781ms
2 item HASHSET strs time: 1354ms

3 item LIST strs time: 950ms
3 item HASHSET strs time: 1405ms

4 item LIST strs time: 1126ms
4 item HASHSET strs time: 1441ms

5 item LIST strs time: 1370ms
5 item HASHSET strs time: 1452ms

6 item LIST strs time: 1481ms
6 item HASHSET strs time: 1418ms

7 item LIST strs time: 1581ms
7 item HASHSET strs time: 1464ms

8 item LIST strs time: 1726ms
8 item HASHSET strs time: 1398ms

9 item LIST strs time: 1901ms
9 item HASHSET strs time: 1433ms

1 item LIST objs time: 614ms
1 item HASHSET objs time: 1993ms

4 item LIST objs time: 837ms
4 item HASHSET objs time: 1914ms

7 item LIST objs time: 1070ms
7 item HASHSET objs time: 1900ms

10 item LIST objs time: 1267ms
10 item HASHSET objs time: 1904ms

13 item LIST objs time: 1494ms
13 item HASHSET objs time: 1893ms

16 item LIST objs time: 1695ms
16 item HASHSET objs time: 1879ms

19 item LIST objs time: 1902ms
19 item HASHSET objs time: 1950ms

22 item LIST objs time: 2136ms
22 item HASHSET objs time: 1893ms

25 item LIST objs time: 2357ms
25 item HASHSET objs time: 1826ms

28 item LIST objs time: 2555ms
28 item HASHSET objs time: 1865ms

31 item LIST objs time: 2755ms
31 item HASHSET objs time: 1963ms

34 item LIST objs time: 3025ms
34 item HASHSET objs time: 1874ms

37 item LIST objs time: 3195ms
37 item HASHSET objs time: 1958ms

40 item LIST objs time: 3401ms
40 item HASHSET objs time: 1855ms

43 item LIST objs time: 3618ms
43 item HASHSET objs time: 1869ms

46 item LIST objs time: 3883ms
46 item HASHSET objs time: 2046ms

49 item LIST objs time: 4218ms
49 item HASHSET objs time: 1873ms

Ecco i dati visualizzati sotto forma di grafico:

Ecco il codice:

static void Main(string[] args)
{
    int times = 10000000;


    for (int listSize = 1; listSize < 10; listSize++)
    {
        List<string> list = new List<string>();
        HashSet<string> hashset = new HashSet<string>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add("string" + i.ToString());
            hashset.Add("string" + i.ToString());
        }

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove("string0");
            list.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");


        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove("string0");
            hashset.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }


    for (int listSize = 1; listSize < 50; listSize+=3)
    {
        List<object> list = new List<object>();
        HashSet<object> hashset = new HashSet<object>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add(new object());
            hashset.Add(new object());
        }

        object objToAddRem = list[0];

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove(objToAddRem);
            list.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");



        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove(objToAddRem);
            hashset.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }

    Console.ReadLine();
}

Answer 2

Stai guardando questo sbagliato. Sì, una ricerca lineare di un elenco batterà un HashSet per un numero limitato di elementi. Ma la differenza di prestazioni di solito non ha importanza per raccolte così piccole. In genere sono le grandi collezioni di cui ti devi preoccupare, ed è qui che pensa in termini di Big-O . Tuttavia, se hai misurato un vero collo di bottiglia sulle prestazioni di HashSet, puoi provare a creare un elenco ibrido / HashSet, ma lo farai conducendo molti test empirici sulle prestazioni, senza fare domande su SO.

Answer 3

È essenzialmente inutile confrontare due strutture per prestazioni che si comportano diversamente. Usa la struttura che trasmette l'intento. Anche se dici che il tuo List<T> non avrebbe duplicati e l'ordine di iterazione non importa rendendolo paragonabile a un HashSet<T>, è ancora una cattiva scelta da usare * Even though addition is O(1) in both cases, it will be relatively slower in HashSet<T> since it involves cost of precomputing hash code before storing it. perché è relativamente meno tollerante ai guasti.

Detto questo, ispezionerò alcuni altri aspetti delle prestazioni,

+------------+--------+-------------+-----------+----------+----------+-----------+
| Collection | Random | Containment | Insertion | Addition |  Removal | Memory    |
|            | access |             |           |          |          |           |
+------------+--------+-------------+-----------+----------+----------+-----------+
| List<T>    | O(1)   | O(n)        | O(n)      | O(1)*    | O(n)     | Lesser    |
| HashSet<T> | O(n)   | O(1)        | n/a       | O(1)     | O(1)     | Greater** |
+------------+--------+-------------+-----------+----------+----------+-----------+

** The superior scalability of HashSet<T> has a memory cost. Every entry is stored as a new object along with its hash code.

This article might give you an idea. <=>

Answer 4

Se usare un HashSet < > oppure Elenco < > si riduce a come è necessario accedere alla propria collezione . Se è necessario garantire l'ordine degli articoli, utilizzare un elenco. In caso contrario, utilizzare un HashSet. Lascia che Microsoft si preoccupi dell'implementazione dei suoi algoritmi e oggetti di hashing.

Un HashSet accederà agli elementi senza dover enumerare la raccolta (complessità di O (1) o vicino ad esso) e poiché un Elenco garantisce l'ordine, diversamente da un HashSet, alcuni elementi dovranno essere enumerati (complessità di O (n)).

Answer 5

Ho pensato di entrare in contatto con alcuni parametri di riferimento per diversi scenari per illustrare le risposte precedenti:

1. Alcune stringhe (12-20) piccole (lunghezza compresa tra 5 e 10 caratteri)
2. Molte (~ 10K) stringhe piccole
3. Alcune stringhe lunghe (lunghezza compresa tra 200 e 1000 caratteri)
4. Molte stringhe lunghe (~ 5K)
5. Alcuni numeri interi
6. Molti (~ 10K) numeri interi

E per ogni scenario, cercare i valori che appaiono:

1. All'inizio dell'elenco (" start " ;, indice 0)
2. Vicino all'inizio dell'elenco (" inizio " ;, indice 1)
3. In mezzo all'elenco (" middle " ;, indice count / 2)
4. Verso la fine dell'elenco (" late " ;, indice count-2)
5. Alla fine dell'elenco (" end " ;, indice count-1)

Prima di ogni scenario ho generato elenchi di stringhe casuali di dimensioni casuali, quindi ho inviato ciascun elenco a un hashset. Ogni scenario è stato eseguito 10.000 volte, essenzialmente:

(test pseudocodice)

stopwatch.start
for X times
    exists = list.Contains(lookup);
stopwatch.stop

stopwatch.start
for X times
    exists = hashset.Contains(lookup);
stopwatch.stop

Output di esempio

Testato su Windows 7, 12 GB di RAM, 64 bit, Xeon 2.8GHz

---------- Testing few small strings ------------
Sample items: (16 total)
vgnwaloqf diwfpxbv tdcdc grfch icsjwk
...

Benchmarks:
1: hashset: late -- 100.00 % -- [Elapsed: 0.0018398 sec]
2: hashset: middle -- 104.19 % -- [Elapsed: 0.0019169 sec]
3: hashset: end -- 108.21 % -- [Elapsed: 0.0019908 sec]
4: list: early -- 144.62 % -- [Elapsed: 0.0026607 sec]
5: hashset: start -- 174.32 % -- [Elapsed: 0.0032071 sec]
6: list: middle -- 187.72 % -- [Elapsed: 0.0034536 sec]
7: list: late -- 192.66 % -- [Elapsed: 0.0035446 sec]
8: list: end -- 215.42 % -- [Elapsed: 0.0039633 sec]
9: hashset: early -- 217.95 % -- [Elapsed: 0.0040098 sec]
10: list: start -- 576.55 % -- [Elapsed: 0.0106073 sec]


---------- Testing many small strings ------------
Sample items: (10346 total)
dmnowa yshtrxorj vthjk okrxegip vwpoltck
...

Benchmarks:
1: hashset: end -- 100.00 % -- [Elapsed: 0.0017443 sec]
2: hashset: late -- 102.91 % -- [Elapsed: 0.0017951 sec]
3: hashset: middle -- 106.23 % -- [Elapsed: 0.0018529 sec]
4: list: early -- 107.49 % -- [Elapsed: 0.0018749 sec]
5: list: start -- 126.23 % -- [Elapsed: 0.0022018 sec]
6: hashset: early -- 134.11 % -- [Elapsed: 0.0023393 sec]
7: hashset: start -- 372.09 % -- [Elapsed: 0.0064903 sec]
8: list: middle -- 48,593.79 % -- [Elapsed: 0.8476214 sec]
9: list: end -- 99,020.73 % -- [Elapsed: 1.7272186 sec]
10: list: late -- 99,089.36 % -- [Elapsed: 1.7284155 sec]


---------- Testing few long strings ------------
Sample items: (19 total)
hidfymjyjtffcjmlcaoivbylakmqgoiowbgxpyhnrreodxyleehkhsofjqenyrrtlphbcnvdrbqdvji...
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0018266 sec]
2: list: start -- 115.76 % -- [Elapsed: 0.0021144 sec]
3: list: middle -- 143.44 % -- [Elapsed: 0.0026201 sec]
4: list: late -- 190.05 % -- [Elapsed: 0.0034715 sec]
5: list: end -- 193.78 % -- [Elapsed: 0.0035395 sec]
6: hashset: early -- 215.00 % -- [Elapsed: 0.0039271 sec]
7: hashset: end -- 248.47 % -- [Elapsed: 0.0045386 sec]
8: hashset: start -- 298.04 % -- [Elapsed: 0.005444 sec]
9: hashset: middle -- 325.63 % -- [Elapsed: 0.005948 sec]
10: hashset: late -- 431.62 % -- [Elapsed: 0.0078839 sec]


---------- Testing many long strings ------------
Sample items: (5000 total)
yrpjccgxjbketcpmnvyqvghhlnjblhgimybdygumtijtrwaromwrajlsjhxoselbucqualmhbmwnvnpnm
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: list: start -- 132.73 % -- [Elapsed: 0.0021517 sec]
3: hashset: start -- 231.26 % -- [Elapsed: 0.003749 sec]
4: hashset: end -- 368.74 % -- [Elapsed: 0.0059776 sec]
5: hashset: middle -- 385.50 % -- [Elapsed: 0.0062493 sec]
6: hashset: late -- 406.23 % -- [Elapsed: 0.0065854 sec]
7: hashset: early -- 421.34 % -- [Elapsed: 0.0068304 sec]
8: list: middle -- 18,619.12 % -- [Elapsed: 0.3018345 sec]
9: list: end -- 40,942.82 % -- [Elapsed: 0.663724 sec]
10: list: late -- 41,188.19 % -- [Elapsed: 0.6677017 sec]


---------- Testing few ints ------------
Sample items: (16 total)
7266092 60668895 159021363 216428460 28007724
...

Benchmarks:
1: hashset: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: hashset: end -- 100.45 % -- [Elapsed: 0.0016284 sec]
3: list: early -- 101.83 % -- [Elapsed: 0.0016507 sec]
4: hashset: late -- 108.95 % -- [Elapsed: 0.0017662 sec]
5: hashset: middle -- 112.29 % -- [Elapsed: 0.0018204 sec]
6: hashset: start -- 120.33 % -- [Elapsed: 0.0019506 sec]
7: list: late -- 134.45 % -- [Elapsed: 0.0021795 sec]
8: list: start -- 136.43 % -- [Elapsed: 0.0022117 sec]
9: list: end -- 169.77 % -- [Elapsed: 0.0027522 sec]
10: list: middle -- 237.94 % -- [Elapsed: 0.0038573 sec]


---------- Testing many ints ------------
Sample items: (10357 total)
370826556 569127161 101235820 792075135 270823009
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0015132 sec]
2: hashset: end -- 101.79 % -- [Elapsed: 0.0015403 sec]
3: hashset: early -- 102.08 % -- [Elapsed: 0.0015446 sec]
4: hashset: middle -- 103.21 % -- [Elapsed: 0.0015618 sec]
5: hashset: late -- 104.26 % -- [Elapsed: 0.0015776 sec]
6: list: start -- 126.78 % -- [Elapsed: 0.0019184 sec]
7: hashset: start -- 130.91 % -- [Elapsed: 0.0019809 sec]
8: list: middle -- 16,497.89 % -- [Elapsed: 0.2496461 sec]
9: list: end -- 32,715.52 % -- [Elapsed: 0.4950512 sec]
10: list: late -- 33,698.87 % -- [Elapsed: 0.5099313 sec]

Answer 6

Il breakeven dipenderà dal costo del calcolo dell'hash. I calcoli dell'hash possono essere banali o no ... :-) C'è sempre la classe System.Collections.Specialized.HybridDictionary per aiutarti a non doverti preoccupare del punto di pareggio.

Answer 7

La risposta, come sempre, è " Dipende " ;. Presumo dai tag di cui stai parlando in C #.

La tua scommessa migliore è determinare

1. Un set di dati
2. Requisiti di utilizzo

e scrivere alcuni casi di test.

Dipende anche da come si ordina l'elenco (se è ordinato), che tipo di confronti devono essere fatti, per quanto tempo " Confronta " operazione accetta l'oggetto particolare nell'elenco o anche il modo in cui si intende utilizzare la raccolta.

Generalmente, il migliore da scegliere non è tanto basato sulla dimensione dei dati con cui stai lavorando, ma piuttosto su come intendi accedervi. Hai ciascun dato associato a una stringa particolare o ad altri dati? Una raccolta basata sull'hash sarebbe probabilmente la migliore. L'ordine dei dati che stai memorizzando è importante o dovrai accedere a tutti i dati contemporaneamente? Un elenco regolare potrebbe essere migliore allora.

Ulteriori:

Naturalmente, i miei commenti sopra presuppongono che "prestazioni" significhi accesso ai dati. Qualcos'altro da considerare: cosa stai cercando quando dici & Quot; performance & Quot ;? Il valore individuale delle prestazioni è ricercato? Gestisce set di valori di grandi dimensioni (10000, 100000 o più)? È la prestazione di riempire la struttura di dati con i dati? Rimozione di dati? Accedere a singoli bit di dati? Sostituire i valori? Iterando sui valori? Utilizzo della memoria? Velocità di copia dei dati? Ad esempio, se si accede ai dati con un valore stringa, ma il requisito di prestazioni principale è un utilizzo minimo della memoria, è possibile che si verifichino problemi di progettazione in conflitto.

Answer 8

È possibile utilizzare un HybridDictionary che rileva automaticamente il punto di rottura e accetta valori null, rendendolo sostanzialmente uguale a un HashSet.

Answer 9

Dipende. Se la risposta esatta conta davvero, fai un po 'di profilazione e scoprilo. Se sei sicuro di non avere mai più di un certo numero di elementi nel set, scegli un Elenco. Se il numero è illimitato, utilizzare un HashSet.

Answer 10

Dipende da ciò che stai facendo. Se le tue chiavi sono numeri interi, probabilmente non hai bisogno di molti elementi prima che HashSet sia più veloce. Se lo stai digitando su una stringa, sarà più lento e dipende dalla stringa di input.

Sicuramente potresti creare un benchmark abbastanza facilmente?

Answer 11

Un fattore di cui non si tiene conto è la solidità della funzione GetHashcode (). Con una funzione hash perfetta, HashSet avrà chiaramente prestazioni di ricerca migliori. Ma man mano che la funzione hash diminuisce, anche il tempo di ricerca di HashSet diminuirà.

Answer 12

Dipende da molti fattori ... Implementazione dell'elenco, architettura della CPU, JVM, semantica del ciclo, complessità del metodo uguale, ecc ... Quando l'elenco diventa abbastanza grande per eseguire un benchmark efficace (oltre 1000 elementi), Hash le ricerche binarie basate su battiti battono le ricerche lineari a mani basse e la differenza aumenta solo da lì.

Spero che questo aiuti!