TP — Séance 2 — Analyse algorithmique

Compter, chercher, mesurer : vérifier une analyse en Java

TP de la séance 2 de Structures de données et algorithmes avancés : compter, borner, mesurer : le coût d’un algorithme.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Instrumenter des fragments pour compter leurs opérations, écrire soi-même le test d’un fragment, écrire la recherche séquentielle et la recherche dichotomique avec un compteur de cases examinées, compter les paires de somme nulle d’un tableau par deux algorithmes de classes différentes, puis confronter ces analyses à des durées mesurées par l’expérience du doublement, à des comptes exacts, et à la file de la Séance 1. Durée : une séance de TP.

À rendre. Le dépôt Git du projet (les classes complétées, les tests au vert) et un compte rendu de deux à trois pages qui répond aux questions marquées Observer, Expliquer et Modifier, en recopiant les sorties obtenues.

Préparation

Le TP se fait dans l’environnement Docker du cours (Java 17, Gradle 8, JUnit 5). Sur la machine, décompresser le code de départ, TP_S02_code_depart.zip, dans ~/dsa : le dossier TP_S02_code_depart/ apparaît. Le conteneur se lance depuis ce dossier :

cd ~/dsa
docker run -it --rm -v "$(pwd):/workspace" elbachirtoure/dsa-java:v2.0

Sous Windows (Git Bash), la commande docker run est précédée de MSYS_NO_PATHCONV=1. Dans le conteneur :

cd /workspace
new-project tp-s02
cd tp-s02
cp -r ../TP_S02_code_depart/. .
rm src/test/java/MainTest.java

Le code de départ contient dix fichiers, sept dans src/main/java/ et trois dans src/test/java/ : la copie les range dans le projet, en remplaçant le Main.java créé par new-project, et rm supprime le MainTest.java créé par new-project. Le dépôt Git du projet se crée dans tp-s02 : git init -b main et l’identité locale, comme à l’étape 7 du TP-1.

Fichier Rôle
Compteur.java le compteur d’opérations du cours (ajouter, total, remise) ; fourni
Chrono.java mediane(tache) : médiane de cinq durées d’exécution, en millisecondes ; fourni
Fragments.java produit et moities, deux fragments à instrumenter (étape 1)
Paliers.java paliers, un fragment à instrumenter, dont le test est à écrire (étape 2)
Recherche.java le compteur examinees ; sequentielle et dichotomie à écrire (étape 3)
Paires.java le compteur comparaisons ; compterNaif et compterRapide à écrire (étape 4)
Main.java programmes d’observation, fourni
FragmentsTest.java, RechercheTest.java, PairesTest.java treize tests JUnit, fournis ; PaliersTest.java est à créer (étape 2)

Les méthodes à écrire contiennent une consigne en commentaire et lèvent UnsupportedOperationException. Les deux commandes du TP sont gradle --no-daemon test et gradle --no-daemon run --args="mode", où mode vaut compter, recherche, doublement, comparer, file ou acces. Les opérations se comptent selon la convention du cours ; i = i / 2 et j += 2 comptent chacune pour 2 (un calcul, une affectation).

Observer. Lancer les tests avant d’écrire la moindre ligne : combien échouent, et avec quelle exception ?

Étape 1 : deux fragments comptés

Écrire produit et moities de Fragments : chacune exécute le fragment de sa javadoc et appelle op.ajouter(k) pour chaque opération exécutée, dans l’ordre où elle l’est.

  1. Observer. Les quatre tests de FragmentsTest doivent passer. Lancer le mode compter et recopier sa sortie.
  2. Expliquer. Établir à la main, instruction par instruction, la fonction de coût \(f(n)\) de produit, et vérifier qu’elle redonne les valeurs attendues par produitCompteSesOperations. Quelle est la classe \(\Theta\) de produit, alors qu’il contient deux boucles imbriquées ?
  3. Expliquer. Combien de tours fait la boucle de moities pour \(n=1\,000\), et pour \(n=1\,024\) ? Donner le nombre de tours en fonction de \(n\geq1\), puis \(f(n)\), et la vérifier sur les valeurs de moitiesCompteSesOperations.
  4. Modifier. Supprimer provisoirement, dans moities, l’appel qui compte le test qui fait sortir de la boucle. Quel test échoue, avec quel message, et pour quelle valeur de \(n\) en premier ? Revenir au code correct.

Étape 2 : écrire soi-même le test d’un fragment

La méthode paliers de Paliers exécute le fragment de sa javadoc, dont la boucle interne part de j = i et avance de 2 en 2. Aucun test n’est fourni : c’est à vous de l’écrire.

  1. Observer. Écrire paliers, en appelant op.ajouter(k) pour chaque opération exécutée, comme à l’étape 1. Sans test, comment savoir si elle est juste ?

  2. Expliquer. Combien de tours fait la boucle interne pour la ligne \(i\) ? Calculer à la main le nombre total de tours (la valeur rendue) pour \(n=1, 2, \dots, 6\), puis l’exprimer en fonction de \(n\), d’abord pour \(n\) pair, puis pour \(n\) impair, puis en une seule formule écrite en arithmétique entière.

    \(n\) 1 2 3 4 5 6
    tours de chaque ligne \(i=0, 1, \dots\)
    nombre total de tours
    \(f(n)\), à remplir en (c)

  3. Expliquer. Établir \(f(n)\), le nombre d’opérations, en fonction de \(n\) et du nombre total de tours. En déduire la classe \(\Theta\) de paliers.

  4. Observer. Créer src/test/java/PaliersTest.java, avec une méthode @Test nommée paliersSuitSaFormule qui, pour chaque \(n\) de 0 à 3 000, compare la valeur rendue par paliers et op.total() aux formules de (b) et (c) par assertEquals. Les formules sont calculées en long, sans double. Le test doit passer. Squelette, à compléter :

    import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

public class PaliersTest {
    @Test
    void paliersSuitSaFormule() {
        for (int n = 0; n <= 3000; n++) {
            Compteur op = new Compteur();
            long c = Paliers.paliers(n, op);
            // tours : la formule de (b), en long
            // assertEquals(attendu, obtenu) pour c, puis pour op.total()
        }
    }
}

  5. Expliquer. Pourquoi éviter le type double dans ce test ? Pourquoi long plutôt que int ? Pourquoi tester 3 001 valeurs de \(n\), et non deux ou trois ?

  6. Modifier. Supprimer provisoirement, dans paliers, l’appel qui compte le test qui fait sortir de la boucle interne. Votre test échoue-t-il, avec quel message, et pour quelle valeur de \(n\) en premier ? Pourquoi pas pour \(n=0\) ? Revenir au code correct.

Étape 3 : chercher, et compter les cases examinées

Écrire sequentielle et dichotomie de Recherche. Chacune incrémente examinees à chaque case comparée à x ; la dichotomie est celle du cours, écrite avec une boucle while.

  1. Observer. Les cinq tests de RechercheTest doivent passer. Lancer le mode recherche et recopier sa sortie.
  2. Expliquer. Dans dichotomieExamineLesBonnesCases, donner les cases examinées pour \(x=40\) et pour \(x=50\) (valeurs de \(lo\), \(hi\) et \(mid\) à chaque tour).
  3. Expliquer. Pourquoi la dichotomie examine-t-elle 11 cases pour \(n=1\,024\) et 21 pour \(n=1\,048\,576\) ? Relier au plus petit nombre de cases qui garantit de conclure. Comparer la moyenne obtenue pour \(n=1\,500\) (valeur présente) à \(\log_2 1\,500\).
  4. Modifier. Remplacer provisoirement lo + (hi - lo) / 2 par (lo + hi) / 2. Les tests échouent-ils ? Pour quelles tailles de tableau les deux écritures diffèrent-elles, et que se passe-t-il alors ? Revenir au code correct.

Étape 4 : paires de somme nulle, deux algorithmes

Les tableaux de Paires contiennent des valeurs distinctes. compterNaif compte les paires d’indices \(i<j\) telles que a[i] + a[j] == 0 par deux boucles imbriquées, et incrémente comparaisons avant chaque test de somme nulle ; compterRapide trie une copie du tableau, puis cherche pour chaque case la valeur opposée par la dichotomie de l’étape 3.

  1. Observer. Les quatre tests de PairesTest doivent passer, et les quatorze tests du projet aussi (les treize fournis et le vôtre).
  2. Expliquer. Combien de paires d’indices compterNaif examine-t-elle pour un tableau de \(n\) cases ? Donner la classe \(\Theta\) de chaque méthode, en comptant le tri par Arrays.sort pour \(\Theta(n\log n)\).
  3. Expliquer. Pourquoi compterRapide travaille-t-elle sur une copie ? Quel test le vérifie ?
  4. Modifier. Remplacer provisoirement if (j > i) c++; par if (j != -1) c++;. Quels tests échouent, avec quelles valeurs ? Expliquer le facteur observé, et dire ce qui changerait si le tableau contenait la valeur 0. Revenir au code correct.

Étape 5 : l’expérience du doublement

Le mode doublement chronomètre les deux méthodes de Paires sur des tableaux de valeurs distinctes mélangées (graine fixe) : compterNaif de 2 000 à 32 000 cases, compterRapide de 64 000 à 2 048 000 cases. Chaque durée est une médiane de cinq exécutions (Chrono.mediane), après une chauffe ; le rapport est celui de la durée à la durée précédente.

  1. Observer. Lancer le mode doublement et recopier les deux tableaux.
  2. Expliquer. En déduire l’exposant \(b\) du modèle \(T(n)\approx a\,n^b\) pour chaque méthode. Les rapports de compterRapide sont-ils plus proches de 2 ou de \(2\cdot\log_2(2n)/\log_2 n\) ? Peut-on les distinguer avec ces mesures ?
  3. Expliquer. Prévoir la durée de compterNaif pour \(n=1\,024\,000\), d’après la dernière mesure et le modèle. Combien de fois compterRapide est-elle plus rapide à \(n=2\,048\,000\), d’après les deux modèles ?
  4. Modifier. Dans compterRapide, remplacer provisoirement Recherche.dichotomie par Recherche.sequentielle ; dans Main.doublement, ramener la seconde boucle à \(n=2\,000, \dots, 32\,000\) (for (int n = 2000; n <= 32000; n *= 2)) et la chauffe de w2 à 4 000 cases. Les tests passent-ils ? Relancer le mode doublement : que deviennent les rapports et les durées, et pourquoi ? Revenir au code correct.
  5. Expliquer. Relancer deux fois le mode doublement : quelles valeurs changent, et lesquelles ne changent pas ?

Étape 6 : compter au lieu de chronométrer

Le mode comparer ne chronomètre rien : pour des tableaux construits comme à l’étape 5, de \(n=2\,000\) à \(n=64\,000\), il affiche le nombre de tests de somme nulle de compterNaif (le compteur comparaisons) et le nombre de cases examinées par les \(n\) dichotomies de compterRapide (le compteur examinees), chacun suivi de son rapport au doublement, avec trois décimales.

  1. Expliquer. Avant de lancer le mode, prévoir le nombre de comparaisons de compterNaif pour \(n=2\,000\) et pour \(n=4\,000\), et leur rapport exact, puis comparer à la sortie de (b).

    \(n\) comparaisons prévues comparaisons affichées rapport
    2 000
    4 000

  2. Observer. Lancer le mode comparer et recopier la sortie. Le lancer une seconde fois : qu’est-ce qui change ?

  3. Expliquer. Les rapports de compterNaif ne sont pas exactement 4 pour les premières lignes. Pourquoi, et vers quoi tendent-ils ?

  4. Expliquer. Comparer les rapports des cases examinées à 2 et à \(2\log_2(2n)/\log_2 n\). Comment évoluent-ils quand \(n\) grandit ? Ces comptes distinguent-ils un coût en \(n\) d’un coût en \(n\log n\), là où les durées de l’étape 5 ne le pouvaient pas ?

  5. Expliquer. Que mesure un compte que ne mesure pas une durée, et inversement ? Citer un coût réel de compterRapide que le compteur examinees ne voit pas.

Étape 7 : retour à la file de la Séance 1

La Séance 1 a jugé mauvaise une file servie par supprimer(0) sur la liste sur tableau. Le mode file sert \(n\) clients, de \(n=12\,500\) à \(n=200\,000\), de deux façons : par remove(0) sur une ArrayList (méthode servirListe), puis par poll() sur une java.util.ArrayDeque, un tableau circulaire (méthode servirDeque). Chaque durée est une médiane de cinq exécutions, après une chauffe.

  1. Expliquer. Avant de lancer le mode, donner le nombre total d’éléments décalés par les \(n\) appels remove(0), la classe \(\Theta\) de chaque façon de servir, et le rapport attendu au doublement pour chacune.

    \(n\) éléments décalés par remove(0) rapport prévu rapport mesuré poll(), ms
    12 500 — —
    25 000
    200 000

  2. Observer. Lancer le mode file et recopier la sortie (compter quelques secondes pour la dernière ligne).

  3. Expliquer. Quels rapports de remove(0) confirment la prévision ? Pourquoi le premier s’en écarte-t-il ?

  4. Expliquer. Les durées de poll() permettent-elles de lire un rapport ? Que montrent-elles quand même ?

  5. Expliquer. Pour \(n=200\,000\), par combien la file sur tableau circulaire divise-t-elle la durée ? Ce facteur est-il fixe quand \(n\) double ? Conclure sur le jugement de la Séance 1.

Étape 8 : l’accès par rang, sans regarder le code

Le mode acces remplit une ArrayList et une LinkedList de \(n\) entiers, puis chronomètre \(n\) appels get(k), avec des rangs \(k\) tirés au hasard, de \(n=2\,500\) à \(n=40\,000\).

  1. Expliquer. Avant de lancer le mode, prévoir la classe \(\Theta\) du temps total de chaque liste, et le rapport attendu quand \(n\) double. La LinkedList d’OpenJDK atteint le rang \(k\) depuis l’extrémité la plus proche : combien de nœuds parcourt en moyenne un get(k) avec \(k\) uniforme ?
  2. Observer. Lancer le mode acces et recopier la sortie. La prévision est-elle confirmée ?
  3. Expliquer. Les durées de l’ArrayList ne croissent pas régulièrement avec \(n\). Pourquoi ne permettent-elles pas de lire un rapport ? Que faudrait-il changer pour les mesurer ?

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet