La magie du dictionnaire : trouver en un clin d'oeil#
En Python, accéder a arbre["espece"] est quasi instantané, même si le dictionnaire contient un million d'entrées. Chercher une valeur dans une liste, en revanche, oblige a parcourir les éléments un par un jusqu'a trouver. Pourquoi cette différence radicale ?
La table de hachage
Un dictionnaire Python est une table de hachage. L'idée : une fonction de hachage transforme la clé (par exemple la chaine "espece") en un numéro de casier. On va directement au bon casier - pas de recherche, pas de parcours.
Imagine une bibliothèque magique ou une formule te donne immédiatement le numéro d'étagère d'un livre, sans avoir a en lire un seul autre. C'est exactement ce qui se passe :
cle = "espece" numeroCasier = fonctionDeHachage(cle) # ex. 47231 casiers[numeroCasier] = "Érable a sucre" # Plus tard, pour retrouver : valeur = casiers[fonctionDeHachage("espece")] # direct, un seul saut| Structure | Cout de recherche | Signification |
|---|---|---|
dict (table de hachage) |
O(1) | Temps constant - indépendant de la taille |
list (parcours) |
O(n) | Proportionnel au nombre d'éléments |
Pour qu'une clé puisse etre hachée, elle doit etre immuable : les textes, les nombres et les tuples sont hachables. Une liste ne l'est pas, car elle peut changer apres avoir été utilisée comme clé.
Démo - Liste vs Dictionnaire
Cherche une espece dans les données. Observe combien de comparaisons la liste a fait, et combien en a fait le dictionnaire.
Especes disponibles :
Une grille qui prend vie : le Jeu de la vie#
En 1970, le mathématicien britannique John Conway invente un objet fascinant : un automate cellulaire. Sur un tableau 2D de cellules vivantes ou mortes, quatre règles simples suffisent a faire émerger des comportements d'une richesse stupéfiante - glisseurs, oscillateurs, vaisseaux spatiaux.
Les règles exactes
A chaque génération, on compte les 8 voisines de chaque cellule (haut, bas, gauche, droite, et les 4 diagonales) :
- Une cellule vivante avec 2 ou 3 voisines vivantes survit.
- Une cellule vivante avec moins de 2 voisines vivantes meurt (solitude).
- Une cellule vivante avec plus de 3 voisines vivantes meurt (surpopulation).
- Une cellule morte avec exactement 3 voisines vivantes nait (reproduction).
Lien avec la Mission Forêt : imagine chaque cellule comme un arbre dans une foret. Trop dense, ca brule ou s'étouffe. Trop clairsemé, ca meurt. La survie tient a l'équilibre du voisinage - exactement comme un vrai écosystème.
Les tableaux 2D servent aussi aux images (une grille de pixels) et aux jeux de plateau (échecs, mots croisés, labyrinthe) - meme structure, usages infinis.
Démo - Jeu de la vie de Conway
Clique sur une cellule pour la faire vivre ou mourir. Démarre pour voir l'évolution.
Les structures de données sont partout#
JSON : le dictionnaire du Web
JSON (JavaScript Object Notation, popularisé par Douglas Crockford au début des années 2000) est devenu le format universel d'échange de données sur Internet. Chaque fois que ton téléphone reçoit des données d'une application, c'est probablement du JSON. Et sa forme ? Exactement un dictionnaire Python :
Les API météo, les données satellites, les résultats de recherche Google - tout transite sous cette forme. Savoir lire et produire du JSON, c'est avoir la clé du Web.
Le cours de programmation t'a donné les outils de base. Ces trois exemples montrent que les memes structures - listes, dictionnaires, tableaux 2D - reviennent partout, habillées différemment. Maitriser les structures, c'est maitriser la matière premiere de l'informatique.