Discussion :

[abd_bela]

Bonjour,

Je suis vraiment tres surpris par le résultat de la comparaison (temps d'execution ) entre une procédure itérative et récursive.
Alors que je pensais qu'une fonction récursive prend plus de temps à cause des appels successif de la fonction (sans parler des créations de variables locales à chaque appel!!)??? Le résultat est complètement l'inverse voici l'exemple :

// gcdIter.c

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(int nb, char *arg[]){
 long  long  a=atoll(arg[1]);
 long  long  b=atoll(arg[2]);
 long  long  x, y,m=a; 
  if ( b < m) m=b; 
  while ( m != 0 ){ 
    x= a % m;  y= b % m;
    if (x == 0 && y == 0 )    break;
    m--;
  }
  printf("gcd of %ld %ld: %ld\n",a,b,m); 
  return 0;  
}

//gcdRecur.c

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
long long  gcd(long long  m, long long  n) {
    if ((m % n) == 0)  return n;
    else  return gcd(n, m % n);
 }
int main(int nb, char *arg[]){
  long long  a=atoll(arg[1]);
  long long  b=atoll(arg[2]);
  long long  m; 
  m=gcd(a,b); 
  printf("gcd of %ld %ld: %ld\n",a,b,m); 
  return 0;  
}

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
tmp$ gcc -o gi gcdIter.c 
tmp$ gcc -o gr gcdRecur.c 
tmp$ time ./gi 516323818 19996479344                    ------->   itératif
gcd of 516323818 19996479344: 2
 
real	0m14,192s
user	0m14,140s
sys	0m0,048s
tmp$ time ./gr 516323818 19996479344               ----------------->  récursif
gcd of 516323818 19996479344: 2
 
real	0m0,003s
user	0m0,000s
sys	0m0,003s

Bonne journée

[Sve@r]

Bonjour

Ce n'est pas évident de faire des tests de benchmark. Parce que linux peut avoir gardé en mémoire des traces des dernières actions (donc pas de swap) etc. Je ne dis pas que c'est le cas ici mais c'est un point à prendre en compte.
Par exemple moi pour faire ce test, j'aurais programmé deux shells qui attendent tous deux la présence d'un fichier X pour lancer le calcul, les aurais lancés tous deux en parallèle depuis deux fenêtres xterm puis créé le fichier depuis une 3°. Ainsi les calculs se seraient déroulés en même temps.

Autre chose: en récursivité il faut distinguer deux cas:

• la récursivité avec retour de calcul (exemple factorielle, fibonacci, pgcd)
• la récursivité qui se termine au dernier appel (appelée aussi "récursivité terminale"). Exemple affichage d'une chaine à l'envers (ou même à l'endroit), affichage d'un nombre X en base "b" (divisions successives), bref en fait toute fonction récursive appelée sans attendre son résultat (donc interdit d'écrire ...=fonction_recursive()). Là encore ce n'est pas le cas ici mais ça peut l'être ailleurs (donc j'en parle pour tes tests futurs)

Autre chose encore: quand on fait des tests, on essaye de rendre les codes testés le plus semblable possible (la seule différence portera par exemple sur la fonction de calcul). Ici tu as un algorithme itératif qui se déroule dans le main tandis que le récursif se déroule dans une fonction à part. Normalement tu aurais dû programmer deux gcd(), le premier itératif et le second résursif, tous deux lancés depuis leur main respectif. Alors ok l'itératif dans une fonction dédiée sera encore plus long que dans le main puisqu'on rajoutera le temps d'empilement/dépilement de la fonction mais là c'est pour l'impartialité des tests.

Maintenant (et là c'est le plus important), quand on compare un algorithme récursif vs algorithme itératif, on a au moins la décence de programmer le même algorithme !!!
La fonction récursive utilise l'algorithme d'Euclide (divisions successives) qui va aller très vite (si je pars par exemple de 1331 et 121, j'obtiens "11" en une opération. L'algorithme récursif, lui, utilise une méthode qui semble fonctionner mais à base de soustractions de b (ce m=b au début suivi de m-- que je ne m'explique pas). Et pour corser le tout, cet algorithme possède deux tests (le while (m !=0) suivi de if (x == 0 && y == 0 ) bien bien lourd avec son "and") !!!

Regarde ton algorithme tel que je l'ai réécrit avec un compteur d'affichage des opérations

Code c :

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
#include <stdio.h>
#include <stdlib.h>
 
long long gcd(long long a, long long b) {
	long long cpt=0;
	long long x, y,m=a;
	if ( b < m) m=b;
	while ( m != 0 ){
		cpt++;
		printf("cpt=%ld, a=%ld, b=%ld, m=%ld\n", cpt, a, b, m);
		x= a % m; y= b % m;
		if (x == 0 && y == 0 ) break;
		m--;
	}
	return m;
}
 
int main(int nb, char *arg[]){
	long long a=atoll(arg[1]);
	long long b=atoll(arg[2]);
	printf("gcd of %ld %ld: %ld\n",a,b,gcd(a, b));
	return 0; 
}

Et regarde le vrai algorithme d'Euclide (là aussi avec un compteur)

Code c :

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
#include <stdio.h>
#include <stdlib.h>
 
long long gcd(long long a, long long b) {
	long long m=a;
	long long cpt=0;
	while (b > 0) {
		cpt++;
		printf("cpt=%ld, a=%ld, b=%ld, m=%ld\n", cpt, a, b, m);
		m=a%b;
		a=b;
		b=m;
	}
	return a;
}
 
int main(int nb, char *arg[]){
	long long a=atoll(arg[1]);
	long long b=atoll(arg[2]);
	printf("gcd of %ld %ld: %ld\n",a,b,gcd(a, b));
	return 0; 
}

Et le rajout du compteur dans le récursif (que j'optimise encore un peu en supprimant le "else" inutile)...

Code c :

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
#include <stdio.h>
#include <stdlib.h>
 
long long gcd(long long m, long long n) {
	static long long cpt=0;
	cpt++;
	printf("cpt=%ld, a=%ld, b=%ld\n", cpt, m, n);
	if ((m % n) == 0) return n;
	return gcd(n, m % n);
}
 
int main(int nb, char *arg[]){
	long long a=atoll(arg[1]);
	long long b=atoll(arg[2]);
	printf("gcd of %ld %ld: %ld\n",a,b,gcd(a, b));
	return 0; 
}

Essaye-les avec par exemple 129236107 113365263 (le premier est 11 * 11 * 97 * 91 et le second est 11 * 11 * 89 * 87 et tu verras la différence dans le compteur de ton itératif par rapport au récursif ou de mon itératif. Ensuite supprime ce compteur et recommence tes tests. Et si tu veux bien charger le truc, il te faut alors choisir deux nombres consécutifs de la suite de Fibonacci comme par exemple le 49° et 50° qui sont 20365011074 et 32951280099 et qui produiront alors 51 itérations (et 20365011074 itérations avec ta version !!!)

[droggo]

Bonjour,

+1

Il est en effet très délicat de prendre le résultat de ce genre de test comme absolu

[Sve@r]

Ca y est, j'ai compris le premier algo itératif: c'est un algo brute force. On part de a et b et m égal au plus petit des deux et on tente de diviser a par m et b par m. Si ça marche ok sinon on décrémente m. Fatalement on finira par trouver un diviseur et ce sera le plus grand commun aux deux ; mais c'est l'algo le plus pourri qui puisse se programmer pour ce genre de calcul.
Mais qu'importe, puisque tu veux tester l'itératif et le récursif, voici les deux codes de cet algo
Itératif

Code c :

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
#include <stdio.h>
#include <stdlib.h>
 
long long gcd(long long a, long long b) {
	long long cpt=0;
	long long m=a < b ?a :b;
	while (1) {
		cpt++;
		printf("cpt=%ld, a=%ld, b=%ld, m=%ld\n", cpt, a, b, m);
		if (a%m == 0 && b%m == 0 ) return m;
		m--;
	}
}
 
int main(int nb, char *arg[]){
	long long a=atoll(arg[1]);
	long long b=atoll(arg[2]);
	printf("gcd of %ld %ld: %ld\n",a,b,gcd(a, b));
	return 0; 
}

Et le récursif

Code c :

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
#include <stdio.h>
#include <stdlib.h>
 
long long gcd(long long a, long long b, long long m) {
	static long long cpt=0;
	cpt++;
	printf("cpt=%ld, a=%ld, b=%ld, m=%ld\n", cpt, a, b, m);
	if (a%m == 0 && b%m == 0 ) return m;
	return gcd(a, b, m-1);
}
 
int main(int nb, char *arg[]){
	long long a=atoll(arg[1]);
	long long b=atoll(arg[2]);
	printf("gcd of %ld %ld: %ld\n",a,b,gcd(a, b, a < b? a :b));
	return 0; 
}

Le programme qui va les lancer (à appeler depuis deux fenêtres distinctes puis taper touch /tmp/x depuis une 3° pour qu'ils partent en même temps)

Code bash :

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

1
2
3
4
5
6
#!/bin/bash
until test -f "/tmp/x"; do
	true
done
echo "start $1"
time "./$1" "$2" "$3"

Et le résultat avec 97097 et 99500 (on peut pas aller beaucoup plus haut car la récursivité explose la pile)

Récursif
gcd of 97097 99500: 1
real 0m0,892s
user 0m0,043s
sys 0m0,136s

Itératif
gcd of 97097 99500: 1
real 0m0,805s
user 0m0,032s
sys 0m0,131s

[Bktero]

Et surtout : les deux programmes font un calcul (qui sera sans doute rapide) et un printf (qui sera sans doute lent). En gros, on mesure sans doute le temps des printf() et non le temps des calculs.

[Sve@r]

J'y ai pensé aussi. Mais quand on l'enlève, les deux programmes sont (malgré leur algo) trop rapides (0.003s pour le récursif et 0.002s pour l'itératif). Même si l'itératif reste plus rapide, les écarts ne sont plus assez significatifs pour pouvoir en discuter.
Et si j'augmente les nombres à chercher, le récursif (qui fera autant d'appels que la valeur du plus petit des deux nombres) explose en vol.

Je me suis donc dit que puisque les printf sont tous deux présents au même endroit, cela chargeait les deux programmes de façon égale ce qui annulait cette charge au résultat (la différence de temps étant donc due à la différence récursif/itératif et non due aux printf)...