Performances HashSet vs. List

Il est clair que les performances de recherche de la HashSet générique HashSet sont supérieures à celles de la classe List générique. Comparez simplement la clé basée sur le hachage avec l’approche linéaire dans la classe List .

Cependant, le calcul d’une clé de hachage peut nécessiter certains cycles de processeur, de sorte que pour une petite quantité d’éléments, la recherche linéaire peut constituer une véritable alternative au HashSet .

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

Pour simplifier le scénario (et être juste), supposons que la classe List utilise la méthode Equals() l’élément pour identifier un élément.

Beaucoup de gens disent qu’une fois la taille HashSet battra toujours List , mais cela dépend de ce que vous faites.

Disons que vous avez une List qui ne comportera en moyenne que 5 éléments. Sur un grand nombre de cycles, si un seul élément est ajouté ou supprimé à chaque cycle, il est préférable d’utiliser une List .

J’ai fait un test pour cela sur ma machine et, bien, il doit être très petit pour tirer parti de List . Pour une liste de chaînes courtes, l’avantage a disparu après la taille 5, pour les objects 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:

entrer la description de l'image ici

Voici le code:

 static void Main(ssortingng[] args) { int times = 10000000; for (int listSize = 1; listSize < 10; listSize++) { List list = new List(); HashSet hashset = new HashSet(); 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 list = new List(); HashSet hashset = new HashSet(); 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(); } 

Vous regardez mal cela. Oui, une recherche linéaire d’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 si petites. Ce sont généralement les grandes collections dont vous devez vous préoccuper, et c’est là que vous pensez en termes de Big-O . Toutefois, si vous avez mesuré un véritable goulot d’étranglement sur les performances de HashSet, vous pouvez essayer de créer un List / HashSet hybride, mais vous le ferez en effectuant de nombreux tests de performances empiriques, sans poser de questions sur SO.

Il est essentiellement inutile de comparer deux structures pour des performances qui se comportent différemment. Utilisez la structure qui transmet l’intention. Même si vous dites que List n’aurait pas de doublons et que l’itération n’a pas d’importance, le HashSet à un HashSet , c’est toujours un mauvais choix d’utiliser List car il est relativement moins tolérant aux pannes.

Cela dit, je vais inspecter d’ autres aspects de la performance,

 +------------+--------+-------------+-----------+----------+----------+-----------+ | Collection | Random | Containment | Insertion | Addition | Removal | Memory | | | access | | | | | | +------------+--------+-------------+-----------+----------+----------+-----------+ | List | O(1) | O(n) | O(n) | O(1)* | O(n) | Lesser | | HashSet | 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 since it involves cost of precomputing hash code before storing it.

** The superior scalability of HashSet has a memory cost. Every entry is stored as a new object along with its hash code. This article might give you an idea.

Que vous utilisiez un HashSet <> ou une liste <>, cela dépend de la manière dont vous devez accéder à votre collection . Si vous avez besoin de 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 œuvre de leurs algorithmes et objects de hachage.

Un HashSet accédera aux éléments sans avoir à énumérer la collection (complexité de O (1) ou proche de celle-ci), et comme une liste garantit l’ordre, contrairement à un HashSet, certains éléments devront être énumérés (complexité de O (n)).

Je pensais juste que je jetterais quelques points de repère pour différents scénarios pour illustrer les réponses précédentes:

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

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

  1. Au début de la liste (“start”, index 0)
  2. Près du début de la liste (“tôt”, index 1)
  3. Au milieu de la liste (“middle”, index count / 2)
  4. Vers la fin de la liste (“en retard”, index 2)
  5. À la fin de la liste (“end”, 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 en hashset. 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 

Échantillon sortie

Testé sur Windows 7, Ram 12 Go, 64 bits, Xeon 2,8 GHz

 ---------- Testing few small ssortingngs ------------ 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 ssortingngs ------------ 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 ssortingngs ------------ 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 ssortingngs ------------ 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] 

Le seuil de rentabilité dépendra du coût du calcul du hachage. Les calculs de hachage peuvent être sortingviaux, ou pas … 🙂 Il existe toujours la classe System.Collections.Specialized.HybridDictionary pour vous aider à ne pas vous soucier du seuil de rentabilité.

La réponse, comme toujours, est ” Cela dépend “. Je suppose que depuis les balises, vous parlez de C #.

Votre meilleur pari est de déterminer

  1. Un dataset
  2. Exigences d’utilisation

et écrire des cas de test.

Cela dépend aussi de la façon dont vous sortingez la liste (si elle est sortingée du tout), du type de comparaison à effectuer, de la durée de l’opération “Compare” pour l’object particulier de la liste, ou même de la collection.

Généralement, le meilleur choix est moins basé sur la taille des données avec lesquelles vous travaillez que sur la manière dont vous souhaitez y accéder. Avez-vous chaque pièce de données associée à une chaîne particulière, ou d’autres données? Une collection basée sur le hachage serait probablement la meilleure. L’ordre des données que vous stockez est-il important ou allez-vous avoir besoin d’accéder à toutes les données en même temps? Une liste régulière peut être préférable.

Additionnel:

Bien sûr, mes commentaires ci-dessus supposent que «performance» signifie un access aux données. Autre chose à considérer: que recherchez-vous lorsque vous dites “performance”? Est-ce que la performance individuelle de valeur recherche? Est-ce 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? Enlever des données? Accéder à des bits de données individuels? Remplacer les 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 principale exigence de performance est une utilisation minimale de la mémoire, vous pouvez rencontrer des problèmes de conception contradictoires.

Vous pouvez utiliser un HybridDictionary qui détecte automatiquement le sharepoint rupture et accepte les valeurs nulles, ce qui le rend indispensable en tant que HashSet.

Ça dépend. Si la réponse exacte compte vraiment, faites du profilage et découvrez. Si vous êtes certain de ne jamais avoir plus d’un certain nombre d’éléments dans l’ensemble, choisissez une liste. Si le nombre est illimité, utilisez un HashSet.

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

Vous pourriez sûrement créer une référence assez facilement?

Un facteur dont vous ne tenez pas 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 de HashSet diminue également.

Dépend de beaucoup de facteurs … Implémentation de la liste, architecture du processeur, JVM, sémantique de la boucle, complexité de la méthode des équations, etc. Au moment où la liste est suffisamment grande pour évaluer efficacement (plus de 1000 éléments), binary basé sur Hash les recherches battent les recherches linéaires de haut en bas et la différence ne s’étend qu’à partir de là.

J’espère que cela t’aides!