stl hash_map plus lent que la simple fonction de hachage?

Je comparais une simple fonction de hachage que j'écrivais et que je multiplie juste par un mod premier autre nombre premier (la taille de la table) et il s'avère que stl est plus lent de 100 fois. Ceci est la méthode d'essai que j'ai écrit:stl hash_map plus lent que la simple fonction de hachage?

stdext:: hash_map<string, int> hashDict; 
for (int l = 0; l < size; ++l){ 
    hashDict[arr[l]] = l; 
} 
long int before3 = GetTickCount(); 
int c = 0; 
while (c < size){ 
    hashDict[arr[c]]; 
    c++; 
} 
long int after3 = GetTickCount(); 
cout << "for stl class, the time is " << (after3 - before3)/1000.0 << '\n'; 
cout << "the average is " << ((after3 - before3)/1000.0) /long (size) << '\n';

La taille du dictionnaire est d'environ 200K éléments et la taille de la table de la fonction de hachage j'ai écrit a entrées 3m, alors peut-être qu'elle a à voir avec la taille de table la classe stl étant très petite. Est-ce que quelqu'un sait ce que la tableize de la fonction stl est et les taux de collision.etc?

Source

2009-12-28 SuperString

C'est ma fonction de hachage: hachage non signé (const char * s) { \t de hashval non signé; \t pour (hashval = 0; * s! = '\ 0'; s ++) \t \t hashval = * s + PRIME * hashval; \t return hashval% HASHSIZE; } – SuperString

Cela a vraiment, vraiment besoin de plus d'informations pour répondre. Quelle est votre fonction de hachage simple, et que fait-elle? De plus, de quelle implémentation 'hash_map' parlez-vous? Il n'y en a pas dans la STL (il y aura un 'std :: unordered_map <>'). Enfin, vous ne faites rien avec le hachage dans le code fourni; êtes-vous sûr que votre version fait quoi que ce soit? –

Je récupère juste les éléments de la carte, ne faisant rien avec. – SuperString

La mise en œuvre VS2008 STL utilise la fonction de hachage suivante pour les chaînes:

size_t _Val = 2166136261U; 
while(_Begin != _End) 
    _Val = 16777619U * _Val^(size_t)*_Begin++;

Ce n'est pas moins efficace que le vôtre, certainement pas 100x, et je doute que la version Builder est bien différente. La différence est soit dans la mesure (GetTickCount() n'est pas très précis) ou dans des opérations autres que le calcul des valeurs de hachage.

Je ne connais pas C++ Builder, mais certaines implémentations STL ont beaucoup de vérifications et d'assertions supplémentaires intégrées dans la version de débogage. Avez-vous essayé de profiler une version optimisée?

Si vous postez un exemple minimal mais complet, nous pouvons vous aider à comprendre ce qui se passe, mais sans plus de code, il n'y a vraiment pas grand chose à dire.

Source

2009-12-28 21:12:18

Je devine 216613626U est la taille de la table et 16777619U est le nombre premier? Quels sont ces chiffres en termes d'int? Et où avez-vous trouvé ce code? – SuperString

Non, ce ne sont que des constantes choisies pour minimiser les collisions, elles n'ont rien à voir avec la table de hachage particulière. La valeur finale est forcée dans la taille de la table avec un module comme dans votre exemple, mais ce n'est pas pertinent en termes de performance. Le code est dans la fonction '_Hash_value' dans l'en-tête' ', mais il est spécifique à l'implémentation. –

alors quelle est la taille de la table stl hash_map? – SuperString

Pour afficher ceci comme réponse: Je pense que vous obtenez des valeurs erronées. Vous n'utilisez pas réellement les valeurs hachées, juste en les référençant, et donc le compilateur peut bien optimiser les accès à votre table de hachage et non le hash_map. Sauf dans des circonstances extrêmes et rares, vous n'allez pas battre une implémentation professionnelle par un grand facteur intégral tout en utilisant toujours le même algorithme, ce que vous êtes. Vous êtes au moins aussi susceptible de gagner le gros lot à la loterie que de le faire par un facteur de 100.

Changez votre code de test pour utiliser les valeurs. Résumez-les et imprimez la somme. C'est rapide et force le programme à rechercher chaque valeur.

Source

2009-12-29 15:35:45

Je peux confirmer qu'il peut y avoir d'énormes différences entre les versions de débogage et les versions de version. Dans mon exemple, j'ai un programme qui utilise hash_map et list. La version de débogage a duré plus de 8 minutes. La version de la version a fonctionné en moins d'une seconde. C'est une différence de temps de 480x au moins.

Source

2011-10-07 18:48:01 Aftershock

stl hash_map plus lent que la simple fonction de hachage?

Répondre

Questions connexes