Il est clair que les performances de recherche de la HashSet<T>
classe générique sont supérieures à celles de la List<T>
classe générique . Il suffit de comparer la clé basée sur le hachage avec l'approche linéaire dans leList<T>
classe.
Cependant, le calcul d'une clé de hachage peut lui-même prendre quelques cycles de processeur, donc pour une petite quantité d'éléments, la recherche linéaire peut être une véritable alternative à la HashSet<T>
.
Ma question: où est le seuil de rentabilité?
Pour simplifier le scénario (et pour être juste) supposons que la List<T>
classe utilise la Equals()
méthode de l'élément pour identifier un élément.
.net
performance
collections
list
hash
Michael Damatov
la source
la source
Réponses:
Beaucoup de gens disent qu'une fois que vous atteignez la taille où la vitesse est en fait une préoccupation qui
HashSet<T>
battra toujoursList<T>
, mais cela dépend de ce que vous faites.Disons que vous en avez un
List<T>
qui ne comportera en moyenne que 5 articles. Sur un grand nombre de cycles, si un seul élément est ajouté ou supprimé à chaque cycle, il est préférable d’utiliser aList<T>
.J'ai fait un test pour cela sur ma machine, et, bien, il doit être très très petit pour en tirer un avantage
List<T>
. Pour une liste de chaînes courtes, l'avantage a disparu après la taille 5, pour les objets après la taille 20.Voici ces données affichées sous forme de graphique:
Voici le code:
la source
List<T>
moteur de jeu, et comme j'ai généralement un volume élevé d'objets, ce genre de collection serait parfait.Vous regardez mal. Oui, une recherche linéaire d'une liste battra un HashSet pour un petit nombre d'éléments. Mais la différence de performances n'a généralement pas d'importance pour les collections aussi petites. Ce sont généralement les grandes collections dont vous devez vous soucier, et c'est là que vous pensez en termes de Big-O . Cependant, si vous avez mesuré un véritable goulot 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 performances empiriques - sans poser de questions sur SO.
la source
when small collection becomes large enough to worry about HashSet vs List?
dizaines, dizaines de milliers, milliards d'éléments?HashSet<T>
. Dans les cas en petit nombre où celaList<T>
pourrait être plus rapide, la différence est insignifiante . "Il est essentiellement inutile de comparer deux structures de performances qui se comportent différemment. Utilisez la structure qui exprime l'intention. Même si vous dites que vous
List<T>
n'auriez pas de doublons et que l'ordre d'itération n'a pas d'importance ce qui le rend comparable à unHashSet<T>
, c'est toujours un mauvais choix à utiliserList<T>
car il est relativement moins tolérant aux pannes.Cela dit, je vais inspecter certains autres aspects de la performance,
Même si l'addition est O (1) dans les deux cas, elle sera relativement plus lente dans HashSet car elle implique des coûts de précalcul du code de hachage avant de le stocker.
L'évolutivité supérieure de HashSet a un coût de mémoire. Chaque entrée est stockée en tant que nouvel objet avec son code de hachage. Cet article pourrait vous donner une idée.
la source
Que ce soit pour utiliser un HashSet <> ou une liste <> se résume à la façon dont vous devez 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 œuvre de leurs algorithmes et objets de hachage.
Un HashSet accédera aux éléments sans avoir à énumérer la collection (complexité de O (1) ou à proximité), et parce qu'une Liste garantit l'ordre, contrairement à un HashSet, certains éléments devront être énumérés (complexité de O (n)).
la source
List
est préférable, car vous pouvez vous souvenir d'un index - c'est la situation que vous décrivent.Je pensais juste que je ferais sonner quelques repères pour différents scénarios pour illustrer les réponses précédentes:
Et pour chaque scénario, recherche des valeurs qui apparaissent:
Avant chaque scénario, j'ai généré des listes de chaînes aléatoires de taille aléatoire, puis j'ai alimenté chaque liste en un hachage. Chaque scénario s'est exécuté 10 000 fois, essentiellement:
(test du pseudocode)
Exemple de sortie
Testé sur Windows 7, 12 Go de RAM, 64 bits, Xeon 2,8 GHz
la source
List
ne faut que 0,17 millisecondes pour effectuer une seule recherche et ne nécessitera probablement pas de substitutionHashSet
jusqu'à ce que la fréquence de recherche atteigne des niveaux absurdes. D'ici là, l'utilisation de List est généralement le moindre des problèmes.Le seuil de rentabilité dépendra du coût de calcul du hachage. Les calculs de hachage peuvent être triviaux, ou non ... :-) Il y a toujours la classe System.Collections.Specialized.HybridDictionary pour vous aider à ne pas avoir à vous soucier du seuil de rentabilité.
la source
La réponse, comme toujours, est " Cela dépend ". Je suppose que les balises dont vous parlez C #.
Votre meilleur pari est de déterminer
et écrire quelques cas de test.
Cela dépend également de la façon dont vous triez la liste (si elle est triée), du type de comparaison à effectuer, de la durée de l'opération "Comparer" pour l'objet particulier de la liste, ou même de la manière dont vous avez l'intention d'utiliser le collection.
Généralement, le meilleur choix n'est pas tellement basé sur la taille des données avec lesquelles vous travaillez, mais plutôt sur la façon dont vous avez l'intention d'y accéder. Avez-vous chaque élément de données associé à 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 alors être meilleure.
Additionnel:
Bien sûr, mes commentaires ci-dessus supposent que «performance» signifie l'accès aux données. Autre chose à considérer: que recherchez-vous lorsque vous dites "performance"? La performance de la valeur individuelle est-elle recherchée? 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? Remplacement 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 principale exigence de performances est une utilisation minimale de la mémoire, vous pouvez rencontrer des problèmes de conception conflictuels.
la source
Vous pouvez utiliser un HybridDictionary qui détecte automatiquement le point de rupture et accepte les valeurs nulles, ce qui le rend essentiellement identique à un HashSet.
la source
Ça dépend. Si la réponse exacte est vraiment importante, faites un profilage et découvrez. Si vous êtes sûr que vous n'aurez jamais plus d'un certain nombre d'éléments dans l'ensemble, optez pour une liste. Si le nombre est illimité, utilisez un HashSet.
la source
Cela dépend de ce que vous hachez. Si vos clés sont des entiers, vous n'avez probablement pas besoin de beaucoup d'éléments avant que le HashSet ne soit plus rapide. Si vous le saisissez sur une chaîne, il sera plus lent et dépend de la chaîne d'entrée.
Vous pourriez sûrement concocter assez facilement une référence?
la source
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 à mesure que la fonction de hachage diminue, le temps de recherche du HashSet diminue également.
la source
Dépend de beaucoup de facteurs ... Implémentation de la liste, architecture CPU, JVM, sémantique de boucle, complexité de la méthode des égaux, etc. les recherches battent haut et bas les recherches linéaires, et la différence ne fait que s'aggraver à partir de là.
J'espère que cela t'aides!
la source