temps d'execution - clock ()

**exhortae** · 21/11/2007, 16h53

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 :

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
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.

**acx01b** · 21/11/2007, 17h22

salut

si tu es sous windows utilise plutôt les fonctions de windows

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
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
113
114
115
/* --------------------------------------------------------------------------
   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>
 #include <windows.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 (18000000000, 22000000);
   temps_final_methode = clock ();
   duree_methode_1 = temps_final_methode - temps_initial_methode;
 
    LARGE_INTEGER a,b,c;
 
 
 QueryPerformanceFrequency(&c);
   QueryPerformanceCounter(&a);
   pgcd2 = trouver_pgcd_methode_2 (18000000000, 22000000);
   QueryPerformanceCounter(&b);
   duree_methode_2 =  b.QuadPart - a.QuadPart;
 
   printf ("PGCD = %ld duree methode 1 : %f ns\n", pgcd1, (double) duree_methode_1 / CLOCKS_PER_SEC * 1000000.0);
   printf ("PGCD = %ld duree methode 2 : %f ns\n", pgcd2, (double) duree_methode_2 / c.QuadPart * 1000000.0);
}
 
int main (int argc, char **argv)
{
   comparer_complexite_temporelle (INT_MAX, INT_MAX - 1);
 
   return EXIT_SUCCESS;
}

sinon sous linux il existe la structure tms et les fonctions qui vont avec:
http://www.opengroup.org/onlinepubs/...ons/times.html

**diogene** · 21/11/2007, 17h40

- la deuxième méthode est tellement rapide que clock arrive pas à calculer son temps d'éxecution.

Oui, l'algorithme d'Euclide de la seconde méthode est beaucoup plus efficace

- Il y a un souci au niveau du code.

Non, je ne pense pas

**exhortae** · 21/11/2007, 23h06

Envoyé par acx01b

salut

si tu es sous windows utilise plutôt les fonctions de windows

sinon sous linux il existe la structure tms et les fonctions qui vont avec:
http://www.opengroup.org/onlinepubs/...ons/times.html

Bonsoir,

Alors oui je suis sous windows mais j'aurais voulu autant que faire se peut utiliser une fonction qui soit POSIX. J'ai essayé avec QueryPerformanceCounter () ça marche effectivement bien, le seul souci c'est le windows.h :/

Sinon au niveau de times () si je comprends bien la librairie sys/times.h est spécifique à linux.

Va falloir que je demande au prof celle que je peux utiliser.

Merci

Envoyé par diogene

Oui, l'algorithme d'Euclide de la seconde méthode est beaucoup plus efficace
Non, je ne pense pas

C'est bien ce que je me disais, merci

A votre avis la fonction gettime de dos.h peut elle être utilisable pour ce genre de travail (même si elle est pas POSIX) et qu'elle ne donne que les centièmes de secondes au plus précis.

Merci

**exhortae** · 21/11/2007, 23h43

Bon au final je vais utiliser l'api windows

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
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
113
114
115
116
117
118
119
120
121
122
123
124
/* --------------------------------------------------------------------------
   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>
 #include <windows.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
          On utilise le timer cpu haute resolution <window.h>
   -------------------------------------------------------------------------- */
void comparer_complexite_temporelle (long x, long y)
{
   LARGE_INTEGER start_ticks;
   LARGE_INTEGER stop_ticks;
   LARGE_INTEGER counts_per_sec;
   long duree_methode_1;
   long duree_methode_2;
   long pgcd1;
   long pgcd2;
 
   /* Frequence a laquelle le compteur est mis a jour */
   QueryPerformanceFrequency(&counts_per_sec);
 
   /* Valeur du compteur au debut */
   QueryPerformanceCounter(&start_ticks);
 
   pgcd1 = trouver_pgcd_methode_1 (x, y);
 
   /* Valeur du compteur a la fin */
   QueryPerformanceCounter(&stop_ticks);
 
   /* Temps d'execution */
   duree_methode_1 =  stop_ticks.QuadPart - start_ticks.QuadPart;
 
   QueryPerformanceCounter(&start_ticks);
   pgcd2 = trouver_pgcd_methode_2 (x, y);
   QueryPerformanceCounter(&stop_ticks);
   duree_methode_2 =  stop_ticks.QuadPart - start_ticks.QuadPart;
 
   printf ("PGCD = %ld | duree methode 1 : %7.2lf micro-secondes\n", pgcd1,
          (double) duree_methode_1 / counts_per_sec.QuadPart * 1000000.0);
   printf ("PGCD = %ld | duree methode 2 : %11.2lf micro-secondes\n", pgcd2,
          (double) duree_methode_2 / counts_per_sec.QuadPart * 1000000.0);
}
 
int main (int argc, char **argv)
{
   comparer_complexite_temporelle (INT_MAX, INT_MAX - 1);
 
   return EXIT_SUCCESS;
}

Par contre je comprends pas le .QuadPart

**Médinoc** · 22/11/2007, 10h11

LARGE_INTERGER est une union, pas un long long.
QuadPart est le champ de type long long de cette union.

**acx01b** · 22/11/2007, 11h09

salut

si tu veux être portable je pense que ceci suffit:

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
void start_chrono();
unsigned long get_elapsed_time(); // en ns ?
 
void start_chrono() {
#ifdef WIN32
...
code windows
#else
...
code linux / mac / unix
#endif
}
 
unsigned long get_elapsed_time() {
#ifdef WIN32
...
code windows
#else
...
code linux / mac / unix
#endif
}

**exhortae** · 22/11/2007, 20h34

Envoyé par Médinoc

LARGE_INTERGER est une union, pas un long long.
QuadPart est le champ de type long long de cette union.

Merci, j'ai un bouquin de C qui parle des unions, je vais y jeter un coup d'oeil.

**DaZumba** · 22/11/2007, 11h33

Envoyé par exhortae

Alors oui je suis sous windows mais j'aurais voulu autant que faire se peut utiliser une fonction qui soit POSIX.

Quand on compare deux algorithmes au niveau de leur rapidite, on ne fait pas qu'un seul appel. Il faut faire les mesures sur un grand nombre d'appels (si possible avec des donnees variables) et faire une moyenne (on peut meme avoir un ecart-type). La resolution temporelle de clock() n'est alors plus un probleme.

**exhortae** · 22/11/2007, 20h44

Envoyé par DaZumba

Quand on compare deux algorithmes au niveau de leur rapidite, on ne fait pas qu'un seul appel. Il faut faire les mesures sur un grand nombre d'appels (si possible avec des donnees variables) et faire une moyenne (on peut meme avoir un ecart-type). La resolution temporelle de clock() n'est alors plus un probleme.

J'ai pas bien compris ce que tu veux dire.

1) Faire une boucle, à l'intérieur de cette boucle appeler chaque fois la fonction et noter la durée du temps d'exécution dans un tableau, puis faire la moyenne à partir de ce tableau.

Code :

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

1
2
3
4
5
6
7
8
9
10
 
for (i = ...)
{
start = clock ()
fonction_calcul_pgcd ()
end = clock
t[i] = end - start
}
 
...

On va se retrouver avec le problème d'avant où la durée sera tellement brève à chaque appel que la durée moyennesera = 0.

2) sauvegarder le temps de départ, faire une boucle avec appel à la fonction puis sauvegader le temps à la sortie de la boucle, faire la différence des temps.

Code :

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

1
2
3
4
5
6
7
8
9
 
start = clock
for (i = ...)
{
fonction_calcul_pgcd
}
end = clock
 
duree = end - start

Cette méthode ne serait applicable qu'a la deuxième méthode (algorithme d'euclide), parceque pour la première méthode 1 seul appel prends déjà 30 seconde sur mon PC avec (INT_MAX, INT_MAX - 1).

**DaZumba** · 22/11/2007, 21h18

Envoyé par exhortae

J'ai pas bien compris ce que tu veux dire.

C'est ton point 2 qui est exact. Il est adapté à des mesures de durées courtes.

2) sauvegarder le temps de départ, faire une boucle avec appel à la fonction puis sauvegader le temps à la sortie de la boucle, faire la différence des temps.

Code :

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

1
2
3
4
5
6
7
8
9
 
start = clock
for (i = ...)
{
fonction_calcul_pgcd
}
end = clock
 
duree = end - start

Attention, la durée d'un seul appel est (end - start) / ( (double) n_appel) où n_appel est le nombre d'itérations. Puisque la première fonction est lente, tu peux te contenter d'un seul appel, mais pour la deuxième, il faudra en faire beaucoup plus.

temps d'execution - clock ()

C

Vue hybride

Discussions similaires

Partager

Partager