Algorithmique & Programmation Orientée Objet Semestre 2 ST Précision, rapidité & complexité
Cours | TD | TP - Corrections
Clavier.class - Ecran.class - Documentation
Exercice 1 On donne le programme Java suivant:
NombreFibonacci.java /* Calcul du nombre de Fibonacci */ /* au moyen d'une fonction récursive */ public class NombreFibonacci { /* Fonction de calcul et retour */ /* de Fib(n) par methode recursive */ /* Définition: */ /* - Fib(0) = 0 */ /* - Fib(1) = 1 */ /* - Fib(n) = Fib(n-1)+Fib(n-2) */ /* n : valeur pour laquelle Fib(n) est calculé */ static long fib(int n) { long res; switch (n) { case 0 : case 1 : { res = n; } break; default : { res = fib(n-1)+fib(n-2); } break; } return res; } /* Programme principal */ public static void main(String [] args) { int n; long fibn; Ecran.afficher("n? "); n = Clavier.saisirInt(); Ecran.afficherln("Début du calcul de fib(",n,")"); fibn = fib(n); Ecran.afficherln("Fin du calcul de fib(",n,")"); Ecran.afficherln("fib(",n,") = ",fibn); } } Clavier.class - Ecran.class - Exemple d'exécution
Ce programme permet le calcul de fib(n) par utilisation d'une fonction développée ad hoc. Cette fonction est implantée en utilisant la récursivité. Modifier le programme précédent pour mesurer et afficher le temps d'exécution de la fonction fib(n) pour les valeurs de n allant de 0 à 50. On utilisera la fonction System.nanoTime() pour les prises de temps. On pourra réaliser l'affichage sur 3 colonnes: - valeur de n - temps de calcul - valeur de fib(n) Que constate-t-on? Analyser le code de la fonction fib(n) pour déterminer la formule mathématique f(n) qui devrait donner le temps d'exécution du calcul de fib(n) en fonction de n? Si la formule f(n) est bonne, le rapport temps de fib(n)/f(n) devrait être constant. Modifier votre programme pour ajouter une colonne supplémentaire permettant d'afficher temps de fib(n)/f(n) pour chaque valeur de n et relancer une exécution. Y a-t-il correspondance entre le postulat théorique et le résultat expérimental? Solution L'analyse du code de la fonction nous conduit à émettre l'hypothèse que la fonction ordre de temps de fib(n) devrait être une fonction de Fibonacci. En effet, calculer fib(n) demande le calcul de fib(n-1) et le calcul de fib(n-2) -> le temps de calcul de fib(n) devrait être "égal" au temps de calcul de fib(n-1) + le temps de calcul de fib(n-2) -> une fonction de Fibonacci.
NombreFibonacciAvecMesureDeTemps.java /* Calcul du nombre de Fibonacci */ /* au moyen d'une fonction récursive */ /* Mesure du temps d'exécution */ public class NombreFibonacciAvecMesureDeTemps { /* Fonction de calcul et retour */ /* de Fib(n) par methode recursive */ /* Définition: */ /* - Fib(0) = 0 */ /* - Fib(1) = 1 */ /* - Fib(n) = Fib(n-1)+Fib(n-2) */ /* n : valeur pour laquelle Fib(n) est calculé */ static long fib(int n) { long res; switch (n) { case 0 : case 1 : { res = n; } break; default : { res = fib(n-1)+fib(n-2); } break; } return res; } /* Programme principal */ public static void main(String [] args) { for ( int n = 0 ; n <= 50 ; n = n+1 ) { Ecran.formater("%5d : ",n); long ti = System.nanoTime(); long fibn = fib(n); long tf = System.nanoTime(); Ecran.formater("%15d %15d %8.2f\n",tf-ti,fibn,(double) (tf-ti)/fibn); } } } Clavier.class - Ecran.class - Exemple d'exécution
Temps obtenus
0 : 2858 0 Infinity 1 : 714 1 714.00 2 : 1429 1 1429.00 3 : 1429 2 714.50 4 : 714 3 238.00 5 : 714 5 142.80 6 : 1428 8 178.50 7 : 2144 13 164.92 8 : 2858 21 136.10 9 : 5001 34 147.09 10 : 7145 55 129.91 11 : 11431 89 128.44 12 : 19289 144 133.95 13 : 30720 233 131.85 14 : 48580 377 128.86 15 : 77871 610 127.66 16 : 125022 987 126.67 17 : 197893 1597 123.92 18 : 313628 2584 121.37 19 : 509378 4181 121.83 20 : 820864 6765 121.34 21 : 1320954 10946 120.68 22 : 2334710 17711 131.82 23 : 3710673 28657 129.49 24 : 5851062 46368 126.19 25 : 10433322 75025 139.06 26 : 14904847 121393 122.78 27 : 23842897 196418 121.39 28 : 38848477 317811 122.24 29 : 65048945 514229 126.50 30 : 107345190 832040 129.01 31 : 166533071 1346269 123.70 32 : 268472280 2178309 123.25 33 : 497475970 3524578 141.14 34 : 723064756 5702887 126.79 35 : 1183033208 9227465 128.21 36 : 1943681211 14930352 130.18 37 : 3106749367 24157817 128.60 38 : 4975953494 39088169 127.30 39 : 7957813775 63245986 125.82 40 : 12764771609 102334155 124.74 41 : 21042182654 165580141 127.08 42 : 33684262002 267914296 125.73 43 : 53778489812 433494437 124.06 44 : 86931211091 701408733 123.94 45 : 141607285179 1134903170 124.77 46 : 229525371031 1836311903 124.99 47 : 368980460741 2971215073 124.19 48 : 597549626146 4807526976 124.29 49 : 972168176940 7778742049 124.98 50 : 1567636699086 12586269025 124.55
On constate que la colonne 4 qui contient le rapport temps expérimental/f(n) contient des valeurs relativement constantes pour les grandes valeurs de n. Ce fait appuie l'hypothèse de véracité de la fonction d'ordre de temps déterminée par analyse du code: une fonction de Fibonacci. Pour les petites valeurs de n, la qualité de la mesure de temps (précision) n'est pas suffisante pour que les résultats soient exploitables. Exercice 2 Le programme ci-dessous réalise les opération suivantes: - Création d'une matrice de n*n réels affectée à la variable m1 - Création d'une matrice de n*n réels affectée à la variable m2 - Création d'une matrice de n*n réels affectée à la variable m - Initialisation de la matrice m1 avec des valeurs tirées au sort entre 0.0 et 1.0 - Initialisation de la matrice m2 avec des valeurs tirées au sort entre 0.0 et 1.0 - Multiplication de m1 par m2 avec report du résultat dans la matrice m
ProduitMatricesCarrees.java /* Produits de deux matrices carrees de reels */ /* de taille n x n */ public class ProduitMatricesCarrees { /* Fonction de creation et retour d'une matrice */ /* carree de double */ /* taille : la taille de la matrice a generer */ static double [][] nouvelleMatrice(int taille) { double [][] t = new double[taille][taille]; return t; } /* Fonction d'initialisation d'une matrice */ /* carree de double avec des nombres aleatoires */ /* compris dans l'intervalle [0.0,1.0] */ /* tab : la matrice carree a initialiser */ static void initRandMatrice(double [][] tab) { int n = tab.length; for ( int i = 0 ; i < n ; i++ ) { for ( int j = 0 ; j < n ; j++ ) { tab[i][j] = Math.random(); } } } /* Fonction de calcul de la matrice de reels */ /* de taille n x n obtenue par produit */ /* d'une matrice de reels de taille n x n */ /* par une matrice de reels de taille n x n */ /* m1 : la premiere matrice de reels */ /* m2 : la seconde matrice de reels */ /* m : la matrice de reels obtenue par produit */ static void produit(double [][] m1, double [][] m2, double [][] m) { int n = m1.length; double [][] m2t = nouvelleMatrice(n); for ( int i = 0 ; i < n ; i++ ) { for ( int j = 0 ; j < n ; j++ ) { m2t[j][i] = m2[i][j]; } } double [][] tmp = nouvelleMatrice(n); for ( int i = 0 ; i < n ; i++ ) { for ( int j = 0 ; j < n ; j++ ) { tmp[i][j] = 0.0; for ( int k = 0 ; k < n ; k++ ) { tmp[i][j] = tmp[i][j] + m1[i][k]*m2t[j][k]; } } } for ( int i = 0 ; i < n ; i++ ) { for ( int j = 0 ; j < n ; j++ ) { m[i][j] = tmp[i][j]; } } } /* Programme principal */ public static void main(String [] args) { int n; double [][] m1; double [][] m2; double [][] m; Ecran.afficher("n? "); n = Clavier.saisirInt(); m1 = nouvelleMatrice(n); m2 = nouvelleMatrice(n); m = nouvelleMatrice(n); Ecran.afficherln("Génération de m1"); initRandMatrice(m1); Ecran.afficherln("Génération de m2"); initRandMatrice(m2); Ecran.afficherln("Début du calcul du produit de m1 par m2"); produit(m1,m2,m); Ecran.afficherln("Fin du calcul du produit de m1 par m2"); } } Clavier.class - Ecran.class - Exemple d'exécution
Modifier le porgramme précédent de façon à mesurer et afficher les temps d'exécutions des deux appels à la fonction initRandMatrice et de l'appel à la fonction produitMatricesCarrees pour les valeurs n allant de 100 à 2000 par pas de 100. Comme à l'exercice 1, on utilisera la fonction System.nanoTime() pour les prises de temps. On pourra réaliser l'affichage sur 4 colonnes: - valeur de n - temps d'initialisation de m1 - temps d'initialisation de m2 - temps de calcul du produit de m1 par m2 Que constate-t-on? Analyser le code des fonctions initRandMatrice(...) et produitMatricesCarrees(...) pour déterminer les formules mathématiques f(n) qui devraient donner leurs temps d'exécution en fonction de la taille n des matrices manipulées? Si les formules f(n) sont bonnes, les rapports temps de fonction(n)/f(n) devraient être constants pour les deux fonctions. Modifier votre programme pour ajouter trois colonnes supplémentaires permettant d'afficher temps de fonction(n)/f(n) pour chaque valeur de n et relancer une exécution Y a-t-il correspondance entre les postulats théoriques et les résultats expérimentaux? Solution La fonction d'initialisation d'une matrice est basée sur une boucle for dont la séquence de code est exécutée n fois. Cette séquence de code contient elle-même un for dont la séquence de code est exécutée n fois -> cette séquence est, au total, exécutée n x n = n2 fois. La fonction de produit matriciel contient 3 parties exécutées successivement. La première est constituée de deux for imbriqués qui conduisent à l'exécution de la séquence la plus interne n x n = n2 fois. La deuxième est constituée de trois for imbriqués qui conduisent à l'exécution de la séquence la plus interne n x n x n = n3 fois. La troisième est constituée de deux for imbriqués qui conduisent à l'exécution de la séquence la plus interne n x n = n2 fois. Le temps total est donc de l'ordre de n2+n3+n2 = 2n2+n3 qui est ramené en n3 par élimination du terme mineur 2n2.
ProduitMatricesCarreesAvecMesureDeTemps.java /* Produits de deux matrices de reels carrees */ /* de taille n x n */ /* Mesure du temps d'exécution */ public class ProduitMatricesCarreesAvecMesureDeTemps { /* Fonction de creation et retour d'une matrice */ /* de double carree */ /* taille : la taille de la matrice a generer */ static double [][] nouvelleMatrice(int taille) { double [][] t = new double[taille][taille]; return t; } /* Fonction d'initialisation d'une matrice */ /* de double carree avec des nombres aleatoires */ /* compris dans l'intervalle [0.0,1.0] */ /* tab : la matrice carree a initialiser */ static void initRandMatrice(double [][] tab) { int n = tab.length; for ( int i = 0 ; i < n ; i++ ) { for ( int j = 0 ; j < n ; j++ ) { tab[i][j] = Math.random(); } } } /* Fonction de calcul du tableau */ /* de reels de dimension 2 de taille n x n */ /* obtenu par produit d'un tableau de reels */ /* de dimension 2 de taille n x n */ /* par un tableau de reels de dimension 2 */ /* de taille n x n */ /* m1 : le premier tableau de reels */ /* m2 : le second tableau de reels */ /* m : le tableau obtenu par produit */ static void produit(double [][] m1, double [][] m2, double [][] m) { int n = m1.length; double [][] m2t = nouvelleMatrice(n); for ( int i = 0 ; i < n ; i++ ) { for ( int j = 0 ; j < n ; j++ ) { m2t[j][i] = m2[i][j]; } } double [][] tmp = nouvelleMatrice(n); for ( int i = 0 ; i < n ; i++ ) { for ( int j = 0 ; j < n ; j++ ) { tmp[i][j] = 0.0; for ( int k = 0 ; k < n ; k++ ) { tmp[i][j] = tmp[i][j] + m1[i][k]*m2t[j][k]; } } } for ( int i = 0 ; i < n ; i++ ) { for ( int j = 0 ; j < n ; j++ ) { m[i][j] = tmp[i][j]; } } } /* Programme principal */ public static void main(String [] args) { double [][] m1; double [][] m2; double [][] m; int n; for ( n = 100 ; n <= 2000 ; n = n+100 ) { Ecran.formater("%5d : ",n); m1 = nouvelleMatrice(n); m2 = nouvelleMatrice(n); m = nouvelleMatrice(n); long t1i = System.nanoTime(); initRandMatrice(m1); long t1f = System.nanoTime(); Ecran.formater("%15d %8.2f",t1f-t1i,(t1f-t1i)/((double) n*n)); long t2i = System.nanoTime(); initRandMatrice(m2); long t2f = System.nanoTime(); Ecran.formater("%15d %8.2f",t2f-t2i,(t2f-t2i)/((double) n*n)); long ti = System.nanoTime(); produit(m1,m2,m); long tf = System.nanoTime(); Ecran.formater("%15d %8.2f\n",tf-ti,(tf-ti)/((double) n*n*n)); } } } Clavier.class - Ecran.class - Exemple d'exécution
Temps obtenus
100 : 22597671 2259.77 6910540 691.05 43538613 43.54 200 : 27967217 699.18 27818619 695.47 345037599 43.13 300 : 62464190 694.05 64093057 712.15 1142755900 42.32 400 : 117509891 734.44 114443621 715.27 2792527358 43.63 500 : 181933722 727.73 184326299 737.31 5401207076 43.21 600 : 261399568 726.11 253941073 705.39 9463987752 43.81 700 : 343935972 701.91 354790084 724.06 14871290934 43.36 800 : 459362627 717.75 460337089 719.28 22098342128 43.16 900 : 585034713 722.27 584048106 721.05 31449854474 43.14 1000 : 720767910 720.77 711101871 711.10 43054377722 43.05 1100 : 864224652 714.24 907947584 750.37 57106373585 42.90 1200 : 1026422650 712.79 1056440954 733.64 74345270499 43.02 1300 : 1241807442 734.80 1208582842 715.14 94878381506 43.19 1400 : 1402765930 715.70 1408404811 718.57 118073572634 43.03 1500 : 1626872304 723.05 1612730452 716.77 145034060466 42.97 1600 : 1851569499 723.27 1833312615 716.14 176199270440 43.02 1700 : 2071319368 716.72 2073379742 717.43 210549591140 42.86 1800 : 2351749532 725.85 2300067298 709.90 247645587842 42.46 1900 : 2588730384 717.10 2580641773 714.86 295139413151 43.03 2000 : 2865814226 716.45 2862029254 715.51 344615848875 43.08
On constate que les colonnes 3, 5 et 7 qui contiennent les rapports temps expérimentaux/f(n) contiennent des valeurs relativement constantes. Ce fait appuie l'hypothèse de véracité des fonctions d'ordre de temps déterminées par analyse du code: temps quadratique pour la fonction initialisation, cubique pour la fonction produit matriciel. Partie supplémentaire: Mesurer des temps courts avec "précision" Mesurer des temps d'exécution très courts se heurte au problème que même la fonction System.nanoTime() peut ne pas être assez précise pour cela. Sur la machine utilisée pour la préparation de ce TP, les temps fournis par System.nanoTime() sont précis à environ 715 ns. Cette durée est très longue pour un ordinateur moderne. Une solution pour palier ce problème pourra être de lancer plus d'une fois (voire un grand nombre de fois) l'algorithme dont on souhaite tester la rapidité de façon à calculer le temps global d'exécution puis à diviser le temps ainsi obtenu par le nombre d'exécutions. Le temps moyen ainsi obtenu devrait être représentatif de la valeur qui serait obtenue pour une seule exécution. Le programme suivant illustre l'utilisation de la librairie Utilitaires.class (documentation) qui permet de créer et utiliser un "Minuteur". Il est ainsi possible de déclarer une variable de type Minuteur, de lui affecter un temps de fonctionnement (compté en milli-secondes), puis de la "déclancher". Cette variable possède un champ booléen nommé enCours qui aura la valeur vrai pour la durée de fonctionnement définie et qui passera automatiquement à faux sitôt cette durée terminée. Il est ainsi possible de construire une boucle while dont la condition de continuation est basée sur la valeur de ce champ, permettant ainsi de programmer l'exécution de cette boucle pour une durée minimum égale au temps du Minuteur. Exemple à utiliser et adapter aux tests demandés
ExempleUtilisationMinuteur.java /* Exemple d'utilisation de l'utilitaire Minuteur */ public class ExempleUtilisationMinuteur { /* Calcul de la somme des valeurs de 1/i */ /* pour i de 1 à n */ static void executerCalcul() { double somme = 0.0; for ( int i = 1 ; i < 10 ; i++ ) { somme = somme + 1.0/i; } } /* Fonction principale */ public static void main(String [] args) { /* Declaration du Minuteur minuteur */ Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur(); /* Configuration du temps de commutation */ /* de minuteur (en milliemes de seconde) */ minuteur.temps = 1000; /* Lancement de minuteur */ minuteur.lancement(); /* Initialisation du compteur d'execution */ long cpt = 0; /* Prise de temps initiale */ long ti = System.nanoTime(); /* Utilisation de minuteur par construction */ /* d'une boucle tant que dont la condition */ /* d'arrêt porte sur la valeur */ /* de son champ booléen enCours */ while ( minuteur.enCours == true ) { executerCalcul(); cpt++; } /* Prise de temps finale */ long tf = System.nanoTime(); /* Affichage des resultats */ Ecran.afficherln(cpt," executions en ",tf-ti," ns"); Ecran.afficherln("Temps moyen : ",(double) (tf-ti)/cpt," ns"); } } Clavier.class - Ecran.class - Exemple d'exécution
Au moyen de ce composant utilitaire, en adaptant le programme ci-dessus, on pourra développer des programmes permettant de faire exécuter tel ou tel sous-algorithme pendant un temps tf-ti en comptant le nombre d'exécutions cpt. En divisant (tf-ti) pat cpt on obtient le temps d'exécution moyen d'un appel au sous-algorithme. On pourra confronter les ordres de temps déterminés théoriquement aux temps constatés expérimentalement pour vérifier leurs validités en calculant les temps moyens pour différentes tailles et en voyant si ces temps suivent les lois théoriques en fonction de la taille. ATTENTION! On veillera à essayer de mesurer le temps d'exécution de la fonction ciblée à l'exclusion de tout autre temps. Dans la pratique, les temps de gestion de la boucle et des incréments sur cpt sont comptés alors qu'ils devraient ne pas l'être. Question: Comment les décompter? Exercice 0 Télécharger les fichiers Utilitaires.class et Utilitaires$Minuteur.class et les installer dans le répertoire de sauvegarde de vos fichiers .java. Télécharger, compiler et exécuter le code source ci-dessus pour vérifier le bon fonctionnement d'un Minuteur. Exercice 1 Adapter le programme de l'exercice 0 pour vérifier sur des petites valeurs de n l'hypothèse posée sur l'ordre de temps du calcul récursif de fib(n). Solution
FibonacciAvecMinuteur.java /* Exemple d'utilisation de l'utilitaire Minuteur */ public class FibonacciAvecMinuteur { /* Fonction de calcul et retour */ /* de Fib(n) par methode recursive */ /* Définition: */ /* - Fib(0) = 0 */ /* - Fib(1) = 1 */ /* - Fib(n) = Fib(n-1)+Fib(n-2) */ /* n : valeur pour laquelle Fib(n) est calculé */ static long fib(int n) { long res; switch (n) { case 0 : case 1 : { res = n; } break; default : { res = fib(n-1)+fib(n-2); } break; } return res; } /* Fonction principale */ public static void main(String [] args) { for ( int n = 0 ; n <= 20 ; n++ ) { /* Declaration du Minuteur minuteur */ Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur(); /* Configuration du temps de commutation */ /* de minuteur (en milliemes de seconde) */ minuteur.temps = 60000; /* Lancement de minuteur */ minuteur.lancement(); /* Initialisation du compteur d'execution */ long cpt = 0; /* Prise de temps initiale */ long ti = System.nanoTime(); /* Utilisation de minuteur par construction */ /* d'une boucle tant que dont la condition */ /* d'arrêt porte sur la valeur */ /* de son champ booléen enCours */ while ( minuteur.enCours == true ) { fib(n); cpt++; } /* Prise de temps finale */ long tf = System.nanoTime(); /* Affichage des resultats */ Ecran.formater("%2d : ",n); Ecran.formater("%12d executions en %14d ns",cpt,tf-ti); Ecran.formater(", temps moyen : %16.3f ns\n",(double) (tf-ti)/cpt); } } }
Temps obtenus
0 : 1377311168 executions en 58421655786 ns, temps moyen : 42.417 ns 1 : 1405510838 executions en 58420634172 ns, temps moyen : 41.565 ns 2 : 453058063 executions en 58425402894 ns, temps moyen : 128.958 ns 3 : 272636486 executions en 58425370031 ns, temps moyen : 214.298 ns 4 : 158026652 executions en 58424492729 ns, temps moyen : 369.713 ns 5 : 97284064 executions en 58427466840 ns, temps moyen : 600.586 ns 6 : 59913239 executions en 58427843337 ns, temps moyen : 975.208 ns 7 : 36841733 executions en 58414300166 ns, temps moyen : 1585.547 ns 8 : 22497944 executions en 58424365563 ns, temps moyen : 2596.876 ns 9 : 13844619 executions en 58425446473 ns, temps moyen : 4220.083 ns 10 : 8605650 executions en 58414979575 ns, temps moyen : 6787.980 ns 11 : 5318996 executions en 58424473440 ns, temps moyen : 10984.117 ns 12 : 3275833 executions en 58414598077 ns, temps moyen : 17831.983 ns 13 : 2017572 executions en 58427424690 ns, temps moyen : 28959.276 ns 14 : 1253918 executions en 58427453267 ns, temps moyen : 46595.912 ns 15 : 771963 executions en 58427412545 ns, temps moyen : 75686.804 ns 16 : 479679 executions en 58427611152 ns, temps moyen : 121805.647 ns 17 : 295595 executions en 58428480596 ns, temps moyen : 197663.968 ns 18 : 182432 executions en 58427432549 ns, temps moyen : 320269.649 ns 19 : 112897 executions en 58415144604 ns, temps moyen : 517419.813 ns 20 : 69166 executions en 58414403756 ns, temps moyen : 844553.737 ns
Le respect d'une loi en fib(n) pour le temps de calcul de fib(n) est globalement validé. Exercice 2 Adapter le programme de l'exercice 0 pour comparer les temps d'exécution respectifs des versions itérative et récursive du calcul de factoriel (fonctions données ci-dessous).
FonctionsFactoriel.java /* Fonction de calcul et retour */ /* de n! par methode récursive */ /* Définition: */ /* - 0! = 1 */ /* - n! = (n-1)!*n si n > 0 */ /* n : valeur pour laquelle n! est calculé */ static long factorielRecursif(int n) { long res; if ( n == 0 ) { res = 1; } else { res = factorielRecursif(n-1)*n; } return res; } /* Fonction de calcul et retour */ /* de n! par methode itérative */ /* Définition: */ /* - 0! = 1 */ /* - n! = 1 * 2 * 3 * ... * n si n > 0 */ /* n : valeur pour laquelle n! est calculé */ static long factorielIteratif(int n) { long res = 1; if ( n > 1 ) { for ( int i = 2 ; i <= n ; i++ ) { res = res*i; } } return res; }
Solution
FonctionsFactorielAvecMinuteur.java /* Calcul de n! par methodes recursive */ /* et iteratives */ /* Mesures de temps */ public class FonctionsFactorielAvecMinuteur { /* Fonction de calcul et retour */ /* de n! par methode récursive */ /* Définition: */ /* - 0! = 1 */ /* - n! = (n-1)!*n si n > 0 */ /* n : valeur pour laquelle n! est calculé */ static long factorielRecursif(int n) { long res; if ( n == 0 ) { res = 1; } else { res = factorielRecursif(n-1)*n; } return res; } /* Fonction de calcul et retour */ /* de n! par methode itérative */ /* Définition: */ /* - 0! = 1 */ /* - n! = 1 * 2 * 3 * ... * n si n > 0 */ /* n : valeur pour laquelle n! est calculé */ static long factorielIteratif(int n) { long res = 1; if ( n > 1 ) { for ( int i = 2 ; i <= n ; i++ ) { res = res*i; } } return res; } /* Fonction principale */ public static void main(String [] args) { Ecran.afficherln(" Iteratif Recursif"); Ecran.afficherln(" n temps moyen temps moyen/n temps moyen temps moyen/n"); for ( int n = 100 ; n <= 10000 ; n += 100 ) { Ecran.formater("%3d :",n); { Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur(); minuteur.temps = 5000; minuteur.lancement(); long cpt = 0; long ti = System.nanoTime(); while ( minuteur.enCours == true ) { factorielIteratif(n); cpt++; } long tf = System.nanoTime(); tf -= cpt*15; Ecran.formater(" %8.3f ns",(double) (tf-ti)/cpt); Ecran.formater(" %11.3f",((double) (tf-ti)/cpt)/n); } { Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur(); minuteur.temps = 5000; minuteur.lancement(); long cpt = 0; long ti = System.nanoTime(); while ( minuteur.enCours == true ) { factorielRecursif(n); cpt++; } long tf = System.nanoTime(); tf -= cpt*15; Ecran.formater(" %12.3f ns",(double) (tf-ti)/cpt); Ecran.formater(" %11.3f",((double) (tf-ti)/cpt)/n); } Ecran.sautDeLigne(); } } }
Temps obtenus
Iteratif Recursif n temps moyen temps moyen/n temps moyen temps moyen/n 0 : 25.691 ns Infinity 25.719 ns Infinity 1 : 25.507 ns 25.507 83.093 ns 83.093 2 : 44.825 ns 22.413 144.786 ns 72.393 3 : 58.822 ns 19.607 176.024 ns 58.675 4 : 71.402 ns 17.850 213.505 ns 53.376 5 : 84.822 ns 16.964 242.324 ns 48.465 6 : 98.012 ns 16.335 272.510 ns 45.418 7 : 111.024 ns 15.861 307.292 ns 43.899 8 : 125.011 ns 15.626 341.547 ns 42.693 9 : 157.617 ns 17.513 379.537 ns 42.171 10 : 168.974 ns 16.897 411.250 ns 41.125 11 : 182.893 ns 16.627 445.017 ns 40.456 12 : 195.668 ns 16.306 474.886 ns 39.574 13 : 208.329 ns 16.025 509.971 ns 39.229 14 : 220.073 ns 15.719 563.928 ns 40.281 15 : 232.637 ns 15.509 591.515 ns 39.434 16 : 246.418 ns 15.401 631.020 ns 39.439 17 : 261.945 ns 15.409 676.189 ns 39.776 18 : 276.072 ns 15.337 707.757 ns 39.320 19 : 291.874 ns 15.362 743.275 ns 39.120 20 : 307.557 ns 15.378 784.396 ns 39.220 21 : 322.518 ns 15.358 812.045 ns 38.669 22 : 359.528 ns 16.342 856.067 ns 38.912 23 : 374.276 ns 16.273 890.110 ns 38.700 24 : 389.430 ns 16.226 929.483 ns 38.728 25 : 405.205 ns 16.208 958.697 ns 38.348 26 : 418.613 ns 16.101 1000.282 ns 38.472 27 : 432.925 ns 16.034 1051.869 ns 38.958 28 : 455.011 ns 16.250 1086.294 ns 38.796 29 : 464.807 ns 16.028 1109.021 ns 38.242 30 : 481.961 ns 16.065 1140.838 ns 38.028 31 : 498.391 ns 16.077 1175.716 ns 37.926 32 : 505.761 ns 15.805 1225.873 ns 38.309 33 : 526.963 ns 15.969 1272.604 ns 38.564 34 : 546.657 ns 16.078 1307.926 ns 38.468 35 : 554.295 ns 15.837 1341.532 ns 38.329 36 : 573.323 ns 15.926 1372.868 ns 38.135 37 : 586.537 ns 15.852 1406.502 ns 38.014 38 : 618.955 ns 16.288 1466.772 ns 38.599 39 : 620.827 ns 15.919 1484.808 ns 38.072 40 : 637.540 ns 15.938 1540.466 ns 38.512 41 : 677.424 ns 16.523 1561.219 ns 38.079 42 : 671.702 ns 15.993 1585.461 ns 37.749 43 : 680.366 ns 15.822 1637.952 ns 38.092 44 : 697.982 ns 15.863 1660.846 ns 37.746 45 : 716.543 ns 15.923 1710.896 ns 38.020 46 : 729.707 ns 15.863 1734.906 ns 37.715 47 : 733.368 ns 15.604 1772.600 ns 37.715 48 : 765.124 ns 15.940 1799.622 ns 37.492 49 : 767.049 ns 15.654 1859.098 ns 37.941 50 : 784.632 ns 15.693 1897.001 ns 37.940 51 : 810.910 ns 15.900 1931.814 ns 37.879 52 : 813.833 ns 15.651 1957.819 ns 37.650 53 : 825.798 ns 15.581 1983.401 ns 37.423 54 : 861.164 ns 15.947 2008.528 ns 37.195 55 : 866.702 ns 15.758 2056.789 ns 37.396 56 : 884.293 ns 15.791 2101.848 ns 37.533 57 : 913.642 ns 16.029 2150.822 ns 37.734 58 : 926.238 ns 15.970 2170.248 ns 37.418 59 : 934.671 ns 15.842 2193.710 ns 37.182 60 : 958.952 ns 15.983 2224.266 ns 37.071 61 : 964.697 ns 15.815 2286.571 ns 37.485 62 : 975.936 ns 15.741 2294.397 ns 37.006 63 : 1009.477 ns 16.023 2345.187 ns 37.225 64 : 1007.723 ns 15.746 2388.096 ns 37.314 65 : 1027.832 ns 15.813 2407.582 ns 37.040 66 : 1048.067 ns 15.880 2441.786 ns 36.997 67 : 1047.380 ns 15.633 2491.308 ns 37.184 68 : 1074.674 ns 15.804 2514.734 ns 36.981 69 : 1080.798 ns 15.664 2556.611 ns 37.052 70 : 1105.873 ns 15.798 2608.566 ns 37.265 71 : 1096.328 ns 15.441 2648.049 ns 37.296 72 : 1120.236 ns 15.559 2675.789 ns 37.164 73 : 1151.293 ns 15.771 2726.840 ns 37.354 74 : 1156.816 ns 15.633 2734.110 ns 36.947 75 : 1189.045 ns 15.854 2799.429 ns 37.326 76 : 1185.735 ns 15.602 2832.587 ns 37.271 77 : 1206.536 ns 15.669 2885.609 ns 37.475 78 : 1215.185 ns 15.579 2934.692 ns 37.624 79 : 1223.903 ns 15.492 2937.063 ns 37.178 80 : 1234.924 ns 15.437 2964.229 ns 37.053 81 : 1269.444 ns 15.672 3021.173 ns 37.298 82 : 1262.674 ns 15.398 3061.524 ns 37.336 83 : 1283.989 ns 15.470 3065.076 ns 36.929 84 : 1294.707 ns 15.413 3102.679 ns 36.937 85 : 1299.747 ns 15.291 3158.455 ns 37.158 86 : 1325.159 ns 15.409 3200.429 ns 37.214 87 : 1344.332 ns 15.452 3218.643 ns 36.996 88 : 1339.409 ns 15.221 3266.705 ns 37.122 89 : 1372.255 ns 15.419 3153.791 ns 35.436 90 : 1365.011 ns 15.167 3165.706 ns 35.175 91 : 1321.552 ns 14.523 3197.950 ns 35.142 92 : 1329.555 ns 14.452 3252.840 ns 35.357 93 : 1367.726 ns 14.707 3282.062 ns 35.291 94 : 1411.332 ns 15.014 3335.993 ns 35.489 95 : 1402.680 ns 14.765 3371.839 ns 35.493 96 : 1412.224 ns 14.711 3431.485 ns 35.745 97 : 1428.504 ns 14.727 3426.484 ns 35.325 98 : 1427.837 ns 14.570 3512.097 ns 35.838 99 : 1441.701 ns 14.563 3524.225 ns 35.598 100 : 1469.973 ns 14.700 3550.132 ns 35.501
On constate un différentiel de temps de l'ordre de 2.5 en faveur de la version itérative. Cela s'explique par le fait que l'utilisation de la récursivité implique des appels de fonction et que ces appels de fonction ont un coût en terme de temps d'exécution.