TP — Séance 1 — ADT et interfaces Java

Écrire, tester et mesurer un deque sur tableau circulaire en Java

TP de la séance 1 de Structures de données et algorithmes avancés : listes, piles, files et deques : un contrat, plusieurs réalisations.
Auteur

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

ImportantObjectif

Écrire le deque du cours sur un tableau circulaire redimensionnable (ArrayDeque<T>, contrat Deque<T>), le faire passer par les tests JUnit fournis, s’en servir comme pile pour évaluer des expressions postfixes et vérifier des parenthésages, puis mesurer le coût amorti du doublement et le coût caché d’une file sur ArrayList. 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 d’une à deux 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_S01_code_depart.zip, dans ~/dsa : le dossier TP_S01_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-s01
cd tp-s01
cp -r ../TP_S01_code_depart/. .
rm src/test/java/MainTest.java

Le code de départ contient six fichiers, cinq dans src/main/java/ et DequeTest.java 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-s01 : git init -b main et l’identité locale, comme à l’étape 7 du TP-1.

Fichier Rôle
Deque.java le contrat : addFirst, addLast, removeFirst, removeLast, peekFirst, peekLast, size, isEmpty ; fourni
ArrayDeque.java les champs donnees, tete, taille, les compteurs copies et agrandissements, size, isEmpty, capacite, indiceTete, etat fournis ; suivant, precedent (étape 1), les six opérations d’extrémité (étape 2) et agrandir (étape 3) à écrire
Postfixe.java evaluer à écrire à l’étape 5 ; estOperateur, appliquer fournis
Parentheses.java estEquilibree à écrire à l’étape 5 ; correspond fourni
Main.java programmes d’observation, fourni
DequeTest.java quatorze tests JUnit, fournis

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 observer, calculs ou mesures. Le nom ArrayDeque est celui de la classe du projet : aucun fichier n’importe java.util.ArrayDeque.

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

Étape 1 : les indices de l’anneau

Écrire suivant(i) et precedent(i) de ArrayDeque : l’indice qui suit et celui qui précède la case \(i\) sur un anneau de donnees.length cases.

  1. Expliquer. Que vaut (0 - 1) % 6 en Java ? Pourquoi precedent ajoute-t-il donnees.length avant de prendre le reste ? Pour quelles valeurs de \(i\) ce terme change-t-il le résultat ?
  2. Expliquer. suivant pourrait-il s’écrire i + 1 == donnees.length ? 0 : i + 1 ? Comparer avec le code de java.util.ArrayDeque (méthode inc).

Étape 2 : les six opérations d’extrémité

Écrire addFirst, addLast, removeFirst, removeLast, peekFirst et peekLast. Les ajouts appellent agrandir() quand le tableau est plein ; elle sera écrite à l’étape 3.

  1. Observer. Les tests ordreFileEtPile, reboucleParLaFin, reboucleParLaTete, peekNeModifiePas et videLeveUneException doivent passer.
  2. Expliquer. Quelle expression donne l’indice du dernier élément ? Dérouler le test reboucleParLaFin : les cases occupées après chaque boucle, et la case du dernier élément.
  3. Expliquer. Pourquoi removeFirst écrit-il null dans la case qu’il libère, alors que le contrat ne l’exige pas ?
  4. Modifier. Remplacer provisoirement le corps de precedent par return (i - 1) % donnees.length;. Quels tests échouent, avec quel message ? Que fait le mode observer ? Revenir au code correct.

Étape 3 : agrandir dans l’ordre logique

Écrire agrandir() : un tableau deux fois plus grand, où l’élément de rang \(k\) (case \((\texttt{tete}+k) \bmod m\)) est recopié en case \(k\), avec copies++ pour chaque case recopiée ; puis tete redevient 0 et agrandissements augmente.

  1. Observer. Les neuf tests qui ne portent ni sur Postfixe ni sur Parentheses doivent passer.
  2. Expliquer. Retrouver par le calcul les 8 agrandissements et les 2 040 copies attendus par copiesDuDoublement. Comparer à \(2n\).
  3. Expliquer. Dans agrandirApresRebouclage, donner les cases occupées et la valeur de tete juste avant addLast(11).
  4. Modifier. Remplacer provisoirement la boucle de recopie par System.arraycopy(donnees, 0, neuf, 0, taille); (et copies += taille;). Quels tests échouent, avec quelles valeurs ? Expliquer chacune. Revenir au code correct.

Étape 4 : observer les indices

Le mode observer crée un deque de 6 cases et affiche, après chaque opération, tete, la fin \((\texttt{tete}+\texttt{taille}) \bmod m\), taille, la capacité et les cases (. : case vide) : des clients arrivent à un guichet de transfert d’argent des Parcelles Assainies, par la fin ou, prioritaires, par le début.

  1. Observer. Lancer gradle --no-daemon run --args="observer" et recopier la sortie.
  2. Expliquer. Après le premier addFirst, que vaut tete, et pourquoi ? Relever une ligne où la fin est inférieure à tete : que signifie-t-elle ?
  3. Expliquer. À quelle opération la capacité change-t-elle ? Que vaut tete juste après, et dans quel ordre les clients sont-ils rangés ?
  4. Modifier. Ajouter à DequeTest deux tests : l’un alterne addFirst et addLast sur un deque vide puis vérifie l’ordre complet de sortie ; l’autre fait boucler la tête par addFirst, puis agrandit le tableau. Lesquels échouent avec la modification de l’étape 2 (d) ?

Étape 5 : une pile par restriction

Un deque restreint à addLast et removeLast est une pile : Postfixe et Parentheses n’utilisent que ces deux opérations. Écrire evaluer et estEquilibree en suivant les consignes.

  1. Observer. Les quatorze tests doivent passer. Lancer le mode calculs et recopier sa sortie.
  2. Expliquer. Dérouler à la main 2000 350 4 * - : la pile après chaque jeton. Que représente ce calcul, en FCFA, pour un billet de 2 000 et 4 articles à 350 ?
  3. Expliquer. Pour chacune des trois expressions rejetées du mode calculs, dire quelle instruction rend false.
  4. Modifier. Échanger provisoirement les deux removeLast() de evaluer. Quels tests échouent ? Quelles lignes du mode calculs changent, et pourquoi la deuxième ne change-t-elle pas ? Revenir au code correct.
  5. Modifier. Remplacer provisoirement le return pile.isEmpty(); final de estEquilibree par return true;. Quel test échoue, sur quelle expression ? Revenir au code correct.

Étape 6 : les coûts mesurés

Le mode mesures fait jusqu’à \(131\,073\) ajouts en fin dans un ArrayDeque de 8 cases et écrit, à six repères, les agrandissements, les copies, les copies par ajout et le plus grand nombre de copies d’un seul ajout (pire). Il sert ensuite \(n\) clients de deux façons, avec une java.util.ArrayList (add, puis remove(0)) et avec l’ArrayDeque du projet (addLast, puis removeFirst), et écrit les durées en millisecondes.

  1. Observer. Lancer le mode mesures et recopier les deux tableaux.
  2. Expliquer. Pourquoi le nombre de copies par ajout vaut-il presque 1 pour \(131\,072\) ajouts et presque 2 pour \(131\,073\) ? Montrer que les copies valent au plus \(2n-10\) pour \(n>8\) avec une capacité initiale de 8.
  3. Modifier. Remplacer provisoirement 2 * donnees.length par donnees.length + 16 dans agrandir. Quels tests échouent ? Relancer le mode mesures : comment les copies évoluent-elles quand \(n\) est multiplié par 50, puis par 1,31 ? Comparer à \(n^2/32\). Revenir au code correct.
  4. Expliquer. Dans le second tableau, comment évoluent les durées quand \(n\) double, pour chaque réalisation ? Relier remove(0) au décalage de la liste sur tableau du cours.
  5. Expliquer. Relancer deux fois le mode mesures : quelles colonnes changent, et pourquoi ?

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet