J'ai fait une analyse de la performance sur le logiciel que je développe et j'ai constaté que les recherches sur un dictionnaire mondial d'URL deviennent environ 10% de l'heure de la phase "chargée" de l'application. Le dictionnaire est implémenté comme une STD C ++ STL :: Carte, qui a des recherches O (LG N). Je vais le déplacer dans un Hash_Map, qui a des recherches temporelles approximativement fixes. La classe STL String n'a pas de propriété de code de hachage, et cela ne cache certainement pas un code de hachage. Cela signifie que chaque recherche nécessite de ré-générer le code de hachage.
Je suis sceptique que la mise en cache du code de hachage vaut l'effort. Cela signifierait changer de nombreuses lignes de code pour utiliser une nouvelle classe de chaîne avec une propriété de code de hachage en cache. Étant donné que la mise en œuvre actuelle connecte (n) des comparaisons de chaînes complètes à chaque recherche, je pense que la réduction de la travertielle de chaîne (par la fonction de hachage) par recherche est une grosse victoire.
Quelqu'un a-t-il de l'expérience avec des codes de hachage de chaîne de cache? A-t-il déjà prouvé la peine d'effort?
5 Réponses :
Un mot d'avertissement.
Bien qu'une carte de hachage puisse avoir des recherches sur le temps fixes, cela peut également finir par avoir des recherches O (n). Bien que ce ne soit pas un cas commun, cela se produit.
Donc, alors que vous devez toujours payer pour le temps O (journal n) sur une carte, vous êtes également garanti que cela ne sera pas pire.
Sur les implémentations écrites par des singes écrasant un clavier.
Cela dépend également de la fonction de hachage? Une bonne fonction de hash devrait laisser peu de collisions. Si je me rappelle correctement, le facteur de charge pourrait également jouer une pièce, en fonction du type de hashmap.
@Gman: Je suppose que beaucoup de singes ont trouvé un emploi rémunéré en tant que programmeurs et ghostwriters shakespearseariens, alors parce que j'ai vu des hayes assez mauvaises.
@Skurmedel: Oui, un hachage qui fait retour 0; ou une autre chose de merde, ou une carte de hachage d'une taille de 1. aucun de ceux qui n'existent vraiment pas dans le code réel. Les cartes de hachage sont presque toujours ~ O (1). @Steven: yuck; Pourquoi les gens font-ils leurs propres hachages? C'est aussi stupide que penser qu'il est facile de faire un bon générateur au hasard. :)
@Gman: Entrée malveillante conçue pour entrer en collision pour votre hachage? ;-)
Sauf si vous avez une fonction de hachage parfaite conçue pour votre ensemble de saisies de correctifs, cela peut arriver. Il y a une fois une fois il y a environ 10 ans et cela m'a rendu prudent des tables de hachage depuis.
@Gman: Peu importe de faire la leur propre comme cueillette au hasard un connu qui se trouve être terrible. Il y a beaucoup de hashes là-bas dans un code réel qui a généralement une mauvaise distribution, ou d'au moins d'énormes talons d'acides lorsqu'ils sont soumis à une certaine gamme d'intrants. Donc, oui, je suis généralement d'accord pour dire que nous devrions faire confiance aux algorithmes de hachage dans des bibliothèques fiables, car il existe également de nombreux algorithmes qui donnent de bons résultats pour presque toutes les contributions.
@R Samuel Klatchko: Si vous êtes vraiment préoccupé par la pire performance d'une table de hachage, vous pouvez le limiter à O (log n) au lieu de O (n) (Utilisez des arbres au lieu de listes pour les collisions de hachage).
@ Jerry: Oui, intéressant, en particulier si la structure des arbres contribue à éviter beaucoup de copier quand il est temps d'élargir la table. Bien que je ne sois pas sûr que cela puisse.
@Jerry - idée intéressante. Connaissez-vous de toute mise en œuvre de ONUORDEDED_MAP qui utilise cela?
@Steven Sudit: Pour la plupart, lorsque vous l'utilisez, vous n'êtes tout simplement pas développé la table - la dégradation ne commence à devenir perceptible si vous remplissez si vous remplissez la table par une marge énorme (> 100000: 1 ). @R Samuel: J'ai fait une mise en œuvre (essentiellement juste un std :: vecteur
@R Samuel: Vous ne pouvez pas implémenter Unommked_map de cette façon, car le type de clé d'un nonOrded_map n'est pas nécessairement ordonné (no opérateur << / code > ou std :: moins spécialisation), vous ne pouvez donc pas nécessairement avoir une carte d'eux. Vous pouvez faire ce que Jerry a fait, qui définit votre propre carte associative qui nécessite que les clés soient habilitées et commandées (et qui prend les paramètres de fonctionnement supplémentaires facultatifs correspondants).
Je n'ai pas d'expérience avec la mise en cache des codes de hasch, mais j'ai fait du travail récemment convertissant std :: map à std :: tr1 :: non ordonnée_map . Deux pensées viennent à l'esprit. Tout d'abord, essayez de profiler pour le profil que le changement relativement simple, car il
Bonjour Kristo, merci pour les conseils. Pour répondre à votre question, j'ai déjà tué environ 40% de l'heure de charge précédente et je suis à court de fruits à suspendre. Que 10% sont relativement juteux et à la portée.
vous aurez bien sûr besoin de profiler pour vérifier vos résultats. Changez-vous à une carte de hachage, puis voyez où la plupart de votre temps est dépensé. À moins que vous soyez des clés de hachage à gauche et à droite, je doute que la plupart de votre temps soient passés là-bas. Le hachage est destiné à être une opération rapide, sinon une carte de hachage n'aurait aucun avantage sur un conteneur commandé.
Le compilateur lui-même saura si une chaîne n'a pas été modifiée et peut probablement cacher le résultat pour vous (dans le même champ). Cela dit, vous ne veuillez pas em> vouloir hériter de plutôt, faites un Vous devez alors surcharger le (aller par boost ici, pas TR1; Je ne sais pas à quel point ils sont similaires) et c'est tout. Notez que dans la paire, code> string code> et Vous voulez une fonction d'assistance: p> std :: string code>; Les classes STL n'étaient pas faites pour cela. P> std :: paire code> et transmettez-le autour de: p> std :: paire Hash_Value Code> Fonction Pour votre type, dans le même espace de noms que la paire est définie: p> taille_t code> est immuable. C'est parce que si la chaîne code> modifie code>, votre hachage est faux. Nous le faisons donc const code>, et nous pouvons aussi bien rendre le hash const code> aussi. P> string_hash_pair make_string_hash(const std::string& pStr)
{
return std::make_pair(pStr, boost::hash_value(pStr));
}
Si je comprends bien, le hachage de la clé est calculé exactement une fois pendant la recherche, quelle que soit la taille de la table, alors la mise en cache de ne pas vous aider beaucoup. Le hachage est calculé lors de l'insertion, mais chaque article n'est inséré qu'une seule fois.
@Steven: C'est calculé une fois par look-up. Mais si vous recherchez la même clé à plusieurs reprises, vous pouvez calculer le hachage plusieurs fois. Je pense qu'il veut éviter cela.
C'est vrai. Je ne peux pas dire à l'OP si la même clé sera levée plus d'une fois, mais si oui, alors cela le justifierait davantage. Bien entendu, il peut également y avoir des moyens de réorganiser le code afin que les valeurs ne soient pas levées plus qu'absolument nécessaires.
Lorsque vous comparez la carte de hachage sur la carte, essayez également une structure de trie ou une structure de données associée (tout ce que vous pouvez sortir de l'étagère):
Malheureusement, vous pouvez passer beaucoup de temps à vous soucier de la convivialité de la cache. À cet égard, une trie est similaire à l'arbre que vous avez déjà et une carte de hachage sera probablement mieux comportée qu'un arbre naïvement attribué.
aussi, je suis un peu confus par la question. Si vous recherchez la même chaîne objet plusieurs fois, de telle sorte que la mise en cache de sa valeur de hachage est utile, ne devriez-vous pas simplement mettre en cache le résultat de la recherche? Le point entier d'une table de hachage est que différents objets qui sont égaux de valeur de valeur à la même valeur. Si vous n'utilisez pas le même hachage plusieurs fois à partir de cordes distinctes contenant les mêmes personnages, votre table de hachage ne fait probablement pas son travail.
Si vous voulez mettre en cache les valeurs des clés déjà dans la table de hachage, c'est jusqu'à la table de hachage.
J'ai fait des comparaisons d'un ensemble set et non ordonné avec des chaînes 4K - 64K dans mon dictionnaire.
J'ai trouvé qu'un STD :: Set et Unorded_sed comptait environ le même point d'exécution de ma situation car le calcul de Hash_Value a pris environ 80% du temps d'exécution pour l'ensemble non ordonné.
Il a nain sur les économies de recherche (boost d'occasion :: Hash_Value pour STD :: String FWIW)
ymmv, et pour les cas généraux, je dirais un profil et ne vous laissez pas berner par des écailles théoriques qui ne tiennent pas compte de l'architecture de la CPU, etc. Une carte de hachage peut courir plus lentement en raison du coût de hachage et consomme plus de mémoire .
Mon cas d'utilisation est que je stocke des informations pendant une longue période et que cela reçoit des mises à jour régulièrement, cela ne modifie pas le hachage d'informations_ID mais peut changer d'autre contenu.
Chaque mise à jour est ensuite transmise à ma fonction de recherche pour décider si je dois en informer de l'extérieur pour cette mise à jour.
La liste des informations_ids à notifier est à cette recherche et peut changer de manière indépendante des informations.
En mettant en cache le hachage pour l'information_ID, il est susceptible d'être réutilisé 10 de temps pendant la durée de vie des informations.
Mes deux lignes changent de cache le hachage amélioré d'une commande d'exécution de ONUNERDED_SED_SHED> X8
Test Set: Benché sur MSVC 2012 Mise à jour 4 Les entrées 1M ont levé 10 fois chacun contre un dictionnaire 4K et 64K: Tous sauf 10 chèques sont des erreurs dans 4K, 500 hits pour 64k (plus Aardvarks :))
SET: 1373 MS / 1938 MS
Multi-ensemble: 1376 MS / 1913 MS
Seau 64k Initialisé 64K / 0.5 Facteur de charge: 168 ms / 362 ms
Unommked_set 4K / 1.0: 331 MS / 452 MS
c.f pré-cache
Unommked_set 64K / 0.5: 1519 MS / 1881 MS
FWIW Les mêmes choses courent contre Mingw 4.9.1 -O3
SET: 2003 MS / 2490 MS
Multiset: 1978 MS / 2306 MS
Seau 64k InitialEded_set 64K / 0.5 Facteur de charge: 140 ms / 605 ms
Unommked_set 4K / 1.0: 318 MS / 683 MS
c.f pré-cache
Unommked_set 64K / 0.5: 1619 MS / 2455 MS
Le hachage prend une très petite quantité de temps. Comment avez-vous l'intention de garder ces chaînes en cache de hasch? Je veux dire, si vous gardez une chaîne autour qui a déjà le hash, pourquoi ne pas simplement garder l'objet associé à ce hachage à la place?
Vous ne pouvez pas envelopper vos chaînes dans un objet auxiliaire qui garde le hasch?
En outre, n'utilisez pas
hash_map , c'est une extension ancienne. UtilisezUnommked_map au lieu de TR1 ou de boost.La mise en cache des hachages ne peut être sûre que pour des objets immuables, quelles chaînes ne le sont pas. Autre que cela, c'est une complication majeure, car vous devriez stocker un tuple combine le hachage avec le haché. Je ne le recommanderais pas à moins que vous ne shakiez quelque chose de vraiment gros et vous avez comparé le code dans des conditions réalistes et que vous avez trouvé la différence importante.
@Skurmedel: Si je devais mettre en cache le code de hachage, ce serait en dérivant de la classe de chaîne standard et en ajoutant la fonctionnalité nécessaire, mais tous les clients qui génèrent les chaînes devraient alors utiliser la nouvelle classe de cordes. C'est beaucoup de code à changer, c'est pourquoi je suis réticent à cache. @Gman, merci, je vais jeter un oeil à Unorded_map.
@David: dériver de classes STL est une mauvaise idée; ils ne sont pas faits pour cela.
Question rapide: Nous parlons de O (LG N), mais quel est le
n dans ce cas?@David Glelfelter: Sans recommander la mise en cache des hachages, je penserais que la bonne façon serait de créer un tuple qui contient une chaîne régulière (const) et une valeur de hachage, de telle sorte qu'il renvoie cette valeur de hachage en cache. L'appelant l'examinerait par hash puis la déréférence la chaîne.
Qui était ma suggestion dès le début;) ... mais j'avais une paire d'esprit.
@Skurkmedel: Oui, et votre réponse a la priorité. On dirait que cette solution impliquerait une touche
STD :: paire> , avec un évaluateur hachage qui prend la paire intérieure et renvoie sa clé.@Steven: Aux fins d'un hachage, la clé n'a mieux de changer, même si l'objet est immuable - sinon vous ne le retrouveriez plus jamais.
@Joel: Pour clarifier, la clé doit être immuable, de sorte qu'un hachage déterministe de celui-ci ne change jamais.
@Steven Sudit: Pas de problème. Vous semblez beaucoup plus surviennent dans ces questions que moi quand même :) (Intéressant ancestrale, votre typographie de mon nom a transformé en un autre mot suédois :))