Discussion :

[befalimpertinent]

J'ai pu constater récemment avec effroi une différence énorme en terme de temps d'exécution entre une std::map<int,int> par exemple et un std::vector<pair<int,int> > .
Je sais que ces deux containers n'ont pas les mêmes fonctions mais dans certains cas le vector<pair<>> peut s'avérer suffisant. Niveau perf le vector est largement plus rapide que la map. Pire dans mon cas effectuer des opérations sur un vector à 10 000 éléments m'est apparu beaucoup plus efficace qu'une map d'une 100 d'éléments. Ceci est surement lié a l'implémentation red-black tree de la map met quand même

J'en viens à penser à essayer autant que possible de virer toutes les maps de mon code. Qu'en pensez vous ?

[Invité]

sauf que ton vector n'assurement l'unicité de ta clé...
donc il est tres probable dans ce cas qu'il aille plus vite, vu qu'il fait moins de trucs

J'ai pu constater récemment avec effroi une différence énorme en terme de temps d'exécution entre une std::map<int,int> par exemple et un std::vector<pair<int,int> > .
Je sais que ces deux containers n'ont pas les mêmes fonctions mais dans certains cas le vector<pair<>> peut s'avérer suffisant. Niveau perf le vector est largement plus rapide que la map. Pire dans mon cas effectuer des opérations sur un vector à 10 000 éléments m'est apparu beaucoup plus efficace qu'une map d'une 100 d'éléments. Ceci est surement lié a l'implémentation red-black tree de la map met quand même

J'en viens à penser à essayer autant que possible de virer toutes les maps de mon code. Qu'en pensez vous ?

[Laurent Gomila]

Il est normal que certaines opérations soient plus rapides avec std::map, et vice-versa. Maintenant il faudrait savoir ce que tu fais exactement avec ton conteneur.

J'en viens à penser à essayer autant que possible de virer toutes les maps de mon code. Qu'en pensez vous ?

Que tu devrais plutôt chercher ce qui cloche dans l'utilisation que tu fais des conteneurs. std::map est efficace pour ce à quoi il est destiné, après si tu en fais n'importe quoi c'est ta responsabilité

[befalimpertinent]

C'est ça le truc.
J'ai l'impression qu'a partir du moment ou je connais la taille totale de ma map je peux en faire un vector<pair <> >. Dans mon cas je suis certain de ne pas avoir de problème d'unicité. Voila le genre de problème que je peux avoir :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
map<int,pair<Point3D,int> > my_map;//ou le premier int est l'indice d'un point

pour info : pair<Point3D,int> permet de calculer la position moyenne d'un point en accumulant les coordonnées dans Point3D et en divisant ensuite par l'int qui correspond au nombre d'accumulations.

/* ou */

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
vector<pair<Point3D,int> > my_vect(nb_point3d);

Une fois remplie, my_map ne référence qu'une centaine de points alors que mon my_vect est de taille égale au nombre totale de points ( + 10 000) même si 90 % des ses éléments sont des valeurs par défauts. Résultats des courses : malgré sa taille 100 x plus importante, my_vect est beaucoup plus rapide que my_map.
Map n'est surement pas le meilleur container dans ce cas. En même temps je suis sous VC 6.0 (indépendamment de ma volonté ) et ma version de STL ne dispose pas des hash_map.

[Laurent Gomila]

On ne sait toujours pas ce que tu fais avec ton conteneur. Recherche ? Suppression ? Insertion ? Parcours ?

[befalimpertinent]

Les valeurs sont simplement calculées dans une boucle en O(n²) où n est le nombre de points3D (impossible de faire mieux niveau coût).

Ensuite un parcours du container va permettre d'affecter la moyenne (égale à pair->first / pair->second ) au point concerné. Dans le cas du vector, seul les points de moyenne différente de la valeur par défaut (égale à make_pair(Point3d(),-1) sont modifiés.

Rien de bien sorcier en somme.
C'est l'étape d'initialisation qui est la plus gourmande, je ne peux par réduire sa complexité donc mon seul gain possible est sur la manière de stocker mes valeurs.

[Laurent Gomila]

Donc en gros, la clé que tu utilises pour ton std::map n'est rien d'autre qu'un indice, et ne sert finalement à rien ?

En tout cas dans ce que tu décris je ne vois rien qui nécessite un conteneur associatif. Par contre je ne comprends pas pourquoi avec std::vector tu as 90% d'éléments inutiles ?