temps d'execution - clock ()
Bonjour,
Voilà je cherche à comparer le temps d'execution pour comparer 2 méthodes qui recherchent le pgcd de 2 nombres.
J'ai décidé d'utiliser la fonction clock (), je sais que cette fonction donne une valeur du temps approximative mais vu que je cherche le pgcd de int_max et int_max - 1 le temps d'exécution est important (environ 30 secondes pour la première méthode).
Le problème est le suivant :
PGCD = 1 duree methode 1 : 30839000000 ns
PGCD = 1 duree methode 2 : 0 ns
Process returned 0 (0x0) execution time : 30.886 s
Press any key to continue.
le temps d'execution de la 2ème méthode est nulle, et j'arrive pas à savoir si c'est parceque :
- la deuxième méthode est tellement rapide que clock arrive pas à calculer son temps d'éxecution.
- Il y a un souci au niveau du code.
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| /* --------------------------------------------------------------------------
Fonction : Comparer la complexite temporelle de 2 methode de calcul pour le
PGCD
-------------------------------------------------------------------------- */
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <limits.h>
/* --------------------------------------------------------------------------
permuter ()
--------------------------------------------------------------------------
Role : Permute 2 nombre (long)
-------------------------------------------------------------------------- */
void permuter (long *x, long *y)
{
long tmp = *x;
*x = *y;
*y = tmp;
}
/* --------------------------------------------------------------------------
trouver_pgcd_methode_1 ()
--------------------------------------------------------------------------
Role : Retourne le PGCD de 2 nombres par la méthode de decrementation
-------------------------------------------------------------------------- */
long trouver_pgcd_methode_1 (long x, long y)
{
long pgcd;
if (x < y)
{
permuter (&x, &y);
}
if (y == 0)
{
pgcd = x;
}
else
{
pgcd = y;
while (x % pgcd != 0 || y % pgcd != 0)
{
pgcd--;
}
}
return pgcd;
}
/* --------------------------------------------------------------------------
trouver_pgcd_methode_2 ()
--------------------------------------------------------------------------
Role : retourne le PGCD de 2 nombre par la formule mathematique
-------------------------------------------------------------------------- */
long trouver_pgcd_methode_2 (long x, long y)
{
long tmp;
if (x < y)
{
permuter (&x, &y);
}
while (y != 0)
{
tmp = x;
x = y;
y = tmp % x;
}
return x;
}
/* --------------------------------------------------------------------------
comparer_complexite_temporelle ()
--------------------------------------------------------------------------
Role : Comparer la complextité temporelle des 2 methodes
-------------------------------------------------------------------------- */
void comparer_complexite_temporelle (long x, long y)
{
clock_t temps_initial_methode;
clock_t temps_final_methode;
clock_t duree_methode_1;
clock_t duree_methode_2;
long pgcd1;
long pgcd2;
temps_initial_methode = clock ();
pgcd1 = trouver_pgcd_methode_1 (x, y - 1);
temps_final_methode = clock ();
duree_methode_1 = temps_final_methode - temps_initial_methode;
temps_initial_methode = clock ();
pgcd2 = trouver_pgcd_methode_2 (x, y - 1);
temps_final_methode = clock ();
duree_methode_2 = temps_final_methode - temps_initial_methode;
printf ("PGCD = %ld duree methode 1 : %10.0lf ns\n", pgcd1, (double) duree_methode_1 /
CLOCKS_PER_SEC * 1000000000.0);
printf ("PGCD = %ld duree methode 2 : %10.0lf ns\n", pgcd2, (double) duree_methode_2 /
CLOCKS_PER_SEC * 1000000000.0);
}
int main (int argc, char **argv)
{
comparer_complexite_temporelle (INT_MAX, INT_MAX - 1);
return EXIT_SUCCESS;
} |
Merci.
