Discussion :

[tlemcenvisit]

Bonjour à tous,

J'ai fait une petite modification dans mon programme qui a généré un important temps de calcul.
Pour simplifier, ceci est un programme contenant deux bouts de codes qui font la même chose :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
double justePourVoir(std::map<double,double> mymap,int i)
{
	return mymap[i];
}
main()
{
clock_t aa,bb,cc;
std::map<double,double> mymap;
for(int i=0;i<500;i++)
	mymap[i]=rand();
double sum1=0,sum2=0;
aa=clock();
for(int i=0;i<500;i++)//1er bout de code
	sum1+=mymap[i];
bb=clock();
for(int i=0;i<500;i++)//2eme bout de code
	sum2+=justePourVoir(mymap,i);
cc=clock();
double t1=bb-aa;
double t2=cc-bb;
}

Quand j'exécute, j'ai t1=0 et t2=8000 !
Quelqu'un aurait une idée sur la source du problème?

D'avance merci !

[hiura]

La copie inutile de la map car elle n'est ni passée par pointeur, ni par référence.

[poukill]

Effectivement, le passage par référence est nécessaire :

Code :

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

1
2
3
4
5
 
double justePourVoir(const std::map<double,double> & mymap,int i)
{
	return mymap[i];
}

Plus d'infos ICI

[koala01]

Salut,

Pour commmencer, expliquons le fait que tes valeurs aléatoires soient identiques:

Avant de vouloir générer une valeur aléatoire tu dois initialiser le générateur, généralement en lui passant la valeur time(NULL) pour qu'il prenne... l'heure système en compte dans son algorithme.

Ensuite, la fonction rand (héritée du C, faut il le rappeler ) est un générateur aléatoire de... nombres entiers, dont la norme C garanti qu'il sera au minimum compris entre 0 et 32767.

Et là, les problèmes commencent

Il faut savoir qu'il n'est jamais bon de vouloir transformer "brut de force" un entier en réel, or c'est ce que tu fais.

En effet, les réels ont la sale manie de souffrir d'une imprécision, au delà d'un certain point.

La manière même dont les données sont représentées en mémoire est responsable de cette imprécision, et il existe, tant pour les double que pour les float, une valeur bien précise, nommé epsylon, en dessous de laquelle nous obtenons l'égalité étrange 1-epsylon == 1 == 1+ epsylon.

Autrement dit, lorsque tu va essayer de transformer ton "1" entier en "1" réel, il pourrait tout aussi bien valoir 0.999999999 que... 1.000000001 (avec peut etre plus ou moins de chiffres derrière la virgule).

Cette imprécision à elle seule justifie amplement le fait que l'on n'utilise que très rarement les réels pour représenter des clés de tri.

De plus, la conversion de réel en entier à la manière "brut de force" pose également de sérieux problèmes:

Par exemple, la conversion du réel 1.6 en entier donnera... 1, car la partie décimale est simplement perdue, alors que, selon les règles d'arrondi, cela aurait du donner... deux.

Si tu avais "correctement" réglé ton compilateur (AKA avec l'option "Wconversion" sous Gcc), il aurait déjà pu t'avertir que

|warning: conversion to 'int' from 'double' may alter its value|

De plus, il faut savoir que l'opérateur [] d'une std::map n'agit pas du tout de la même manière que l'opérateur [] d'un std::vector ou d'un tableau "C Style"

En effet, lorsque tu utilise un std::vector ou un tableau "C style", l'opérateur [] te permet d'accéder à l'élément dont l'indice est donné entre les crochets.

Or, une std::map n'est pas un tableau: c'est un conteneur trié utilisant d'un coté une clé pour effectuer le tri et la recherche et de l'autre une valeur représentée par la clé (et, bien que le vocable "tableau associatif" soit courremment utilisé, il me gène quelque peu par la fausse idée que peut induire le terme "tableau", car il s'agit en réalité d'un arbre binaire )

Et son opérateur ne va donc pas renvoyer la valeur dont l'indice est celui donné entre crochet, mais va effectuer la recherche approchée de la clé afin de renvoyer la valeur associée.

Et, si, par malheur, la clé n'existe pas, il va la créer sans vergogne.

Par "recherche approchée", je sais me tromper de terme (je ne l'ai plus en tete à l'instant), mais je veux indiquer le fait qu'il ne s'agit pas d'une vérification d'égalité.

Ce n'est pas un test du genre de si (clé en cours == clé recherchée) qui est utilisé, mai un double test du genre de

si ( clé en cours n'est pas plus petit que la clé recherchée ET clé recherchée n'est pas plus petit que la clé en cours), alors, c'est que la clé en cours est la clé recherchée.

Et, là encore, ce que j'ai écrit plus haut devrait t'aider à comprendre pourquoi l'utilisation d'un réel en tant que clé n'est pas idéale, et pourquoi c'est encore un moins bon plan que d'essayer de le comparer... à un entier...

[ram-0000]

Cela ne fait pas avancer le schmilblick mais je dit :
très belle réponse koala01

[koala01]

Cela ne fait pas avancer le schmilblick mais je dit :
très belle réponse koala01

Si, ca le fait avancer...

Déjà, ma réponse précise (sans dire où il doit arriver) qu'il faut un

Code :

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

srand(time(NULL));

dans la fonction principale.

De plus, la réponse sous entend qu'il ne faut pas utiliser une std::map<double, double>, même si elle ne dit pas ce qu'il faut utiliser

Allez, je suis bon prince, je proposerais une std::map<size_t, double> ou une std::map<size_t, size_t>

Enfin, elle met en garde contre l'utilisation de l'opérateur []... Il est vrai qu'elle aurait pu donner une alternative, faisons le maintenant:

Pour l'insertion, préférer insert sous la forme de

Code :

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

mymap.insert(std::make_pair(key, value));

Pour la recherche / sélection d'un élément : il faudrait préférer

Code :

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

1
2
3
std::map<KeyType,ValueType>::iterator it=mymap.find(key);
/* voire*/
std::map<KeyType,ValueType>::const_iterator it = mymap.find(key);

et pour obtenir la valeur associée à la clé, utiliser

Code :

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

(*it).second;

Maintenant que tu m'a forcé à tout mettre, le PO n'aura plus qu'à placer les bonnes instructions aux bons endroits

[ram-0000]

Cela ne fait pas avancer le schmilblick mais je dit :
très belle réponse koala01

Si, ca le fait avancer...

Pas de méprise, quand je disais "cela ne fait pas avancer le schmilblick", je parlai de mon post qui dit que ta réponse est jolie.