Pages : 1
#1 Le 12/02/2008, à 16:15
- Skippy le Grand Gourou
[C++] map ou vector ?
Salut,
Une question me taraude : je veux associer à un certain nombre de valeurs non entières d'autres valeurs non entières. Par exemple :
0.1 -> 5.0
0.2 -> 4.5
0.3 -> 4.0
0.4 -> 3.5
0.5 -> 3.0
0.6 -> 2.5
0.7 -> 2.0
0.8 -> 1.5
0.9 -> 1.0
1.0 -> 0.5Mon code devra accéder à la seconde en fonction de la première. Il doit si possible être optimisé en terme de temps (et si possible de consommation), il y a énormément d'accès, et ils ne sont pas séquentiels : on prend la valeur, on l'utilise pour faire quelque chose. Pour le nombre d'entrées, je dirais 1000 à 10000, peut-être plus.
Est-ce raisonnable ? Ma question : est-il préférable dans un tel cas d'utiliser une map, ou de transformer la valeur d'entrée en un entier et d'utiliser un tableau ?
Mici. 
Hors ligne
#2 Le 12/02/2008, à 17:33
- Karl_le_rouge
Re : [C++] map ou vector ?
Avant de chercher à optimiser, demandes-toi quelle structure te convient le mieux.
Dans ton cas (tableau associatif), je dirais que ce serait plutà´t le map surtout si tu dois insérer et supprimer des données.
Si tu tiens absolument à utiliser un std::vector ou parce qu'après profilage, tu estimes que c'est nécessaire, tu peux utiliser un std::vector<std::pair<int, double> > ; ou créer une str
"premature optimization is the root of all evil" Tony Hoare
Hors ligne
#3 Le 12/02/2008, à 18:04
- Skippy le Grand Gourou
Re : [C++] map ou vector ?
Avant de chercher à optimiser, demandes-toi quelle structure te convient le mieux.
Ben oui, ça tombe bien c'est la question... 
Dans ton cas (tableau associatif), je dirais que ce serait plutà´t le map surtout si tu dois insérer et supprimer des données.
Non, j'avais oublié de le préciser, la table est créée au départ et ne bouge plus, juste accès en lecture.
Si tu tiens absolument à utiliser un std::vector ou parce qu'après profilage, tu estimes que c'est nécessaire, tu peux utiliser un std::vector<std::pair<int, double> > ; ou créer une str
"premature optimization is the root of all evil" Tony Hoare
Je tiens pas spécialement à utiliser un vector, je cherche la structure optimale. Je ferai pas de profilage, c'est pour rentrer un tout petit bout de code dans une unsine à gaz que je n'ai pas créé, mais mon code ne doit pas la faire ralentir.
Donc étant donné le nombre d'entrées et l'accès juste en lecture, tu me conseillerais toujours la map ?
Edit : Ah oui tiens, j'avais pas pensé au vector de paire (que j'utilise pourtant dans un autre code). Et je viens de me souvenir de ce topic que j'avais créé pour une autre occasion, je vais le relire. 
Edit2 : Ah oui, et les données sont ordonnées : ordre croissant pour le premier chiffre, décroissant pour le second.
Edit3 : Non, le vector de paire ça peut pas coller : je veux B connaissant A.
Dernière modification par Skippy le Grand Gourou (Le 12/02/2008, à 18:22)
Hors ligne
#4 Le 12/02/2008, à 19:19
- Aurel34
Re : [C++] map ou vector ?
perso je partirai aussi sur une map, en faisant une petite interface,par exemple deux fonctions: une qui crée la structure au début et une "get_element(double n)".
comme ça tu te prends pas la tête et si ça suffit vraiment pas tu t'embêteras pas pour modifier
#5 Le 12/02/2008, à 19:36
- Skippy le Grand Gourou
Re : [C++] map ou vector ?
perso je partirai aussi sur une map, en faisant une petite interface,par exemple deux fonctions: une qui crée la structure au début et une "get_element(double n)".
comme ça tu te prends pas la tête et si ça suffit vraiment pas tu t'embêteras pas pour modifier
Non non, pas d'interface. Le code initial est déjà truffé d'optimisation du genre passage systématique de "const uchar&" au lieu de simple "int", etc... Et faut que je m'adapte, et j'ai pas le temps de faire des tests et tout ça. Donc je veux la structure optimale, maintenant tout de suite.
Dans le lien du topic que j'ai donné quelqu'un m'avait répondu :
La map garanti un acces constant en recherche (comme un tableau dont l'index correspond à la clé de la map) sauf que le traitement dans le cas de la map est plus lourd. Ce sera un temps constant genre de 1 instruction machine pour le tableau, 20 instruction machine pour la map voire peut être 100 pour la map.
Dans ce cas le choix est clair, je multiplie mes float par 100 et je caste en int, ça me donne l'indice du tableau, et j'ai mon résultat en beaucoup moins d'opérations.
à‡a semble raisonnable ?
Hors ligne
#6 Le 12/02/2008, à 19:40
- Aurel34
Re : [C++] map ou vector ?
c'est rapide mais c'est pas souple.
disons qu'il faudra pas évoluer vers autres chose en termes d'indices...
mais sinon oui il y a moyen que ça tourne vite, et plus qu'une table de hachage (ce qui est somme toute naturel).
#7 Le 12/02/2008, à 19:40
- Aurel34
Re : [C++] map ou vector ?
(ça me fait penser aux tables de sinus pour les calculs 3D d'il y a ... longtemps:))
#8 Le 12/02/2008, à 19:46
- Skippy le Grand Gourou
Re : [C++] map ou vector ?
(ça me fait penser aux tables de sinus pour les calculs 3D d'il y a ... longtemps:))
C'est exactement ce que je veux faire (avec une fonction un peu plus compliquée que des sinus).
Et pour l'évolution, il n'y a pas à s'inquiéter, je vais faire ça souple (et en plus il y a des chances pour que ce ne soit que temporaire).
Dernière modification par Skippy le Grand Gourou (Le 12/02/2008, à 19:47)
Hors ligne
#9 Le 13/02/2008, à 08:43
- Aurel34
Re : [C++] map ou vector ?
C'est exactement ce que je veux faire (avec une fonction un peu plus compliquée que des sinus).
oui mais elle prend quelle place ta fonctin ?
le sinus ça se faisait en quelques octets (simu du pendule par différences finies)
#10 Le 13/02/2008, à 09:37
- Skippy le Grand Gourou
Re : [C++] map ou vector ?
Elle prend pas beaucoup de place en soit, la difficulté réside dans le fait que je veux l'abscisse en fonction de l'ordonnée et qu'elle n'est pas facilement inversible (produit d'exponentielles, dont une exponentielle d'exponentielle). Jusque là je faisais une dichotomie, mais une table serait beaucoup plus simple...
Et pour la taille de la table ça dépend de la précision demandée, entre 1000 et 10000 je pense, une précision supérieure n'est pas censée apporter grand'chose (Par contre comme c'est pas linéaire, ça pourrait être intéressant de faire une table non linéaire (pas [0.1,0.2,0.3,0.4,0.5] mais [0.05,0.1,0.2,0.4,0.8] par exemple), mais c'est bon, je vois comment faire. )
Hors ligne
Pages : 1