Performances HashSet vs. List

Question

Il est clair qu'une performance de recherche de la classe générique HashSet<T> est supérieure à celle de la classe générique List<T>. Il suffit de comparer la clé basée sur le hachage avec l’approche linéaire de la Equals() classe.

Cependant, le calcul d'une clé de hachage peut prendre quelques cycles de la CPU. Par conséquent, la recherche linéaire peut constituer une véritable alternative à la <=>.

Ma question: où est le seuil de rentabilité?

Pour simplifier le scénario (et pour être juste), supposons que la classe <=> utilise la méthode <=> de l'élément pour identifier un élément.

Answer 1

Beaucoup de gens disent qu’une fois que vous avez atteint la taille où la vitesse est réellement une préoccupation que HashSet<T> battra toujours List<T>, mais cela dépend de ce que vous faites.

Supposons que vous avez un <=> élément qui ne contiendra en moyenne que 5 éléments. Sur un grand nombre de cycles, si un seul élément est ajouté ou supprimé à chaque cycle, il vaut peut-être mieux utiliser un <=>.

J'ai fait un test à ce sujet sur ma machine et, bien, il doit être très petit pour obtenir un avantage de <=>. Pour une liste de chaînes courtes, l’avantage disparaissait après la taille 5, pour les objets après la taille 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

Voici les données affichées sous forme de graphique:

Voici le code:

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

Vous regardez ce qui ne va pas. Oui, une recherche linéaire dans une liste battra un HashSet pour un petit nombre d'éléments. Mais la différence de performance n'a généralement pas d'importance pour les collections. Ce sont généralement les grandes collections qui vous préoccupent, et c’est là que vous pense en termes de Big-O . Cependant, si vous avez mesuré un véritable goulet d'étranglement sur les performances de HashSet, vous pouvez essayer de créer une liste hybride / HashSet, mais vous le ferez en effectuant de nombreux tests de performance empiriques, sans poser de questions sur les SO.

Answer 3

Il est essentiellement inutile de comparer deux structures pour une performance qui se comportent différemment. Utilisez la structure qui traduit l'intention. Même si vous dites que votre List<T> n'aura pas de doublons et que l'ordre des itérations importe peu, vous pouvez le comparer à un HashSet<T>, mais le choix est toujours mauvais <= à cause de sa tolérance moins élevée aux pannes.

Cela dit, j'examinerai certains autres aspects de la performance,

.

+------------+--------+-------------+-----------+----------+----------+-----------+
| 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** |
+------------+--------+-------------+-----------+----------+----------+-----------+

* 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.

** 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

S'il faut utiliser un HashSet < > ou Liste < > revient à comment accéder à votre collection . Si vous devez garantir l'ordre des articles, utilisez une liste. Si vous ne le faites pas, utilisez un HashSet. Laissez Microsoft s’inquiéter de la mise en oeuvre de ses algorithmes et objets de hachage.

Un hachage permettra d'accéder aux éléments sans avoir à énumérer la collection (complexité de O (1) . ou près de celui-ci) et comme une liste garantit l’ordre, contrairement à un hachage, certains éléments devront être énumérés (complexité de O (n)).

Answer 5

Je pensais juste ajouter quelques points de repère pour différents scénarios afin d'illustrer les réponses précédentes:

1. Quelques petites chaînes (longueur comprise entre 5 et 10 caractères)
2. Beaucoup (~ 10K) de petites chaînes
3. Quelques longues chaînes (longueur comprise entre 200 et 1000 caractères)
4. Beaucoup de chaînes (~ 5K) longues
5. Quelques entiers
6. Plusieurs nombres entiers (~ 10K)

Et pour chaque scénario, recherchez les valeurs qui apparaissent:

1. Au début de la liste (" start " ;, index 0)
2. Au début de la liste (" early " ;, index 1)
3. Au milieu de la liste (" milieu " ;, nombre d'index / 2)
4. Près de la fin de la liste (" en retard " ;, index count-2)
5. À la fin de la liste (" fin " ;, index count-1)

Avant chaque scénario, j’ai généré des listes de chaînes aléatoires de taille aléatoire, puis alimenté chaque liste dans un hachage. Chaque scénario a été exécuté 10 000 fois, essentiellement:

(pseudocode de test)

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

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

Exemple de sortie

Testé sous Windows 7, 12 Go de RAM, 64 bits, Xeon 2,8 GHz

---------- 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

Le seuil de rentabilité dépendra du coût de calcul du hachage. Les calculs de hachage peuvent être triviaux, ou pas ... :-) Il y a toujours la classe System.Collections.Specialized.HybridDictionary pour vous aider à ne pas avoir à vous soucier du seuil de rentabilité.

Answer 7

Comme toujours, la réponse est & "; Cela dépend &"; Je suppose que, d'après les tags dont vous parlez, C #.

Votre meilleur pari est de déterminer

1. Un ensemble de données
2. Conditions d'utilisation

et écrivez quelques cas de test.

Cela dépend également de la manière dont vous triez la liste (si elle est triée du tout), du type de comparaison à effectuer, de la durée de la & "Comparaison &"; l'opération prend pour l'objet particulier de la liste, ou même comment vous prévoyez d'utiliser la collection.

En règle générale, le meilleur choix est de ne pas se baser uniquement sur la taille des données sur lesquelles vous travaillez, mais plutôt sur la manière dont vous souhaitez y accéder. Avez-vous chaque donnée associée à une chaîne particulière ou à d’autres données? Une collection basée sur le hachage serait probablement la meilleure. Est-ce que l'ordre des données que vous stockez est important ou allez-vous avoir besoin d'accéder à toutes les données en même temps? Une liste régulière peut être mieux alors.

Supplémentaire:

Bien sûr, mes commentaires ci-dessus supposent que «performance» signifie accès aux données. Autre chose à considérer: que cherchez-vous quand vous dites & "Performance &"; La performance est-elle une valeur individuelle? S'agit-il de la gestion de grands ensembles de valeurs (10000, 100000 ou plus)? Est-ce la performance de remplir la structure de données avec des données? Supprimer des données? Accéder à des bits de données individuels? Remplacer des valeurs? Itérer sur les valeurs? Utilisation de la mémoire? Vitesse de copie des données? Par exemple, si vous accédez aux données par une valeur de chaîne, mais que votre exigence principale en matière de performances est une utilisation minimale de la mémoire, des problèmes de conception peuvent apparaître.

Answer 8

Vous pouvez utiliser un HybridDictionary qui détecte automatiquement le point de rupture et accepte les valeurs NULL, le rendant ainsi essentiellement comme un HashSet.

Answer 9

Cela dépend. Si la réponse exacte compte vraiment, faites un profilage et découvrez-le. Si vous êtes certain que l'ensemble ne contient jamais plus d'un certain nombre d'éléments, choisissez une liste. Si le nombre est illimité, utilisez un HashSet.

Answer 10

Cela dépend de ce que vous hachez. Si vos clés sont des entiers, vous n'aurez probablement pas besoin de beaucoup d'éléments avant que le HashSet ne soit plus rapide. Si vous le saisissez sur une chaîne, celle-ci sera plus lente et dépend de la chaîne d'entrée.

Vous pourriez sûrement créer facilement un repère?

Answer 11

Un facteur que vous ne prenez pas en compte est la robustesse de la fonction GetHashcode (). Avec une fonction de hachage parfaite, le HashSet aura clairement de meilleures performances de recherche. Mais comme la fonction de hachage diminue, le temps de recherche HashSet le sera également.

Answer 12

Dépend de nombreux facteurs ... de la mise en oeuvre de la liste, de l’architecture de la CPU, de la JVM, de la sémantique de la boucle, de la complexité de la méthode de l’égale, etc ... les recherches binaires basées sur une base de données ont battu les recherches linéaires haut la main, et la différence ne fait qu’augmenter à partir de là.

J'espère que ça aide!