stl map performance?

Vous devez d’abord comprendre ce qu’est une carte et que représentent les opérations que vous effectuez. Un std::map est un arbre binary équilibré, la recherche prendra O( log N ) opérations, chacune étant une comparaison des clés plus quelques extra que vous pouvez ignorer dans la plupart des cas (gestion du pointeur). L’insertion prend à peu près le même temps pour localiser le point d’insertion, plus l’allocation du nouveau noeud, l’insertion réelle dans l’arbre et le rééquilibrage. La complexité est de nouveau O( log N ) bien que les constantes cachées soient plus élevées.

Lorsque vous essayez de déterminer si une clé est dans la carte avant l’insertion, vous engagez le coût de la recherche et, en cas d’échec, le même coût pour localiser le point d’insertion. Vous pouvez éviter le coût supplémentaire en utilisant std::map::insert qui renvoie une paire avec un iterator et un bool vous indiquant si l’insertion s’est réellement produite ou si l’élément était déjà là.

Au-delà de cela, vous devez comprendre combien il est coûteux de comparer vos clés, ce qui MyStruct de ce que la question montre ( MyStruct peut en contenir un seul ou un millier), et vous devez en tenir compte.

Enfin, il se peut qu’une map ne soit pas la structure de données la plus efficace pour vos besoins et vous pouvez envisager d’utiliser soit un std::unordered_map (table de hachage) qui a prévu des insertions de temps constant (si la fonction de hachage est pas terrible ) ou pour les petits ensembles de données, même un tableau ordonné (ou std::vector ) sur lequel vous pouvez utiliser la recherche binary pour localiser les éléments (cela réduira le nombre d’allocations, au prix d’insertions plus coûteuses, mais si les types tenus sont assez petits, cela pourrait en valoir la peine)

Comme toujours avec la performance, mesurez puis essayez de comprendre où le temps est passé. Notez également que 10% du temps consacré à une fonction ou à une structure de données particulière peut représenter beaucoup, voire presque rien, selon l’application de votre application. Par exemple, si votre application effectue uniquement des recherches et des insertions dans un jeu de données, et que cela ne prend que 10% de la CPU, il vous rest beaucoup à optimiser partout!

Serait-il plus rapide de simplement faire une insert et de vérifier si la pair.second est false si la clé existe déjà?

comme ça

 if ( myMap.insert( make_pair( MyStruct, I* ) ).second == false) { //report error } else // inserted new value 

plutôt que de faire un appel à chaque fois?

Au lieu de map vous pouvez essayer unordered_map qui utilise des clés de hachage, au lieu d’un arbre, pour rechercher des éléments. Cette réponse donne des indications sur le moment de préférer unordered_map à la map .

Cela peut être long, mais pour les petites collections, le facteur le plus important est parfois la performance du cache .

Depuis que std::map implémente un arbre rouge-noir, qui [AFAIK] n’est pas très efficace en cache, utiliser peut-être la carte en tant que std::vector> serait une bonne idée, et utiliser la recherche binary là-bas [au lieu de chercher sur la carte], au minimum elle devrait être efficace une fois que vous commencez à regarder seulement [arrêtez d’insérer des éléments], puisque std::vector est plus susceptible de rentrer dans le cache que la map .

Ce facteur [cpu-cache] est généralement négligé et masqué de manière constante dans la grande notation O, mais il peut avoir un effet majeur sur les grandes collections.

De la manière dont vous utilisez la carte, vous effectuez des recherches sur la base d’une instance de MyStruct et, en fonction de votre implémentation particulière, la comparaison requirejse peut être coûteuse ou non.

Existe-t-il une autre implémentation que je pourrais vouloir utiliser? Je pense que je ne devrais pas écrire le mien mais je pourrais le faire si je pensais que c’était une bonne idée.

Si vous comprenez assez bien le problème, expliquez en détail comment votre mise en œuvre sera supérieure.

Est-ce que la map est la bonne structure? Si tel est le cas, la mise en œuvre de votre bibliothèque standard sera probablement de bonne qualité (bien optimisée).

La comparaison de MyStruct peut- MyStruct être simplifiée?

Où est le problème – redimensionnement? Chercher?

Avez-vous minimisé les coûts de copie et d’assignation des coûts pour vos structures?

Comme indiqué dans les commentaires, sans code approprié, il y a peu de réponses universelles à vous donner. Cependant, si MyStruct est vraiment énorme, la copie de stack peut être coûteuse. Il est peut-être judicieux de stocker les pointeurs sur MyStruct et de mettre en œuvre votre propre mécanisme de comparaison:

 template  struct deref_cmp { bool operator()(std::shared_ptr lhs, std::shared_ptr rhs) const { return *lhs < *rhs; } }; std::map, I*, deref_cmp> mymap; 

Cependant, c’est quelque chose que vous devrez profiler. Cela pourrait accélérer les choses.

Vous recherchez un élément comme celui-ci

 template  struct NullDeleter { void operator()(T const*) const {} }; // needle being a MyStruct mymap.find(std::shared_ptr(&needle,NullDeleter())); 

Inutile de dire qu’il y a plus de potentiel d’optimisation.