Résoudre le même besoin avec plusieurs structures et prouver les conséquences.
Scénario
HashBox doit gérer un annuaire de 50 000 membres. Les opérations : ajouter, retrouver par identifiant, lister dans l'ordre alphabétique, supprimer. L'équipe hésite entre une liste, un dictionnaire et un arbre de recherche.
Objectif
Implémenter le même annuaire avec trois structures différentes, vérifier qu'elles se comportent identiquement, puis mesurer lesquelles gagnent sur chaque opération.
Environnement
Python 3.10 ou plus. Éditeur et terminal. Pas de bibliothèque externe.
État de départ
Un fichier annuaire.py vide. Une interface à respecter : ajouter(id, nom), trouver(id), supprimer(id), lister() (trié par nom).
Tâches
- Écris l'interface (contrat de chaque opération, cas limites).
- Implémente
AnnuaireListe(liste de couples). - Implémente
AnnuaireDict(dictionnaire id → nom). - Implémente
AnnuaireBST(arbre de recherche trié par nom). - Écris une suite de tests commune aux trois, dont un test aléatoire de 500 séquences d'opérations.
- Mesure chaque opération avec 1 000, 10 000 et 50 000 membres.
- Rédige un tableau comparatif et une recommandation argumentée.
Observations attendues
- Les trois implémentations réussissent les mêmes tests.
trouverest nettement plus rapide avec le dictionnaire sur de grandes tailles.listertrié est immédiat avec le BST (parcours en ordre) mais demande un tri avec les autres.- Insérer dans l'ordre alphabétique rend le BST très lent : tu le constates et l'expliques.
Validation
Les tests passent sur les trois classes. Les mesures sont reproductibles : les ordres de grandeur sont identiques d'une exécution à l'autre.
Indices
💡 Indice 1
Fais d'abord marcher la liste, elle sert de référence.
💡 Indice 2
Pour le BST, trie le résultat de la liste pour vérifier lister().
💡 Indice 3
Mélange les noms avec random.shuffle avant l'insertion dans le BST.
Preuves à rendre
-
annuaire.pyavec les trois classes et leurs contrats - Tests, dont le test aléatoire
- Tableau des temps et recommandation (10 lignes)
Réflexion
- Quelle opération a décidé de ton choix final ?
- Quelle hypothèse sur l'usage réel pourrait inverser ta recommandation ?
HEF-020 — Structures de données
Atelier Python

