Aller au contenu

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
def return_neighbors_tiles(self, tile): neighbors = [] possible_neighbors = self.find_neighbors(tile.coo) for tile in self.tiles: if tile.coo in possible_neighbors: neighbors.append(tile) return neighbors

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
>>> [3, 4] == (3, 4) False

Les quatre structures

StructureÉcritureOrdonnéeModifiableDoublonsUsage type
Liste[1, 2, 3]ouiouiouiUne suite d'éléments qu'on parcourt
Tuple(1, 2, 3)ouinonouiUn petit groupe fixe : des coordonnées
Dictionnaire{"a": 1}ouiouiclés uniquesRetrouver une valeur par sa clé
Ensemble{1, 2, 3}nonouinonSavoir 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
coo = (3, 4) coo[0] = 5 # TypeError

Ç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
tiles_by_coo = {} tiles_by_coo[(3, 4)] = tile # fonctionne tiles_by_coo[[3, 4]] = tile # TypeError: unhashable type: 'list'
UtiliserQuand
TupleLe nombre d'éléments est fixe et chacun a un sens : (colonne, ligne), (rouge, vert, bleu)
ListeOn 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
>>> import json >>> json.loads(json.dumps((3, 4))) [3, 4]

C'est exactement ce qui arrive aux coordonnées dans les sauvegardes du jeu. Il faut reconvertir à la lecture :

Python
coo = tuple(data["coo"])

Le jeu le fait déjà à certains endroits, par exemple dans Player.load_tiles_owned, mais pas dans Map.load_from_save.

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
self.tiles_by_coo = {tile.coo: tile for tile in self.tiles} def return_neighbors_tiles(self, tile): return [ self.tiles_by_coo[c] for c in self.find_neighbors(tile.coo) if c in self.tiles_by_coo ]

Six recherches directes, au lieu de 2 600 comparaisons.

CarteAvec la listeAvec le dictionnaire
127 cases127 cases examinées6 recherches
2 611 cases2 611 cases examinées6 recherches

Le cours La complexité donne un nom à cette différence.

Lire un dictionnaire sans planter

ÉcritureSi la clé manque
d[key]Erreur KeyError
d.get(key)Renvoie None
d.get(key, 0)Renvoie la valeur par défaut
key in dRé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
self.tiles_seen_coos = set() self.tiles_seen_coos.add((3, 4)) if (3, 4) in self.tiles_seen_coos: ...

Les ensembles savent aussi se combiner. Map.layers l'utilise pour construire les anneaux de la carte :

Python
coo_list[-1].update(neighbors - total_tiles)

neighbors - total_tiles donne les voisins qui ne sont pas déjà dans la carte.

OpérationÉcritureRésultat
Uniona.union(b)Tout ce qui est dans l'un ou l'autre
Intersectiona & bCe qui est dans les deux
Différencea - bCe qui est dans a mais pas dans b

in : le même mot, quatre vitesses

Python
if x in collection:
Type de collectionCe que fait PythonCoût
Liste, tupleCompare avec chaque élémentProportionnel à la taille
Dictionnaire, ensembleCalcule l'emplacementConstant

C'est le point à retenir de ce cours. Dans Player.update_map_tiles_owner :

Python
for tile in self.game.map.tiles: if tile in total_tiles_owned: # total_tiles_owned est une liste tile.owner = self.id

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
return (self.name, self.tile_linked.coo, self.current_hp, self.current_movement)

Et la relit par position :

Python
unit.current_hp = unit_data[2] unit.current_movement = unit_data[3]

Ajouter un champ au milieu décale tout. Un dictionnaire, ou une dataclass, nomme chaque valeur :

Python
return {"name": self.name, "coo": self.tile_linked.coo, "hp": self.current_hp} ... unit.current_hp = unit_data["hp"]

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.
  • in sur une liste est une boucle cachée.

Exercices

  1. Dans un interpréteur Python, vérifier que [3, 4] in [(3, 4)] vaut False.
  2. Corriger Map.load_from_save pour que les coordonnées soient des tuples. Charger une partie et déplacer une unité.
  3. Ajouter tiles_by_coo à Map et réécrire return_neighbors_tiles.
  4. Dans Player.update_map_tiles_owner, transformer total_tiles_owned en ensemble. Pourquoi faut-il que Tile soit utilisable dans un ensemble, et est-ce le cas ?