Algorithmique & Programmation Orientée Objet Semestre 2 ST Précision, rapidité & complexité
Cours | TD | TP - Corrections
Clavier.class - Ecran.class - Documentation
Les programmes de test des exercices ont été implantés de manière à générer un lot de mesures de performance pour des tailles d'"ensemble" traité allant d'une borne initiale bi à une borne finale bf avec un incrément inc donnés. Une durée d est définie (10 secondes par exemple) pour chaque test. La durée totale d'exécution du programme est donc voisine de d*(bf-bi)/inc. La durée d est d'abord demandée, puis la borne bi, la borne bf et l'incrément inc. A chaque test, un Minuteur est créé, configuré pour la durée d et lancé. Une boucle tant que est implantée dont la candition d'arrêt porte sur le booléen du Minuteur et dont le contenu consiste en un appel à la fonction testée. Le nombre d'appels réalisés est comptabilisé au moyen d'un compteur. Pour obtenir le temps d'exécution d'un appel, le temps global est divisé par le nombre d'appels. Exercice n°1
TestFactoriel.java /* Calcul de n! par methode recursive */ /* - 0! = 1 */ /* - n! = (n-1)!*n */ static long factorielRecursif(int n) { if ( n == 0 ) { return 1; } else { return factorielRecursif(n-1)*n; } } /* Calcul de n! par methode sequentielle */ static long factorielSequentiel(int n) { long res = 1; if ( n > 1 ) for ( int i = 2 ; i <= n ; i++ ) { res = res*i; } return res; } static void testsFactoriel(int temps,int ni,int nf,int inc) { Ecran.afficherln("Itératif récursif"); Ecran.formater("%6s%21s%12s%14s%14s%14s%12s%14s%14s%14s\n", "Niveau","Resultat","Appels","Temps total", "Temps moyen","o(n)", "Appels","Temps total","Temps moyen","o(n)"); for ( int nu = ni ; nu <= nf ; nu = nu+inc ) { long n = factorielSequentiel(nu); { Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur(); minuteur.temps = temps*1000; minuteur.lancement(); long i = 0; long ti = System.nanoTime(); do { factorielSequentiel(nu); i++; } while ( minuteur.enCours ); long t = System.nanoTime()-ti; Ecran.formater("%6d%21d%12d%14d%14.3f%14.4f", nu,n,i,t,(double) t/i,(double) t/i/nu); } { Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur(); minuteur.temps = temps*1000; minuteur.lancement(); long i = 0; long ti = System.nanoTime(); do { factorielRecursif(nu); i++; } while ( minuteur.enCours ); long t = System.nanoTime()-ti; Ecran.formater("%12d%14d%14.3f%14.4f\n", i,t,(double) t/i,(double) t/i/nu); } } } Clavier.class - Ecran.class - Exemple d'exécution
Le tableau des temps calculés expérimentalement est donné ci-dessous pour les versions séquentielle et récursive. Les deux premières colonnes donnent la valeur n sur laquelle la factorielle est calculée ainsi que le résultat du calcul. Les colonnes données en séquentiel et en récursif sont le nombre d'appels réalisés en 10 secondes (quand un 1 apparait dans cette colonne, il n'y a eu qu'un seul appel qui a pris plus voire beaucoup plus de 10 secondes), le temps moyen d'un appel (en ns), le rapport temps moyen/n. Enfin une colonne donne le temps moyen en récursif divisé par le temps moyen en séquentiel. La récursivité maximale obtenue dans les conditions du test a été de l'ordre de 9200. L'overflow constaté sur le résultat du calcul de f(n) n'a pas d'incidence sur la vitesse de calcul et n'entraine pas de plantage pur et simple de l'application. La valeur n'est simplement pas bonne. Les deux colonnes temps moyen/n permettent de tester l'hypothèse de linéarité. Les valeurs qu'elles contiennent devraient être constantes. La dernière colonne donne le temps moyen en récursif divisé par le temps moyen en séquentiel et a pour but de comparer les vitesses respectives des 2 versions pour déterminer quelle méthode est la plus rapide.
Conclusion: - La linéarité des deux algorithmes est vérifiée: valeur t/n voisine de 3.6 en séquentiel et 4.8 en récusif. En récursif, on note toutefois une transition qui débute vers n=500 avec un ralentissement de la vitesse de fonctionnement qui s'amplifie avec la profondeur de récursivité. Cette transition est difficilement explicable. Elle est liée au fonctionnement intime de la récursivité et est peut-être le résultat de l'utilisation de mémoire pour la gestion des appels en profondeur. - A l'exception de n = 0 où les deux versions sont de vitesses équivalente, la version séquentielle est systématiquement plus rapide que la version récursive d'environ 1/3 jusqu'à 500 en croissance au delà. Exercice n°2 Produit matrice-vecteur Deux versions de la fonction produit matrice-vecteur ont été testées: - Une version avec tableau retourné et donc déclaration par new du tableau retourné dans la fonction - Une version avec tableau en résultat en paramètre d'entête et donc déclaration par new du tableau résultat dans l'algorithme appelant à l'extérieur de la fonction
TestProduitMatriceVecteur.java /* Fonction de calcul du produit d'une matrice */ /* carree de reel de taille n.n par un tableau */ /* de reel de taille n */ /* n quelconque */ /* Retour: Un tableau de reel de taille n */ static double [] produitMatriceVecteur(double [][] m, double [] v) { int n = v.length; double [] w = new double[n]; for ( int i = 0 ; i < n ; i++ ) { w[i] = 0.0; for ( int j = 0 ; j < n ; j++ ) { w[i] = w[i] + m[i][j]*v[j]; } } return w; } /* Fonction de calcul du produit d'une matrice */ /* carree de reel de taille n.n par un tableau */ /* de reel de taille n */ /* n quelconque */ /* Resultat: Un tableau de reel de taille n */ static void produitMatriceVecteur(double [][] m, double [] v, double [] w) { int n = v.length; for ( int i = 0 ; i < n ; i++ ) { w[i] = 0.0; for ( int j = 0 ; j < n ; j++ ) { w[i] = w[i] + m[i][j]*v[j]; } } } static void testsProduitMatriceVecteur(int temps,int ni,int nf,int inc) { Ecran.formater("%6s%12s%14s%22s%14s%12s%14s%22s%14s\n", "Taille","Appels","Temps total","Temps moyen", "o(n^2)", "Appels","Temps total","Temps moyen","o(n^2)"); for ( int n = ni ; n <= nf ; n = n+inc ) { double [][] m = initRandMatrice(n,n,10.0); double [] v = initRandVecteur(n,10.0); { double [] w = new double[n]; Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur(); minuteur.temps = temps*1000; minuteur.lancement(); long i = 0; long ti = System.nanoTime(); do { produitMatriceVecteur(m,v,w); i++; } while ( minuteur.enCours ); long t = System.nanoTime()-ti; Ecran.formater("%6d%12d%14d%22.3f%14.4f", n,i,t,(double) t/i, ((double) t/i)/((double) n*n)); } { Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur(); minuteur.temps = temps*1000; minuteur.lancement(); long i = 0; long ti = System.nanoTime(); double [] w; do { w = produitMatriceVecteur(m,v); i++; } while ( minuteur.enCours ); long t = System.nanoTime()-ti; Ecran.formater("%12d%14d%22.3f%14.4f\n", i,t,(double) t/i, ((double) t/i)/((double) n*n)); } } } Clavier.class - Ecran.class - Exemple d'exécution
Le tableau ci-dessous présente les temps obtenus expérimentalement pour des tests élémentaires de 10 secondes. La première colonne donne la taille n. On a ensuite 3 colonnes pour chacune des deux fonctions: le nombre d'appels réalisés en 10 secondes, le temps moyen nécessaire à chaque appel, le rapport temps moyen sur n2. Les deux colonnes temps moyen/n2 permettent de tester l'hypothèse de temps quadratique. Les valeurs qu'elles contiennent devraient être constantes.
Conclusion: - Le temps quadratique des deux algorithmes est vérifié: valeur t/n2 voisine de 4.2 en version avec retour et version avec résultat en entête. On note que la convergence vers cette valeur arrive vers n=40 où la quantité de calcul du produit matriciel devient très supérieure à la quantité de calcul nécessaire à la gestion de l'appel de fonction. - Pour les petites valeurs de n pour lesquels le temps de calcul du produit matriciel n'est pas considérablement plus grand que le temps de gestion de l'appel de fonction, on constate que, logiquement, la fonction avec retour est moins rapide que la fonction avec résultat en entête. En effet, la fonction avec retour nécessite la déclaration par new du tableau retourné dans le corps qui est une opération assez longue. Produit matrice-matrice
TestProduitMatriceMatrice.java /* Fonction de calcul du produit d'un tableau */ /* de dimension 2 de taille n.n */ /* par un tableau de dimension 2 de taille n.n */ /* Resultat: Un tableau de dimension 2 */ /* de taille n.n */ static void produitMatricesCarrees(double [][] m1,double [][] m2, double [][] r) { int n = m1.length; for ( int i = 0 ; i < n ; i++ ) { for ( int j = 0 ; j < n ; j++ ) { double v = 0.0; for ( int k = 0 ; k < n ; k++ ) { v += m1[i][k]*m2[k][j]; } r[i][j] = v; } } } /* Fonction de calcul du produit d'un tableau */ /* de dimension 2 de taille n.m */ /* par un tableau de dimension 2 de taille m.p */ /* Resultat: Un tableau de dimension 2 */ /* de taille n.p */ static void produitMatriceMatrice(double [][] m1,double [][] m2, double [][] r) { int n = m1.length; int m = m2.length; int p = m2[0].length; for ( int i = 0 ; i < n ; i++ ) { for ( int j = 0 ; j < p ; j++ ) { double v = 0.0; for ( int k = 0 ; k < m ; k++ ) { v += m1[i][k]*m2[k][j]; } r[i][j] = v; } } } static void testsProduitMatricesCarrees(int temps,int ni,int nf,int inc) { Ecran.formater("%6s%12s%14s%22s%14s\n", "Taille","Appels","Temps total","Temps moyen", "o(n*n*n)"); for ( int n = ni ; n <= nf ; n = n+inc ) { double [][] m1 = initRandMatrice(n,n,10.0); double [][] m2 = initRandMatrice(n,n,10.0); double [][] m = new double[n][n]; Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur(); minuteur.temps = temps*1000; minuteur.lancement(); long i = 0; long ti = System.nanoTime(); do { if ( i%2 == 0 ) produitMatricesCarrees(m1,m2,m); else produitMatricesCarrees(m2,m1,m); i++; } while ( minuteur.enCours ); long t = System.nanoTime()-ti; Ecran.formater("%6d%12d%14d%22.3f%14.4f\n", n,i,t,(double) t/i, ((double) t/i)/((double) n*n*n)); } } static void testsProduitMatricesQuelconques(int temps,int ni,int nf,int inc) { Ecran.formater("%18s%12s%14s%22s%14s\n", "Tailles","Appels","Temps total","Temps moyen", "o(n*m*p)"); for ( int n = ni ; n <= nf ; n = n+inc ) { for ( int m = ni ; m <= nf ; m = m+inc ) { for ( int p = ni ; p <= nf ; p = p+inc ) { double [][] m1 = initRandMatrice(n,m,10.0); double [][] m2 = initRandMatrice(m,p,10.0); double [][] mat = new double[n][p]; Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur(); minuteur.temps = temps*1000; minuteur.lancement(); long i = 0; long ti = System.nanoTime(); do { produitMatriceMatrice(m1,m2,mat); i++; } while ( minuteur.enCours ); long t = System.nanoTime()-ti; Ecran.formater("%6d%6d%6d%12d%14d%22.3f%14.4f\n", n,m,p,i,t,(double) t/i, ((double) t/i)/((double) n*m*p)); } } } } Clavier.class - Ecran.class - Exemple d'exécution
Produit de matrices carrées Le tableau ci-dessous présente les temps obtenus expérimentalement pour des tests élémentaires de 10 secondes. La première colonne donne la taille n. On a ensuite 3 colonnes: le nombre d'appels réalisés en 10 secondes, le temps moyen nécessaire à chaque appel, le rapport temps moyen sur n3. La colonne temps moyen/n3 perme de tester l'hypothèse de temps cubique. Les valeurs qu'elle contient devraient être constantes.
Conclusion: - Le temps cubique de l'algorithme n'est pas vérifié. Produit de matrices quelconques Exercice n°3
TestRecursiviteEnArbreParfait.java /* Parcours recursif en arbre unaire */ /* de profondeur n */ static long parcoursUnaire(int n) { long nb = 1; if ( n > 0 ) { nb = nb+parcoursUnaire(n-1); } return nb; } /* Parcours recursif en arbre binaire parfait */ /* de profondeur n */ static long parcoursBinaire(int n) { long nb = 1; if ( n > 0 ) { nb = nb+parcoursBinaire(n-1); nb = nb+parcoursBinaire(n-1); } return nb; } /* Parcours recursif en arbre ternaire parfait */ /* de profondeur n */ static long parcoursTernaire(int n) { long nb = 1; if ( n > 0 ) { nb = nb+parcoursTernaire(n-1); nb = nb+parcoursTernaire(n-1); nb = nb+parcoursTernaire(n-1); } return nb; } static void testsRapiditeEnUnaire(int temps,int ni,int nf,int inc) { long i; long ti; long t; long n; long tMax = temps*1000000000L; i = 0; ti = System.nanoTime(); do { n = parcoursUnaire(5); t = System.nanoTime()-ti; i++; } while ( t < tMax) ; Ecran.formater("%6s","Taille"); Ecran.formater("%16s","Resultats"); Ecran.formater("%12s","Appels"); Ecran.formater("%14s","Temps total"); Ecran.formater("%14s","Temps moyen"); Ecran.formater("%14s","o(n)"); Ecran.formater("\n"); for ( int nu = ni ; nu <= nf ; nu = nu+inc ) { n = parcoursUnaire(nu); Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur(); minuteur.temps = temps*1000; minuteur.lancement(); i = 0; ti = System.nanoTime(); do { parcoursUnaire(nu); i++; } while ( minuteur.enCours ); t = System.nanoTime()-ti; Ecran.formater("%6d",nu); Ecran.formater("%16d",n); Ecran.formater("%12d",i); Ecran.formater("%14d",t); Ecran.formater("%14d",t/i); double rp =(double)t/i/nu; Ecran.formater("%14.4f\n",rp); } } static void testsRapiditeEnBinaire(int temps,int ni,int nf,int inc) { long i; long ti; long t; long n; long tMax = temps*1000000000L; i = 0; ti = System.nanoTime(); do { n = parcoursBinaire(5); t = System.nanoTime()-ti; i++; } while ( t < tMax) ; Ecran.formater("%6s","Taille"); Ecran.formater("%16s","Resultats"); Ecran.formater("%12s","Appels"); Ecran.formater("%14s","Temps total"); Ecran.formater("%14s","Temps moyen"); Ecran.formater("%14s","o(2^n)"); Ecran.formater("\n"); for ( int nu = ni ; nu <= nf ; nu = nu+inc ) { n = parcoursBinaire(nu); Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur(); minuteur.temps = temps*1000; minuteur.lancement(); i = 0; ti = System.nanoTime(); do { parcoursBinaire(nu); i++; } while ( minuteur.enCours ); t = System.nanoTime()-ti; Ecran.formater("%6d",nu); Ecran.formater("%16d",n); Ecran.formater("%12d",i); Ecran.formater("%14d",t); Ecran.formater("%14d",t/i); double rp =(double)t/i/Math.pow(2,nu); Ecran.formater("%14.4f\n",rp); } } static void testsRapiditeEnTernaire(int temps,int ni,int nf,int inc) { long i; long ti; long t; long n; long tMax = temps*1000000000L; i = 0; ti = System.nanoTime(); do { n = parcoursUnaire(5); t = System.nanoTime()-ti; i++; } while ( t < tMax) ; Ecran.formater("%6s","Taille"); Ecran.formater("%16s","Resultats"); Ecran.formater("%12s","Appels"); Ecran.formater("%14s","Temps total"); Ecran.formater("%14s","Temps moyen"); Ecran.formater("%14s","o(3^n)"); Ecran.formater("\n"); for ( int nu = ni ; nu <= nf ; nu = nu+inc ) { n = parcoursTernaire(nu); Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur(); minuteur.temps = temps*1000; minuteur.lancement(); i = 0; ti = System.nanoTime(); do { parcoursTernaire(nu); i++; } while ( minuteur.enCours ); t = System.nanoTime()-ti; Ecran.formater("%6d",nu); Ecran.formater("%16d",n); Ecran.formater("%12d",i); Ecran.formater("%14d",t); Ecran.formater("%14d",t/i); double rp =(double)t/i/Math.pow(3,nu); Ecran.formater("%14.4f\n",rp); } } Clavier.class - Ecran.class - Exemple d'exécution
En unaire, binaire et ternaire, sont présentés les tableaux avec les colonnes n, f(n), nombre d'appels pour 10 secondes de test, temps moyen pour 1 appel, temps/o(t). La dernière colonne devrait présenter des valeurs constantes si l'hypothèse de temps est vérifiée. Unaire
Binaire
Ternaire

En unaire, l'hypothèse de linéarité est bien vérifiée jusqu'à un niveau de récursivité voisin de 1000. Au delà, il semble qu'une composante non linéaire (logarithmique?) apparaisse.

Binaire

Ternaire

En binaire et en ternaire les hypothèses sont bien vérifiées. On constate toutefois une étrangeté: Les valeurs de test sont différentes pour les niveaux de récursivité pairs et impairs. Cette bizarrerie doit être liée à l'utilisation du langage Java, car le même test réalisé avec les mêmes fonctions programmées en langage C ne fait pas apparaître cette aternance.