Alternative à stdext :: hash_map pour des raisons de performance

Question

Je travaille sur une application hautes performances où tous les appels doivent être justifiés. J'ai une carte qui est utilisée une fois au début de chaque transaction pour faire une recherche que je voudrais améliorer. La carte est chargée au démarrage et ne change pas après cela.

La clé dans la carte ci-dessous est une chaîne std :: mais elle peut être changée en tableau de char si nécessaire. C ou C++ comme solution est bien.

typedef stdext::hash_map<std:string, int> symbols_t; 

Est-ce que quelqu'un connaît d'autres solutions qui pourraient éliminer la recherche ou être plus rapide?

Merci d'avance pour votre aide.

Autres infos sur les modifications:
1. La hash_map contient actuellement 350 000 éléments.
2. Chaque valeur de clé a généralement une longueur comprise entre 4 et 10 caractères.
3. Des informations sont reçues sur un rappel d'une API tierce. Le rappel reçoit un symbole qui est utilisé comme valeur clé lors de la recherche de la carte. Le reste du logiciel est dérivé de l'int retourné à partir de la recherche de carte. MERCI: Merci à tous pour votre contribution. Vous m'avez donné quelques pistes à explorer. Je vais certainement essayer ces derniers. J'apprécie l'aide.

Answer 1

Je dirais que nous manquons d'informations ici pour vous dire de façon fiable ce qu'il faut faire.

Vous voudrez peut-être être plus précis sur la raison d'être de la recherche et sur le coût algorithmique global de vos fonctions.

Si vous encombrer le code avec des hacks laids pour gagner 1 microseconde constante dans une fonction dont le coût algorithmique est O(n²) où il pourrait être O(n), vous perdez votre temps sur le mauvais problème.

Sans plus de détails, nous ne pouvons pas vraiment dire. Code

Answer 2

Hand-code un hachage-carte qui est plus accordé à vos données.

1. fonction de hachage simpliste qui est assez bon
2. utiliser un C-matrice creuse qui est assez grand pour ne pas avoir des collisions pour vos données
3. assurez-vous que tous les appels sont inline
4. Assurez-vous de ne jamais copier ou convertit des chaînes

5. Écrivez du code pour générer la source C pour ce tableau C. Il va ressembler (en utilisant 0 pour aucune entrée):

   int symbols[] = { 0,0,0,0,0,0,5,0,0,0,0,0,3,0,0,0,0,0,0,2 /* etc */ }; 
   

   Le code que vous écrivez pouvez rechercher une fonction de hachage où il n'y a pas de collisions pour vos données. Peut-être est-ce quelque chose d'aussi simple que les deux premiers caractères du symbole (ou premier 4) comme int. Si vous ne vous souciez pas de l'espace, vous n'avez pas besoin de faire un hachage parfait pour toutes les données possibles, juste un rapide qui est parfait pour les données que vous avez.

L'indice de tableau est simple_hash(string& s)

Rappelez-vous que si vous modifiez les symboles, vous pouvez avoir à réécrire le hachage et certainement besoin de régénérer la table.

EDIT: en fonction de la réponse de @ feu - le code # 5 est écrit pour vous et est appelé gperf

Answer 3

Si vous avez vraiment besoin d'une hash_map calée sur les chaînes, vous pourriez essayer de personnaliser la fonction de hachage. Si vos chaînes sont principalement uniques dans (disons) les quatre premiers caractères, alors écrivez une fonction de hachage personnalisée qui ne regarde que les quatre premiers caractères d'une chaîne, et faites en sorte que hash_map l'utilise. Voici un exemple:

struct CustomStringHash: std::unary_function<std::string, size_t> 
{ 
    size_t operator()(const std::string & s) const 
    { 
     switch (s.size()) 
     { 
       case 0: 
        return 0; 
       case 1: 
        return s[0] + 1; 
       case 2: 
        return (s[0] << 8) + s[1]; 
       default: //3 or more chars long, plus a terminating null 
        return *reinterpret_cast<const uint32_t *>(s.c_str()); 
     } 
    } 

Si vos chaînes sont 8-12 caractères en moyenne, et la plupart du temps unique dans les quatre premiers caractères, la personnalisation puis la fonction de hachage pourrait accélérer les recherches tout à fait significative.

Answer 4

Comment pouvons-nous vous conseiller pour éliminer votre recherche puisque vous ne nous dites pas ce que vous cherchez ou pourquoi? Nous aurions besoin de beaucoup plus de détails algorithmiques. En ce qui concerne les performances, l'utilisation ou non d'un hash_map dépend de la complexité. Hashmaps ont (si vous avez une bonne implémentation, de façon réaliste) O (1) lookup, insertion. Mais les frais généraux constants peuvent être assez élevés. Si vous avez un faible nombre d'entrées, vous pourriez souffrir ici et bénéficier d'une std :: map. Vous pourriez également souffrir de problèmes de cohérence de cache si de nombreux éléments différents de la carte sont fréquemment utilisés et pourraient envisager une sorte de tableau trié à la place.

Answer 5

Cette carte est-elle complètement constante ou change-t-elle entre les invocations de programme? Pour les hachages constants (connus au moment de la compilation), il existe un programme gperf, qui génère une table de recherche O (1) rapide et garantie.

En outre, il pourrait être utile de comprendre votre problème si vous nous dites pourquoi et comment exactement les recherches de carte ralentissent votre code.

Answer 6

Une table de hachage est généralement assez rapide O (1) et nous ne pouvons pas vous dire si vous pouvez vous débarrasser de la table de hachage sans connaître toute la structure de votre application. Ce n'est peut-être pas possible.

Je ne sais pas comment est mis en œuvre stdext::hash_map<std::string,T>, mais un prefix tree est probablement une solution mieux . C'est l'équivalent d'une table de hachage avec une fonction de hachage parfaite.

 s 
     | 
     t 
    / \ 
    o  a 
    |  | 
(p,42) r 
     | 
     (t,69) 

Il vous donnera la valeur correspondant à votre chaîne en O (1) maximum 10 itérations (longueur maximale de la chaîne) et à réduire le coût de l'espace de stockage des clés.

Answer 7

Voici un article sur la performance du hash_map, où est présenté un remplacement d'accueil qui devrait effectuer beaucoup mieux:

http://www.codeproject.com/KB/cross-platform/BenchmarkCppVsDotNet.aspx

Voici une liste des autres tests de performance:

http://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/http://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/
http://tinodidriksen.com/2009/10/04/cpp-map-speeds-msvc-edition/

expérimenté qui std_ext :: hash_map perfo Rmed mal quand plus de 25.000 éléments, où les recherches sont devenues plus lent que le nombre d'éléments a augmenté. Changer pour boost :: unordered_map a résolu le problème.