[debutant] problemes de temps

**dervish** · 03/08/2004, 15h02

Bonjour,
je débute en C++ et j'ai un petit soucis avec la mesure du temps mis par des algos...
J'ai trois versions de tri à bulle (versions avec différents reaffinements), j'initialise 3 tableaux identiques d'un milliers de valeurs générées aléatoirement.
Je mesure le temps d'execution avec clock() avant et après l'exec de la fonction.
Et je me suis apperçu, que le classement des trois fonctions est différent selon l'ordre dans lequel je les exécute

P.S: il va s'en dire que chacune des méthode s'applique à son propre tableau de données.
Si quelqu'un pouvais m'éclairer...
merci d'avance

**la drogue c'est mal** · 03/08/2004, 15h15

est ce que les 3 tableaux sont identiques ( au niveau du contenu ) ?

**dervish** · 03/08/2004, 15h18

oui. C'est bien ça le problème...
(au fait, je tourne sous linux et me sert d'anjuta)

**bjousse** · 03/08/2004, 15h21

Est ce que quand tu fais tournenr deux fois de suite la même fonction, le temps est différent ?

**dervish** · 03/08/2004, 15h28

oui mais pas de manière significative...

**Grulim** · 03/08/2004, 15h43

Envoyé par dervish

Bonjour,
Je mesure le temps d'execution avec clock() avant et après l'exec de la fonction.
Et je me suis apperçu, que le classement des trois fonctions est différent selon l'ordre dans lequel je les exécute

il me semble que les mesures de temps avec clock() sont très imprécises et qu'il vaut mieux utiliser getimeofday()...
je crois qu'il y a une classe dans boost qui s'occupe de ce probleme.

**Trap D** · 03/08/2004, 16h14

Salut

Le premier tri est-il toujours un peu plus long que s'il n'est pas effectué le premier ?

**freddy766** · 03/08/2004, 17h02

Salut,
si ton probleme est du au temps d'execution, voila les fonctions que je te recommande (par ordre de precision) :

Code :

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

1
2
3
4
5
 
1/ QueryPerformanceCounter (); //Windows
2/ gettimeofday ();
3/ GetTickCount();  //Windows
4/ clock();

Si tu veux qulques exemples pour les executer, fais moi appel.

**dervish** · 04/08/2004, 01h14

En fait, la performance des différents tris dépends (surtout pour celui qui est à priori le + optimisé) de la place qu'ils occupent dans l'ordre de réalisation des fonctions de tri... C'est cela qui m'étonne
P.S: si vous voulez je peux metre le code en p.j...

**Luc Hermitte** · 04/08/2004, 01h33

La compléxité de certains algos n'est pas "fixe". Notament le quicksort a une complexité dans le pire des cas (éléments déjà triés) en O(N²).

Sinon, prend de très grosses structures initialisées aléatoirement, et trie les plusieurs fois si tu veux avoir des mesures qui aient un quelconque sens.