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 mntr = new Utilitaires.Minuteur(); mntr.temps = temps*1000; mntr.lancement(); long i = 0; long ti = System.nanoTime(); do { factorielSequentiel(nu); i++; } while ( mntr.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 mntr = new Utilitaires.Minuteur(); mntr.temps = temps*1000; mntr.lancement(); long i = 0; long ti = System.nanoTime(); do { factorielRecursif(nu); i++; } while ( mntr.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 nanosecondes), 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: - On note l'existence d'une période de transition à partir de n = 0. Celle-ci est liée au fait que l'on ne mesure pas absolument exactement le temps d'exécution que l'on souhaite, mais ce temps plus une certaine quantité de temps liée aux opérations de gestion du protocole de mesure (boucle de mesure, gestion du compteur, appel de fonction, ...). Ces temps de gestion deviennent rapidement négligeables par rapport aux temps que l'on souhaite mesurer. Les valeurs deviennent alors représentatives. - La linéarité des deux algorithmes est vérifiée: valeur t/n de l'ordre de 16.0 en séquentiel et 38.0 en récusif. En récursif, on constate toutefois une courbe moins "simple" qu'en itératif. Une première période de relaxation (voir ci-dessus) qui se termine vers n = 65 avec une valeur t/n voisine de 35.0. Elle est suivie d'une remontée régulière jusqu'à n = 200 et t/n = 38.0. On trouve ensuite une première portion stable à t/n = 38.0 qui se termine vers n = 40000. Cette période stable est suivie d'une période de transtion avec croissance jusqu'à t/n = pour n voisin de . Enfin, une seconde portion de stabilité se met en place à t/n = . L'explication de ces variations est certainement à trouver dans le fait que la gestion récusivité nécessite l'utilisation de mémoire, que la quantité de mémoire utilisée augmente linéairement avec le niveau de profondeur récursive, que l'architecture des ordinateurs fait que le temps d'accès à la mémoire varie beaucoup avec la quantité de mémoire utilisée, et que cette variation n'est pas linéaire (en escalier) et dépend de la machine utilisée. En itératif, la seule mémoire utilisée est celle déclarée dans l'algorithme. On constate donc une très bonne linéarité. En récursif, la liéarité théorique est seulement constatée sur les intervalle où le problème d'accès mémoire n'apparait pas: [200,40000] et [ ,µ]. - A l'exception de n = 0, la version séquentielle est systématiquement plus rapide que la version récursive d'un facteur qui est voisin de 2.4 sur la première portion stable et sur la seconde portion stable. 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 mntr = new Utilitaires.Minuteur(); mntr.temps = temps*1000; mntr.lancement(); long i = 0; long ti = System.nanoTime(); do { produitMatriceVecteur(m,v,w); i++; } while ( mntr.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 mntr = new Utilitaires.Minuteur(); mntr.temps = temps*1000; mntr.lancement(); long i = 0; long ti = System.nanoTime(); double [] w; do { w = produitMatriceVecteur(m,v); i++; } while ( mntr.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 (en nanosecondes), 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 mntr = new Utilitaires.Minuteur(); mntr.temps = temps*1000; mntr.lancement(); long i = 0; long ti = System.nanoTime(); do { if ( i%2 == 0 ) produitMatricesCarrees(m1,m2,m); else produitMatricesCarrees(m2,m1,m); i++; } while ( mntr.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 testsProduitMatrices(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 mntr = new Utilitaires.Minuteur(); mntr.temps = temps*1000; mntr.lancement(); long i = 0; long ti = System.nanoTime(); do { produitMatriceMatrice(m1,m2,mat); i++; } while ( mntr.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)); } } } } static void testsProduitMatricesN(int temps,int ni,int nf, int inc,int m,int p) { 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 ) { { double [][] m1 = initRandMatrice(n,m,10.0); double [][] m2 = initRandMatrice(m,p,10.0); double [][] mat = new double[n][p]; Utilitaires.Minuteur mntr = new Utilitaires.Minuteur(); mntr.temps = temps*1000; mntr.lancement(); long i = 0; long ti = System.nanoTime(); do { produitMatriceMatrice(m1,m2,mat); i++; } while ( mntr.enCours ); long t = System.nanoTime()-ti; Ecran.formater("%6d%6d%6d%12d%14d%22.3f%14.4f%10s\n", n,m,p,i,t,(double) t/i, ((double) t/i)/((double) n*m*p), heureActuelle()); } System.gc(); } } static void testsProduitMatricesM(int temps,int mi,int mf, int inc,int n,int p) { Ecran.formater("%18s%12s%14s%22s%14s\n", "Tailles","Appels","Temps total","Temps moyen", "o(n*m*p)"); for ( int m = mi ; m <= mf ; m = m+inc ) { { double [][] m1 = initRandMatrice(n,m,10.0); double [][] m2 = initRandMatrice(m,p,10.0); double [][] mat = new double[n][p]; Utilitaires.Minuteur mntr = new Utilitaires.Minuteur(); mntr.temps = temps*1000; mntr.lancement(); long i = 0; long ti = System.nanoTime(); do { produitMatriceMatrice(m1,m2,mat); i++; } while ( mntr.enCours ); long t = System.nanoTime()-ti; Ecran.formater("%6d%6d%6d%12d%14d%22.3f%14.4f%10s\n", n,m,p,i,t,(double) t/i, ((double) t/i)/((double) n*m*p), heureActuelle()); } System.gc(); } } static void testsProduitMatricesP(int temps,int pi,int pf, int inc,int n,int m) { Ecran.formater("%18s%12s%14s%22s%14s\n", "Tailles","Appels","Temps total","Temps moyen", "o(n*m*p)"); for ( int p = pi ; p <= pf ; 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 mntr = new Utilitaires.Minuteur(); mntr.temps = temps*1000; mntr.lancement(); long i = 0; long ti = System.nanoTime(); do { produitMatriceMatrice(m1,m2,mat); i++; } while ( mntr.enCours ); long t = System.nanoTime()-ti; Ecran.formater("%6d%6d%6d%12d%14d%22.3f%14.4f%10s\n", n,m,p,i,t,(double) t/i, ((double) t/i)/((double) n*m*p), heureActuelle()); } System.gc(); } } static void testsProduitMatricesN(int temps,int ni,int nf, int inc,int deb,int fin,int pas) { for ( int i = deb ; i <= fin ; i+= pas ) { testsProduitMatricesN(temps,ni,nf,inc,i,i); } } static void testsProduitMatricesM(int temps,int mi,int mf, int inc,int deb,int fin,int pas) { for ( int i = deb ; i <= fin ; i+= pas ) { testsProduitMatricesM(temps,mi,mf,inc,i,i); } } static void testsProduitMatricesP(int temps,int pi,int pf, int inc,int deb,int fin,int pas) { for ( int i = deb ; i <= fin ; i+= pas ) { testsProduitMatricesP(temps,pi,pf,inc,i,i); } } 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 (en nanosecondes), le rapport temps moyen sur n3. La colonne temps moyen/n3 permet 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; } /* Parcours recursif en arbre parfait d'arite */ /* quelconque et de profondeur n */ static long parcoursNaire(int n,int arite) { long nb = 1; if ( n > 0 ) { for ( int i = 0 ; i < arite ; i++ ) { nb = nb+parcoursNaire(n-1,arite); } } return nb; } static void testsEnUnaire(int temps,int ni,int nf,int inc) { Ecran.formater("%8s%12s%14s%14s%22s%14s\n", "Niveau","Appels","Temps total","Temps total", "Temps moyen","o(n)"); for ( int n = ni ; n <= nf ; n = n+inc ) { { Utilitaires.Minuteur mntr = new Utilitaires.Minuteur(); mntr.temps = temps*1000; mntr.lancement(); long i = 0; long ti = System.nanoTime(); do { parcoursUnaire(n); i++; } while ( mntr.enCours ); long t = System.nanoTime()-ti; Ecran.formater("%8d%12d%14d%14d%22.3f%14.4f\n", n,i,t,mntr.dt,(double) t/i,((double) t/i)/n); } System.gc(); } } static void testsEnBinaire(int temps,int ni,int nf,int inc) { Ecran.formater("%8s%12s%14s%22s%14s\n", "Niveau","Appels","Temps total", "Temps moyen","o(2^n)"); for ( int n = ni ; n <= nf ; n = n+inc ) { { Utilitaires.Minuteur mntr = new Utilitaires.Minuteur(); mntr.temps = temps*1000; mntr.lancement(); long i = 0; long ti = System.nanoTime(); do { parcoursBinaire(n); i++; } while ( mntr.enCours ); long t = System.nanoTime()-ti; Ecran.formater("%8d%12d%14d%22.3f%14.4f\n", n,i,t,(double) t/i, ((double) t/i)/Math.pow(2,n)); } System.gc(); } } static void testsEnTernaire(int temps,int ni,int nf,int inc) { Ecran.formater("%8s%12s%14s%22s%14s\n", "Niveau","Appels","Temps total", "Temps moyen","o(3^n)"); for ( int n = ni ; n <= nf ; n = n+inc ) { { Utilitaires.Minuteur mntr = new Utilitaires.Minuteur(); mntr.temps = temps*1000; mntr.lancement(); long i = 0; long ti = System.nanoTime(); do { parcoursTernaire(n); i++; } while ( mntr.enCours ); long t = System.nanoTime()-ti; Ecran.formater("%8d%12d%14d%22.3f%14.4f\n", n,i,t,(double) t/i, ((double) t/i)/Math.pow(3,n)); } System.gc(); } } static void testsEnNaire(int temps,int ni,int nf,int inc,int arite) { Ecran.formater("%8s%12s%14s%22s%14s\n", "Niveau","Appels","Temps total", "Temps moyen","o(arite^n)"); for ( int n = ni ; n <= nf ; n = n+inc ) { Utilitaires.Minuteur mntr = new Utilitaires.Minuteur(); mntr.temps = temps*1000; mntr.lancement(); long i = 0; long ti = System.nanoTime(); do { parcoursNaire(n,arite); i++; } while ( mntr.enCours ); long t = System.nanoTime()-ti; System.gc(); Ecran.formater("%8d%12d%14d%22.3f%14.4f\n", n,i,t,(double) t/i, ((double) t/i)/Math.pow(arite,n)); } } Clavier.class - Ecran.class - Exemple d'exécution
En unaire, binaire et ternaire, les tableaux correspondant aux résultats expérimentaux sont présentés avec les colonnes n, f(n), nombre d'appels pour 60 secondes de test, temps moyen pour 1 appel (en nanosecondes), temps moyen/o(x) avec x = n en unaire, 2n en binaire, 3n en ternaire. La dernière colonne devrait présenter des valeurs constantes si les hypothèses de temps attendues sont vérifiées. Pour faciliter l'interprétation, des graphiques ont été générés. Conclusion en binaire et en ternaire:
Binaire (n de 0 à 40 par incrément de 1)
Ternaire (n de 0 à 25 par incrément de 1)
Les temps en o(2n) en binaire et o(3n) en ternaire sont bien vérifiés. 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. Conclusion en unaire:
Unaire (n de 0 à 1000 par incrément de 1)
Unaire (n de 0 à 9260 par incrément de 10, 9260 limite de récursivité)
Pas 1: Jusqu'à n égal à un peu plus de 30, l'hypothèse de linéarité est bien vérifiée. On retrouve l'étrangeté constatée en binaire et en ternaire avec une courbe en dents de scie. Pas 1: A n égal 33, on constate un décrochement avec dégradation des performances suivi d'un nouveau plat compatible avec l'hypothèse de linéarité. L'étrangeté constatée en binaire et en ternaire avec une courbe en dents de scie est toujours présente. Pas 1: A partir de n égal 67, l'étrangeté disparait et le plat continue. Pas 10: Le plat continue jusqu'à 500. Pas 10: Un nouveau décrochement intervient au alentours de n = 520, avec une nouvelle dégradation des performances progressive jusqu'à n voisin de 640 suivi d'une légère amélioration jusqu'à n voisin de 750. A partir de 750, on repart avec une dégradation progressive. Pas 10: La dégradation progressive se poursuit (tangentiellement?) jusqu'à la limite de profondeur de récursivité qui est voisine de 9600. En conclusion, l'hypothèse de linéarité est bien vérifiée entre les niveaux de récursivité 0 à 33 et 35 à 520. Au delà, il semble qu'une composante non linéaire (logarithmique?) apparaisse.