# 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 | É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
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'
```

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

<Mermaid
  chart={`flowchart LR
    subgraph liste [Dans une liste]
      direction LR
      l1[case 0] --> l2[case 1] --> l3[case 2] --> l4[...] --> l5[case 2599]
    end
    subgraph dico [Dans un dictionnaire]
      direction LR
      k["clé (3, 4)"] --> h[calcul direct de l'emplacement] --> v[la case]
    end`}
/>

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.

| 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é](/algorithmes/complexite) 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.get(key, 0)` | 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
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 | É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
if x in collection:
```

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

<Mermaid
  chart={`flowchart TB
    q1{Je veux retrouver un élément<br/>par un identifiant ?}
    q1 -- oui --> dict[Dictionnaire]
    q1 -- non --> q2{Je veux seulement savoir<br/>si un élément est présent ?}
    q2 -- oui --> set[Ensemble]
    q2 -- non --> q3{Le contenu change<br/>après création ?}
    q3 -- oui --> list[Liste]
    q3 -- non --> tuple[Tuple]`}
/>

## À 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 ?
