Choisir sa structure de données
Python propose quatre structures de base. Elles se ressemblent, mais le choix de l'une ou l'autre peut rendre un code mille fois plus rapide, ou éviter un bug invisible. Le jeu en donne deux exemples.
Le problème
Premier exemple. Pour trouver les voisins d'une case, le jeu parcourt toutes les cases :
Python
Sur une carte de 2 600 cases, on en examine 2 600 pour en trouver 6.
Second exemple. Après le chargement d'une sauvegarde, ce même code ne trouve plus aucun voisin, sans aucune erreur. La raison tient en une ligne :
Python
Les quatre structures
| Structure | Écriture | Ordonnée | Modifiable | Doublons | Usage type |
|---|---|---|---|---|---|
| Liste | [1, 2, 3] | oui | oui | oui | Une suite d'éléments qu'on parcourt |
| Tuple | (1, 2, 3) | oui | non | oui | Un petit groupe fixe : des coordonnées |
| Dictionnaire | {"a": 1} | oui | oui | clés uniques | Retrouver une valeur par sa clé |
| Ensemble | {1, 2, 3} | non | oui | non | Savoir si un élément est présent |
Liste ou tuple
Les deux rangent des éléments dans l'ordre. La différence : un tuple ne peut pas être modifié après sa création.
Python
Ça paraît être une limite. C'est une garantie : une coordonnée ne changera pas par accident. Et surtout, seul ce qui ne change pas peut servir de clé de dictionnaire ou d'élément d'ensemble.
Python
| Utiliser | Quand |
|---|---|
| Tuple | Le nombre d'éléments est fixe et chacun a un sens : (colonne, ligne), (rouge, vert, bleu) |
| Liste | On ajoute, retire, trie : les cases, les unités d'un joueur |
Le piège du JSON
Le format JSON ne connaît pas les tuples. Tout devient liste :
Python
C'est exactement ce qui arrive aux coordonnées dans les sauvegardes du jeu. Il faut reconvertir à la lecture :
Python
Le jeu le fait déjà à certains endroits, par exemple dans Player., mais pas dans Map..
Le dictionnaire : retrouver sans chercher
Un dictionnaire associe une clé à une valeur. Sa force : trouver une valeur par sa clé prend le même temps, qu'il y ait dix éléments ou dix millions.
Pour le jeu :
Python
Six recherches directes, au lieu de 2 600 comparaisons.
| Carte | Avec la liste | Avec le dictionnaire |
|---|---|---|
| 127 cases | 127 cases examinées | 6 recherches |
| 2 611 cases | 2 611 cases examinées | 6 recherches |
Le cours La complexité donne un nom à cette différence.
Lire un dictionnaire sans planter
| Écriture | Si la clé manque |
|---|---|
d[key] | Erreur KeyError |
d.get(key) | Renvoie None |
d. | Renvoie la valeur par défaut |
key in d | Répond True ou False |
Le projet écrit parfois in d.keys(). in d fait la même chose, en plus court.
L'ensemble : savoir si c'est dedans
Un ensemble ne garde chaque élément qu'une fois et répond très vite à la question « est-ce présent ? ».
Le jeu s'en sert bien pour le brouillard de guerre :
Python
Les ensembles savent aussi se combiner. Map.layers l'utilise pour construire les anneaux de la carte :
Python
neighbors - donne les voisins qui ne sont pas déjà dans la carte.
| Opération | Écriture | Résultat |
|---|---|---|
| Union | a.union(b) | Tout ce qui est dans l'un ou l'autre |
| Intersection | a & b | Ce qui est dans les deux |
| Différence | a - b | Ce qui est dans a mais pas dans b |
in : le même mot, quatre vitesses
Python
Type de collection | Ce que fait Python | Coût |
|---|---|---|
| Liste, tuple | Compare avec chaque élément | Proportionnel à la taille |
| Dictionnaire, ensemble | Calcule l'emplacement | Constant |
C'est le point à retenir de ce cours. Dans Player. :
Python
Pour chaque case de la carte, on parcourt la liste des cases possédées. Deux boucles imbriquées, cachées derrière un in.
Des structures qui disent ce qu'elles contiennent
Le jeu sauvegarde une unité sous forme de tuple :
Python
Et la relit par position :
Python
Ajouter un champ au milieu décale tout. Un dictionnaire, ou une dataclass, nomme chaque valeur :
Python
Aide-mémoire
À retenir
- Coordonnées : toujours des tuples. Reconvertir après un JSON.
- Retrouver par identifiant : un dictionnaire.
- Tester la présence : un ensemble.
insur une liste est une boucle cachée.
Exercices
- Dans un interpréteur Python, vérifier que
[3, 4] in [(3, 4)]vautFalse. - Corriger
Map.pour que les coordonnées soient des tuples. Charger une partie et déplacer une unité.load_ from_ save - Ajouter
tiles_by_cooàMapet réécrirereturn_.neighbors_ tiles - Dans
Player., transformerupdate_ map_ tiles_ owner total_en ensemble. Pourquoi faut-il quetiles_ owned Tilesoit utilisable dans un ensemble, et est-ce le cas ?