Cours BUT Info

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

Iris.java (première version)
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

VarietyLengthWidth
Setosa5.13.5
Setosa4.93.0
Setosa4.73.2
Versicolor7.03.2
Versicolor6.43.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.2

Ni 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 = 6

L'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.

Ce que fait add() dans un HashSet : hashCode() choisit le seau, puis equals() tranche entre les éléments qui s'y trouvent. Sans ces deux méthodes redéfinies, le doublon passe — c'est le bug corrigé en Q6 du TP 1.

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)
equals dit si deux objets ont la même valeur ; hashCode doit rester d'accord, sinon les collections (Set, Map) cherchent au mauvais endroit. C'est exactement le bug du TP 1 : le doublon est accepté.

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.2

Les 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.2

removeIf 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.

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 : 1

Q5 — 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 : 1

Constat : 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 : 2

Supprimer 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 : 2981

Trois 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.


tp1-collections.pdf

R3.02 · TP 1 — Utilisation des collections · 2 pages

Consultation seule — téléchargement désactivé

Chargement du document…

Dernière mise à jour le

Sur cette page