TP 1 — Utilisation des collections
Le TP d'ouverture de R3.02 : des iris dans un Set (et le piège equals/hashCode observé en direct), les Streams en une ligne, le TreeSet, puis un compteur de mots sur Notre-Dame de Paris.
Ce TP est le passage à la pratique du chapitre 1, en deux
parties : d'abord la classe Iris manipulée dans un Set — où un doublon refuse de
disparaître tant qu'equals et hashCode ne sont pas redéfinis — puis un compteur de mots
sur le vrai texte de Notre-Dame de Paris.
Tout ce qui suit a été écrit, compilé et exécuté : les sorties affichées sont de vraies traces d'exécution. Le corpus utilisé à la partie 2 est téléchargeable en bas de page.
Comment utiliser cette page
Suivez l'ordre du TP : le bug de la question 5 (un doublon accepté par un Set) n'a d'intérêt que si on l'observe d'abord, avant de le corriger. Les numéros de question sont ceux du sujet.
Partie 1 — des iris dans un Set
Q1 — la classe Iris
public class Iris {
private String variety;
private Double length;
private Double width;
public Iris(String variety, Double length, Double width) {
this.variety = variety;
this.length = length;
this.width = width;
}
public void affiche() {
System.out.println(this);
}
@Override
public String toString() {
return variety + " " + length + " " + width;
}
}Un toString en plus de affiche() : il rend l'objet affichable partout (dont dans un
println), et sert au débogage.
Q2 — les 5 iris du sujet
| Variety | Length | Width |
|---|---|---|
| Setosa | 5.1 | 3.5 |
| Setosa | 4.9 | 3.0 |
| Setosa | 4.7 | 3.2 |
| Versicolor | 7.0 | 3.2 |
| Versicolor | 6.4 | 3.2 |
Iris i1 = new Iris("Setosa", 5.1, 3.5);
Iris i2 = new Iris("Setosa", 4.9, 3.0);
Iris i3 = new Iris("Setosa", 4.7, 3.2);
Iris i4 = new Iris("Versicolor", 7.0, 3.2);
Iris i5 = new Iris("Versicolor", 6.4, 3.2);Q3 — une Collection… un HashSet
Set<Iris> fleurs = new HashSet<>();
fleurs.add(i1);
fleurs.add(i2);
fleurs.add(i3);
fleurs.add(i4);
fleurs.add(i5);Q4 — comment sont ordonnés les éléments ?
Affichage réel de la collection :
Setosa 4.9 3.0
Setosa 5.1 3.5
Versicolor 7.0 3.2
Setosa 4.7 3.2
Versicolor 6.4 3.2Ni l'ordre d'insertion, ni l'ordre alphabétique : un HashSet range les éléments selon leur
hashCode (ici, celui d'identité — l'adresse mémoire), donc l'ordre est arbitraire et peut
changer d'une exécution à l'autre. C'est le prix de la rapidité d'insertion et de recherche.
Q5 — le doublon… accepté ?
Iris doublon = new Iris("Versicolor", 6.4, 3.2); // mêmes caractéristiques que i5
boolean ajoute = fleurs.add(doublon);— après ajout du « doublon » (accepté : true) —
Setosa 4.9 3.0
Versicolor 6.4 3.2
Setosa 5.1 3.5
Versicolor 7.0 3.2
Setosa 4.7 3.2
Versicolor 6.4 3.2
taille = 6L'ajout est accepté (true) et la collection contient deux fois « Versicolor 6.4 3.2 ». Ce
n'est pas normal pour un ensemble : mais pour le HashSet, doublon et i5 sont deux
objets sans rapport — sans equals ni hashCode redéfinis, la comparaison se fait sur les
références, qui diffèrent.
Q6 — corriger : equals et hashCode
La correction consiste à redéfinir les deux méthodes ensemble (le contrat du chapitre 1) :
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Iris)) return false;
Iris iris = (Iris) o;
return Objects.equals(variety, iris.variety)
&& Objects.equals(length, iris.length)
&& Objects.equals(width, iris.width);
}
@Override
public int hashCode() {
return Objects.hash(variety, length, width);
}En relançant le même main :
ajout du doublon accepté ? false (taille = 5)Q7 — les Streams, une ligne chacun
Les quatre opérations demandées, sans parcours explicite :
// les fleurs de longueur supérieure à 5
fleurs.stream().filter(f -> f.getLength() > 5).forEach(System.out::println);
// la collection triée par ordre décroissant de longueur
fleurs.stream()
.sorted(Comparator.comparingDouble(Iris::getLength).reversed())
.forEach(System.out::println);
// la moyenne de la largeur des fleurs
System.out.println(fleurs.stream().mapToDouble(Iris::getWidth).average().orElse(0.0));
// une liste contenant le triple des longueurs
List<Double> triples = fleurs.stream().map(f -> f.getLength() * 3).collect(Collectors.toList());
System.out.println(triples);— les fleurs de longueur > 5 —
Versicolor 6.4 3.2
Setosa 5.1 3.5
Versicolor 7.0 3.2
— triées par longueur décroissante —
Versicolor 7.0 3.2
Versicolor 6.4 3.2
Setosa 5.1 3.5
Setosa 4.9 3.0
Setosa 4.7 3.2
— largeur moyenne —
3.22
— le triple des longueurs —
[14.100000000000001, 19.200000000000003, 14.700000000000001, 15.299999999999999, 21.0]System.out::println et les doubles
System.out::println est une référence de méthode : le raccourci de
f -> System.out.println(f). Et sur le triple des longueurs, la sortie révèle l'arithmétique
binaire des double : 4.7 * 3 vaut 14.100000000000001. C'est normal — pour afficher
proprement, on formate (String.format("%.1f", v)) au lieu d'imprimer la valeur brute.
Q8 — passer à un TreeSet
Pour qu'un TreeSet sache ordonner les iris, la classe doit implémenter Comparable<Iris> :
il faut définir l'ordre naturel, par exemple variété, puis longueur, puis largeur.
public class Iris implements Comparable<Iris> {
// ... le reste est inchangé
@Override
public int compareTo(Iris autre) {
int parVariete = variety.compareTo(autre.variety);
if (parVariete != 0) return parVariete;
int parLongueur = length.compareTo(autre.length);
if (parLongueur != 0) return parLongueur;
return width.compareTo(autre.width);
}
}Puis dans le main : Set<Iris> arbre = new TreeSet<>(fleurs);
— le TreeSet —
Setosa 4.7 3.2
Setosa 4.9 3.0
Setosa 5.1 3.5
Versicolor 6.4 3.2
Versicolor 7.0 3.2Les différences : un HashSet est très efficace mais ne promet aucun ordre ; un TreeSet
trie ses éléments selon compareTo (les Setosa groupés, longueurs croissantes), au prix
d'insertions et de recherches plus coûteuses. Les arbres arriveront au cours 5.
Dans un TreeSet, c'est compareTo qui tranche
Pour décider qu'un élément est « déjà présent », un TreeSet se fie à compareTo : un
retour 0 signifie « identique ». C'est une autre raison de garder compareTo cohérent
avec equals — en comparant variété, longueur et largeur, les deux disent la même chose.
Q9 — retirer les Setosa
fleurs.removeIf(f -> f.getVariety().equals("Setosa"));— après retrait des Setosa (taille = 2) —
Versicolor 6.4 3.2
Versicolor 7.0 3.2removeIf supprime proprement pendant le parcours interne. La version classique — un itérateur
dont on appelle it.remove() — est équivalente ; en revanche, un fleurs.remove(...) pendant
un foreach provoquerait l'interdiction de modification en cours de parcours (chapitre 1).
À retenir (la conclusion du sujet)
Quand on utilise une Collection d'objets que l'on crée, le bon fonctionnement de add,
remove et contains dépend de la redéfinition d'equals et hashCode. Et certaines
implémentations exigent en plus des objets Comparable — c'était le cas du TreeSet.
import java.util.Objects;
/**
* Version finale de la classe Iris : equals et hashCode redéfinis (Q6),
* et Comparable implémentée (Q8, pour que le TreeSet sache ordonner).
*/
public class Iris implements Comparable<Iris> {
private String variety;
private Double length;
private Double width;
public Iris(String variety, Double length, Double width) {
this.variety = variety;
this.length = length;
this.width = width;
}
public String getVariety() { return variety; }
public Double getLength() { return length; }
public Double getWidth() { return width; }
public void affiche() {
System.out.println(this);
}
@Override
public String toString() {
return variety + " " + length + " " + width;
}
// Q6 — deux iris sont égaux s'ils ont la même variété, la même longueur
// et la même largeur.
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Iris)) return false;
Iris iris = (Iris) o;
return Objects.equals(variety, iris.variety)
&& Objects.equals(length, iris.length)
&& Objects.equals(width, iris.width);
}
// Q6 — indispensable pour que hashCode reste cohérent avec equals
// (a.equals(b) => a.hashCode() == b.hashCode()).
@Override
public int hashCode() {
return Objects.hash(variety, length, width);
}
// Q8 — l'ordre naturel : variété, puis longueur, puis largeur.
@Override
public int compareTo(Iris autre) {
int parVariete = variety.compareTo(autre.variety);
if (parVariete != 0) return parVariete;
int parLongueur = length.compareTo(autre.length);
if (parLongueur != 0) return parLongueur;
return width.compareTo(autre.width);
}
}import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import java.util.stream.Collectors;
/** Le main complet : Q4 à Q9 avec la classe Iris corrigée. */
public class UseIris {
public static void main(String[] args) {
// Q2 — les 5 iris du sujet
Iris i1 = new Iris("Setosa", 5.1, 3.5);
Iris i2 = new Iris("Setosa", 4.9, 3.0);
Iris i3 = new Iris("Setosa", 4.7, 3.2);
Iris i4 = new Iris("Versicolor", 7.0, 3.2);
Iris i5 = new Iris("Versicolor", 6.4, 3.2);
// Q3 — un HashSet
Set<Iris> fleurs = new HashSet<>();
fleurs.add(i1);
fleurs.add(i2);
fleurs.add(i3);
fleurs.add(i4);
fleurs.add(i5);
// Q4 — affichage
System.out.println("— la collection —");
for (Iris fleur : fleurs) {
fleur.affiche();
}
// Q5/Q6 — le doublon est maintenant refusé
Iris doublon = new Iris("Versicolor", 6.4, 3.2);
boolean ajoute = fleurs.add(doublon);
System.out.println("ajout du doublon accepté ? " + ajoute + " (taille = " + fleurs.size() + ")");
// Q7 — quatre opérations en une ligne chacune
System.out.println("— les fleurs de longueur > 5 —");
fleurs.stream().filter(f -> f.getLength() > 5).forEach(System.out::println);
System.out.println("— triées par longueur décroissante —");
fleurs.stream().sorted(Comparator.comparingDouble(Iris::getLength).reversed()).forEach(System.out::println);
System.out.println("— largeur moyenne —");
System.out.println(fleurs.stream().mapToDouble(Iris::getWidth).average().orElse(0.0));
System.out.println("— le triple des longueurs —");
List<Double> triples = fleurs.stream().map(f -> f.getLength() * 3).collect(Collectors.toList());
System.out.println(triples);
// Q8 — un TreeSet ordonne selon compareTo
System.out.println("— le TreeSet —");
Set<Iris> arbre = new TreeSet<>(fleurs);
for (Iris fleur : arbre) {
fleur.affiche();
}
// Q9 — retrait des Setosa
fleurs.removeIf(f -> f.getVariety().equals("Setosa"));
System.out.println("— après retrait des Setosa (taille = " + fleurs.size() + ") —");
for (Iris fleur : fleurs) {
fleur.affiche();
}
}
}Partie 2 — compter les mots d'un texte
Q1 — la classe Compte
Le dictionnaire associe à chaque mot son nombre d'occurrences :
- la clé est un
String(le mot) ; - la valeur est un
Integer(la fréquence) ; - première implémentation : une
HashMap.
public class Compte {
private Map<String, Integer> occurrences = new HashMap<>();
}Q2 — compter les mots d'une phrase
public void compter(String phrase) {
for (String mot : phrase.split("\\s+")) {
occurrences.merge(mot, 1, Integer::sum);
}
}merge, ou la version à la main
merge(mot, 1, Integer::sum) signifie : si le mot est absent, lui mettre 1 ; sinon, le
remplacer par ancienne valeur + 1. La version manuelle, plus proche de get/put du cours,
est équivalente : Integer n = occurrences.get(mot); occurrences.put(mot, n == null ? 1 : n + 1); — le null signale le mot jamais vu.
Q3 — le toString par parcours de la Map
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (Map.Entry<String, Integer> couple : occurrences.entrySet()) {
sb.append(couple.getKey()).append(" : ").append(couple.getValue()).append('\n');
}
return sb.toString();
}Q4 — tester la phrase du sujet
Compte compte = new Compte();
compte.compter("Un chasseur sachant chasser doit savoir chasser sans son chien");
System.out.println(compte);sachant : 1
son : 1
chasser : 2
sans : 1
doit : 1
Un : 1
chasseur : 1
savoir : 1
chien : 1Q5 — remplacer par une TreeMap
Une seule ligne change : new TreeMap<>() au lieu de new HashMap<>().
Un : 1
chasser : 2
chasseur : 1
chien : 1
doit : 1
sachant : 1
sans : 1
savoir : 1
son : 1Constat : l'affichage est devenu alphabétique — la TreeMap trie selon les clés,
là où la HashMap rangeait selon les hachages. Détail savoureux : Un passe en tête car, en
ordre Unicode, les majuscules précèdent les minuscules.
Q6 — retirer les mots vus une seule fois
public void retirerOccurrencesUniques() {
Iterator<Map.Entry<String, Integer>> it = occurrences.entrySet().iterator();
while (it.hasNext()) {
if (it.next().getValue() <= 1) {
it.remove();
}
}
}— après retrait des mots vus une seule fois —
chasser : 2Supprimer pendant le parcours
Un occurrences.remove(mot) pendant le parcours de la Map lèverait une
ConcurrentModificationException — même règle qu'au chapitre 1. it.remove() est la
suppression propre ; l'écriture moderne équivalente est
occurrences.entrySet().removeIf(couple -> couple.getValue() <= 1);.
Q7 — le fichier Notre-Dame de Paris
public void compterFichier(String chemin) throws IOException {
occurrences.clear(); // « pensez à vider votre Map au préalable ! »
for (String ligne : Files.readAllLines(Path.of(chemin), StandardCharsets.UTF_8)) {
for (String mot : ligne.split("\\s+")) {
if (!mot.isEmpty()) {
occurrences.merge(mot, 1, Integer::sum);
}
}
}
}Sur le vrai fichier (environ 4 200 lignes lues en UTF-8, comptage en une fraction de seconde) :
brut : 28892 mots distincts, en 71 ms
de : 8080
la : 4908
et : 4261
le : 3607
à : 3118Évidemment, avec un découpage sur les espaces, « de » et « de, » et « de. » sont trois mots différents — c'est ce que la question 8 propose d'améliorer.
Q8 — les cinq mots les plus courants, puis l'amélioration
public void afficherPlusFrequents(int n) {
occurrences.entrySet().stream()
.sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
.limit(n)
.forEach(couple -> System.out.println(couple.getKey() + " : " + couple.getValue()));
}Amélioration de la sélection des mots : minuscules, apostrophes et ponctuation traitées comme séparateurs, et seuls les mots d'au moins deux lettres sont gardés.
static List<String> decouperProprement(String ligne) {
String[] bruts = ligne.toLowerCase()
.replaceAll("[’']", " ") // les apostrophes séparent
.replaceAll("[^a-zàâäçéèêëîïôöùûüœæ]", " ") // le reste → des espaces
.split("\\s+");
return Stream.of(bruts).filter(mot -> mot.length() > 1).collect(Collectors.toList());
}Nouveau classement, sur le même texte :
nettoyé : 16379 mots distincts
de : 8262
la : 5397
et : 4585
le : 4125
il : 2981Trois effets visibles :
- « de », « la »… grimpent : toutes les formes collées à une ponctuation (« de, », « de. ») fusionnent enfin ;
- « à » sort du top 5 : c'est un mot d'une lettre, filtré par la longueur > 1 ;
- « il » entre dans le classement — sur un texte brut, ce sont les petits mots grammaticaux qui dominent, quelle que soit la beauté du roman.
La découpe, c'est un vrai sujet
Changer la façon de découper (les « tokens ») change complètement le classement : c'est l'étape de tokenisation, et elle mérite toute l'attention dans un programme d'analyse de texte.
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.Stream;
/**
* Le « compteur de mots » du TP 1 (partie 2) : une Map mot -> nombre
* d'occurrences. Q1 : le type de la clé (String) et de la valeur (Integer).
*/
public class Compte {
// Q1/Q2 — le dictionnaire d'occurrences, une HashMap pour commencer
private Map<String, Integer> occurrences = new HashMap<>();
// Q2 — compter les mots d'une phrase (et cumuler si le mot est déjà là)
public void compter(String phrase) {
for (String mot : phrase.split("\\s+")) {
if (!mot.isEmpty()) {
occurrences.merge(mot, 1, Integer::sum);
}
}
}
// Q7 — compter les mots d'un fichier : on vide d'abord, puis ligne par ligne
public void compterFichier(String chemin) throws IOException {
occurrences.clear();
for (String ligne : Files.readAllLines(Path.of(chemin), StandardCharsets.UTF_8)) {
for (String mot : ligne.split("\\s+")) {
if (!mot.isEmpty()) {
occurrences.merge(mot, 1, Integer::sum);
}
}
}
}
// Q8 (amélioration) — découpage nettoyé : minuscules, apostrophes et
// ponctuation comme séparateurs, et on ne garde que les mots d'au moins
// deux lettres.
static List<String> decouperProprement(String ligne) {
String[] bruts = ligne.toLowerCase()
.replaceAll("[’']", " ")
.replaceAll("[^a-zàâäçéèêëîïôöùûüœæ]", " ")
.split("\\s+");
return Stream.of(bruts).filter(mot -> mot.length() > 1).collect(Collectors.toList());
}
public void compterFichierPropre(String chemin) throws IOException {
occurrences.clear();
for (String ligne : Files.readAllLines(Path.of(chemin), StandardCharsets.UTF_8)) {
for (String mot : decouperProprement(ligne)) {
occurrences.merge(mot, 1, Integer::sum);
}
}
}
// Q3 — l'affichage : on parcourt la Map avec entrySet()
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (Map.Entry<String, Integer> couple : occurrences.entrySet()) {
sb.append(couple.getKey()).append(" : ").append(couple.getValue()).append('\n');
}
return sb.toString();
}
// Q6 — retirer les mots vus une seule fois (it.remove retire proprement)
public void retirerOccurrencesUniques() {
Iterator<Map.Entry<String, Integer>> it = occurrences.entrySet().iterator();
while (it.hasNext()) {
if (it.next().getValue() <= 1) {
it.remove();
}
}
}
// Q8 — les n mots les plus fréquents, du plus fréquent au moins fréquent
public void afficherPlusFrequents(int n) {
occurrences.entrySet().stream()
.sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
.limit(n)
.forEach(couple -> System.out.println(couple.getKey() + " : " + couple.getValue()));
}
public int taille() {
return occurrences.size();
}
}/** Q4 à Q6 sur la phrase du sujet (et l'observation de l'ordre de la Map). */
public class TestPhrase {
public static void main(String[] args) {
Compte compte = new Compte();
// Q4 — la phrase du sujet
compte.compter("Un chasseur sachant chasser doit savoir chasser sans son chien");
System.out.println("— la Map telle quelle —");
System.out.println(compte);
// Q6 — on retire les mots vus une seule fois
compte.retirerOccurrencesUniques();
System.out.println("— après retrait des mots vus une seule fois —");
System.out.println(compte);
}
}/** Q7 et Q8 sur le vrai texte : Notre-Dame de Paris. */
public class TestRoman {
public static void main(String[] args) throws Exception {
String chemin = args[0];
// Q7 — comptage brut (découpage sur les espaces)
Compte brut = new Compte();
long debut = System.currentTimeMillis();
brut.compterFichier(chemin);
long duree = System.currentTimeMillis() - debut;
System.out.println("brut : " + brut.taille() + " mots distincts, en " + duree + " ms");
brut.afficherPlusFrequents(5);
// Q8 — comptage nettoyé (minuscules, ponctuation, longueur > 1)
Compte propre = new Compte();
propre.compterFichierPropre(chemin);
System.out.println("nettoyé : " + propre.taille() + " mots distincts");
propre.afficherPlusFrequents(5);
}
}tp1-collections.pdf
R3.02 · TP 1 — Utilisation des collections · 2 pages
Chargement du document…
Dernière mise à jour le
TD 2 — Piles et files
Trois exercices — la pile sur tableau, la file circulaire, et la vérification des délimiteurs — corrigés, compilés et testés, avec les traces d'exécution.
TP 2 — Le labyrinthe
Sortir d'un labyrinthe en explorant ses cases : parcours en profondeur avec une pile, puis en largeur avec une file — corrigés testés, pièges et observations.