Algorithmique & Programmation Orientée Objet Semestre 2 ST Précision, rapidité & complexité
Cours | TD | TP - Corrections
Clavier.class - Ecran.class - Documentation
Première partie: Adapter l'environnement Scite pour réaliser des mesures de temps fiables et pouvoir utiliser plus de mémoire Mesurer des temps représentatifs! Dans le but d'accélérer les programmes Java réalise une analyse du code contenu dans les fichiers .class dans le but d'en optimiser le fonctionnement. Cette démarche est très efficace. Elle permet des facteurs d'accélération qui peuvent aller jusqu'à 10.0 voire plus. Le problème est que ce ne sont plus réellement nos algorithmes qui sont exécutés, mais nos algorithmes après optimisation automatique. Les temps d'exécution risquent donc de ne plus être fiables. L'option d'exécution -Xint permet d'interdire à Java de réaliser ces optimisations en l'obligeant à interpréter strictement le code programmé et compilé. Permettre l'utilisation de plus de mémoire Par défaut un programme Java peut déclarer au maximum 256 Mo de variables. Cette quantité de mémoire est relativement limitée et peut être inférieure à la quantité minimale nécessaire à l'implantation d'un problème à résoudre. Il peut donc être nécessaire de l'augmenter. Les options d'exécution -Xxms1024m -Xxmx1024m permettent d'augmenter à 1024 Mo la mémoire disponible (1024 Mo au lancement et au maximum) pour l'application exécutée, c'est à dire 4 fois plus que la valeur par défaut. Adapter la taille de la pile Par défaut un programme Java possède une pile limitée à 64 Ko. Cette quantité de mémoire est relativement limitée et peut conduire à des problèmes d'exécution lorsque la récursivité est utilisée car celle-ci utilise cette mémoire. Il peut donc être nécessaire d'augmenter la taille de la pile. L'option d'exécution -Xss64m permet d'augmenter à 64 Mo la mémoire disponible pour la pile, c'est à dire un peu plus de 1000 fois plus que la valeur par défaut. Configurer Scite Le fichier suivant: SciTE.properties peut être téléchargé et copié dans le répertoire qui contient les fichiers .java (et .class) à compiler/exécuter. Ce fichier contient des options de paramètrage de SciTE qui seront prises en compte pour tous les fichiers .java situés dans ce répertoire. La ligne importante est: command.go.*.java=java -Xms1024m -Xmx1024m -Xss64m -Xint $(FileName) C'est cette ligne qui configure l'exécution pour une quantité de mémoire utilisable égale à 1024 Mo, une pile de 64 Mo et une interprétation stricte du code. Elle correspond à l'entrée "Go" du menu "Tools" à laquelle est associé le racourci clavier F5. Deuxième partie Télécharger et installer le fichier SciTE.properties dans votre répertoire de travail Algo-POO. 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 théorique 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? 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écution individuels des deux appels à la fonction initRandMatrice et le temps d'exécution 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) théoriques 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? 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.
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). 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; }