Comment vérifier si mon hash personnalisé est bon dans hash_map?

J'ai écrit un hachage personnalisé pour ma clé personnalisée dans stdext :: hash_map et je voudrais vérifier si le hasher est bon. J'utilise STL fourni avec VS 2008. Une vérification typique, comme je sais, est de vérifier l'uniformité de la distribution parmi les seaux.Comment vérifier si mon hash personnalisé est bon dans hash_map?

Comment dois-je organiser un tel contrôle correctement? Une solution qui me vient à l'esprit est de modifier les sources STL pour ajouter une méthode à hash_map qui parcourt les buckets et fait le sujet. Y a-t-il de meilleurs moyens?

Peut-être, dériver de hash_map et créer une telle méthode?

Source

2010-03-03 flashnik

Je voudrais exécuter un (grand) jeu de données via stl :: hash_map. Une fois fait, je collectionne les résultats pour tous les godets en utilisant la méthode suivante

De hash_map:

size_type elems_in_bucket (size_type __n) const;

Enfin, je ne calcule l'écart-type (SD) du élém à -bucket distribution.

Je ferais ce qui précède pour différentes fonctions de hachage. Quelle que soit la fonction de hachage résultant en SD minimum est le gagnant (pour ce jeu de données).

Source

2010-03-03 23:28:50 Arun

Oui, ce serait parfait, mais je n'ai pas ce membre hors de la boîte. Dois-je définir _HAS_TRADITIONAL_STL? Quels effets secondaires cela causerait-il? – flashnik

J'ai trouvé :) Dans la STL de mon compilateur (MS VS 2008) cette méthode est appelée 'bucket_size'. Grand merci! – flashnik

@flashnik: De rien. N'hésitez pas à commenter si vous avez des questions de suivi. – Arun

Votre meilleur pari pourrait être de ne prendre que votre algorithme de hachage à un tableau de ints et compter le nombre de fois que chaque seau de hachage est frappé, compte tenu des données réelles. (Je suggère de prendre la STL hors de l'équation ici, vraiment.)

Si vous finissez par voir un écart important dans vos comptes avec de grands ensembles de données du monde réel, votre algorithme de hachage génère beaucoup de collisions quand il Il y a beaucoup de seaux vides (ou vides) disponibles.

Notez que «écart élevé» est un terme relatif. Un bon algorithme de hachage est un processus aléatoire déterministe et tout processus aléatoire a une chance de générer des résultats étranges, donc testez souvent, testez bien, et dans la mesure du possible, utilisez votre domaine réel comme source de vos tests et de vos contrôles.

Source

2010-03-03 23:24:48 Sniggerfardimungus

Oui, c'est ce que je vais faire. Mais AFAIK je ne peux pas accéder aux compartiments (et à la quantité d'éléments dedans) en dehors de hash_map. Maintenant, je vois deux façons: modifier les sources STL ou dériver sa propre classe de hash_map avec une méthode appropriée. Je préférerais la deuxième solution. Y a-t-il d'autres moyens? – flashnik

... C'est pourquoi user30997 dit dans le premier paragraphe de retirer la STL de l'image et d'exécuter simplement votre méthode de hachage sur les données réelles et les compteurs incrémentés. – vladr

Eh bien, je crains que différentes réalisations STL puissent fonctionner différemment avec les résultats de hachage. Par exemple, en utilisant 'this-> comp (_Keyval) & _Mask' pour déterminer si un busket fonctionne correctement si _Mask est' 2^N -1'. Et _Mask est déterminé par un foncteur hasher (c'est une multiplication de min_buckets fourni par hasher). Dans tous les autres cas, cela n'est pas équivalent à un rappel 'this-> comp (_Keyval)% _Mask'. – flashnik

Comment vérifier si mon hash personnalisé est bon dans hash_map?

Répondre

Questions connexes