J'ai mis en œuvre une recherche binaire, une recherche linéaire et une table de hachage pour comparer chaque fois la complexité. Le problème est qu'entreprime, ma table de hachage est beaucoup plus lente que la recherche binaire lorsque je mesure le temps de trouver des nombres premiers. Ci-dessous mon code: hashtable.h J'ai déjà essayé de dépasser la taille de la taille de la table pour éliminer les collisions Mais je n'ai remarqué aucune différence. 
3 Réponses :
Il s'agit de la recherche binaire de complexité est O (log n) et votre recherche est linéaire SO O (n), à un moment donné lorsque vous avez beaucoup de collision.
Certaines choses sous-optimales avec la mise en œuvre de la table de hachage:
Vous gérez des collisions avec des listes liées: cela signifie que vous suivez toujours au moins un pointeur à l'écart de la mémoire contiguë de la table, ce qui est lent et pour les collisions que vous sautez dans la mémoire avec chaque nœud de la liste; Utilisation de prime.size () * 20 est excessif - vous obtiendrez beaucoup plus de cache misses que nécessaire; Essayez une plage de valeurs entre 1 et ~ 2 pour trouver un point optimal
prime.size () * 20 est toujours même et tous les nombres premiers que vous avez avec Taille% de clé sont impairs, donc vous ne savez jamais la moitié des seaux, le gaspillage d'espace et les performances de cache dégradantes
std :: vecteur int similaires.
Si vos données sont complètement aléatoires, il peut être difficile de trouver une bonne constante pour l'opération MODULO. Si vos données suivent une sorte de motif, vous voudrez peut-être essayer d'utiliser un tas de constantes de candidat pour voir la meilleure performance sur vos données.
in Ce post J'ai montré comment un tel test à grande échelle pourrait être structuré. À la fin, ma table de hachage a produit une recherche moyenne dans 1,5 comparaisons avec un pire des cas de 14. La table contenait 16 000 entrées, environ 2 ^ 14.
C'est un très bon graphique. On dirait que l'on s'attendait à: la recherche de hachage a une complexité de temps constante et le binaire a une logarithmique. C'est juste que la constante de la table de hachage est assez grande. Les vecteurs jouent très bien avec les caches.
Probablement sans rapport avec la référence; mais le constructeur doit accepter
prime par référenceQu'advient-il de vos horaires si vous modifiez le type de
Table surstd :: vecteur * ? Ouais, mais je viens d'utiliser le vecteur pour insérer les éléments. Je mesure seulement le temps de trouver l'élément. Le conteneur utilisé dans la table est STD :: Liste * Tableau.
Eh bien, si je change de table à un vecteur, je ne peux pas gérer de collisions, c'est pourquoi j'utilise un tableau de listes.
Que se passe-t-il si vous changez
Taille de% de% de clé surKey% 12345 , je veux dire, code du disque dur? Sera-ce plus rapide? Je pense que la division peut être un peu trop lente. (BTW, c'est un mauvais type de fonction de hachage en général, à moins que le diviseur soit un nombre premier). De plus, compilez-vous votre code avec des optimisations sur ou désactivées?Utilisez STD :: vecteur *, si seulement la recherche de la recherche trier la collision. Et obtenir un const & de table [index]
Où est votre code de référence?
int tablesize = prime.size () * 20; - c'est un lot de l'espace gaspillé (et, par conséquent, le temps)Je crois que la suggestion de Msandiford était d'utiliser une gamme de vecteurs plutôt que d'une liste de listes. Tout ce que vous faites avec les éléments du tableau consiste à rechercher et à ajouter;
Vecteur devrait surperformerListe pour cela.J'aime voir des questions comme celles-ci. : ')
Il s'agit d'une implémentation de hashtable assez médiocre, comme les commentaires ci-dessus expliquent. Donc, il a une très haute tenue de temps. Cependant, il s'agit d'une bonne hache, de sorte que ses performances sont à peu près constantes, même si le nombre de nœuds augmente. À moins que le nombre d'éléments est très important, il sera battu par une recherche binaire bien écrite. Avez-vous Benchmark
std :: Unordered_map oustd :: ONUOMODRED_SET_SET ?