[STL] rapidité vector vs map

:salut:
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 8O 8O

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

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

Citation:

---

Envoyé par befalimpertinent

:salut:
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 8O 8O

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

---

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.

Citation:

---

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é ;)

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:

---

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:

---

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.

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

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.

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 ?

Tu as raison pour la clé.
Et pour le vecteur "creux", il m'est nécessaire pour faire correspondre les indices de ce vecteur avec les indices de mon tableau de point3D (avec la map cet indice était la clé.). Il a donc une taille égale au nombre de points 3D. Seulement mon algo d'initialisation ne calcule que la moyenne pour certains points spécifiques et je ne connais pas à l'avance le nombre de ces points spécifiques.
Si je fais un vecteur et que je "push_back" seulement les valeurs qui m'intéressent, je ne sais pas quel indice de point je manipule. Je ne pourrai pas lui affecter sa nouvelle valeur par la suite.


J'me demande si j'ai été clair sur ce coup là ;) désolé :aie:

Moi perso je te propose tout d'abord d'utiliser ceci.
Quand tu commences à utiliser la STl pour ses conteneur il faut avoir ça en tête :
http://c.developpez.com/faq/cpp/?pag...hoix_conteneur
Avec ça déjà tu t'affranchi de pas mal de problèmes de design et autres soucis de rapidité etc...

Tout le problème est là : le choix du container.
En gros, faute de mieux, j'ai le choix entre une map avec comme clé les indices de points à bouger et de taille égale au nombre de ces points. Ou un vecteur creux de taille nombre_totale_de_points initialiser avec une valeur par défaut mais dont les indices correspondent à ceux de mon vecteur de point3D.

Même s'il est certain que le container associatif ne s'impose pas dans cas, je voulais éviter le vecteur "creux".

Question bête : tu ne peux pas accumuler directement dans le résultat ? Ca t'éviterait cette histoire d'indice, et par la même occasion un vector creux ou un std::map.

Citation:

---

Envoyé par Laurent Gomila

Question bête : tu ne peux pas accumuler directement dans le résultat ? Ca t'éviterait cette histoire d'indice, et par la même occasion un vector creux ou un std::map.

---

Malheureusement non !
L'algo en O(n²) travaille sur les positions initiales des points 3D.

Si je devait le résumé je dirais ceci :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

pair<Point3D,int> val_defaut = make_pair(Point3D(),0); vector<pair<Point3D,int> > my_vect(nb_points,val_defaut); for(;;) { for(int n =0; n< nb_points; n++) { if(specifique(n)) { my_vect[n]->first = calcul_coordonnees(points[n]); my_vect[n]->second ++; } }

---

Je n'ai pas préciser la condition d'arret du for. En gros on quitte cet algo quand une valeur seuil d'un critère de qualité calculé dans la boucle est atteinte. Raisonnablement je compte environ 500 tours.