Aller au contenu

La complexité

La complexité répond à une question précise : si mes données deviennent dix fois plus grosses, mon code devient combien de fois plus lent ?

Le problème

Le jeu est fluide sur la carte par défaut, 127 cases. Sur la plus grande, 2 611 cases, il ralentit. Le code est pourtant le même. L'auteur a noté à plusieurs endroits « pas très optimisé », sans savoir par où commencer.

La complexité donne une méthode pour repérer où ça coince, sans rien mesurer, juste en lisant le code.

L'idée

On ne compte pas des secondes, qui dépendent de la machine. On compte combien d'opérations fait le code en fonction de la taille des données, notée n.

Ici, n est le nombre de cases de la carte.

Les cas courants

NotationNomSi n est multiplié par 10Exemple
O(1)ConstantLe temps ne change pasLire tiles_by_coo[(3, 4)]
O(log n)LogarithmiqueLe temps augmente à peineRetirer le plus petit élément d'un tas
O(n)Linéaire10 fois plus longParcourir toutes les cases
O(n log n)Quasi linéaireUn peu plus de 10 foisTrier une liste
O(n²)Quadratique100 fois plus longPour chaque case, parcourir toutes les cases

La notation se lit « grand O de n ». Elle garde l'ordre de grandeur et ignore les détails : 3n + 5 opérations, c'est O(n).

En chiffres, pour les deux tailles de carte du jeu :

Complexité127 cases2 611 casesRapport
O(1)111
O(n)1272 61121
O(n²)16 1296 817 321423

Une carte 21 fois plus grande rend un code quadratique 423 fois plus lent. C'est là que le jeu ralentit.

Lire la complexité dans le code

Une boucle : O(n)

Python
for tile in self.tiles: tile.draw_tile(self.fog_of_war)

Une opération par case.

Deux boucles imbriquées : O(n²)

Python
for a in self.tiles: for b in self.tiles: ...

Pour chaque case, on reparcourt toutes les cases.

La boucle cachée

Le cas le plus traître. Aucune seconde boucle visible :

Python
for tile in self.game.map.tiles: if tile in total_tiles_owned: tile.owner = self.id

Mais in sur une liste est une boucle : Python compare avec chaque élément. C'est donc O(n × m), avec m le nombre de cases possédées.

Les boucles cachées courantes :

ÉcritureSur une listeSur un dictionnaire ou un ensemble
x in collectionO(n)O(1)
collection.index(x)O(n)sans objet
collection.remove(x)O(n)O(1)
collection.pop(0)O(n)sans objet
collection.append(x)O(1)sans objet

Une fonction appelée dans une boucle

Python
for tile in regional_tiles: for neighbor in self.game.map.return_neighbors_tiles(tile): ...

return_neighbors_tiles parcourt toute la carte : O(n). Appelée dans une boucle, elle coûte O(n) à chaque tour.

Dans le jeu

CodeComplexitéÀ quelle fréquenceVerdict
Map.draw_tilesO(n), plusieurs passes60 fois par secondeLe principal coût à l'affichage
Survol de la souris, test sur chaque caseO(n)60 fois par secondeÉvitable : une conversion de coordonnées suffit
Map.return_neighbors_tilesO(n)À chaque déplacement, expansionDevient O(1) avec un dictionnaire
Map.update_tile_sizeO(n)À chaque mouvement de caméraInévitable tant qu'on recalcule toutes les cases
Player.update_map_tiles_ownerO(n × m)À chaque fin de tourDevient O(n) avec un ensemble
Player.load_units_ownedO(u × n)Au chargementSans gravité : une seule fois
Génération de la carteAu moins O(n²)À la créationL'auteur note que le ralentissement vient de là

La fréquence compte autant que la complexité

Un code lent exécuté une fois ne gêne personne. Un code moyen exécuté 60 fois par seconde, si.

C'est pourquoi load_units_owned, pourtant peu efficace, n'est pas un problème, alors que le test de survol, tout simple, en est un.

Pathfinding : pourquoi la complexité décide

A* interroge les voisins de chaque case qu'il explore. Sur une grande carte, il peut explorer un millier de cases.

Recherche des voisinsCoût d'un calcul de chemin sur 2 611 cases
Avec la liste, O(n)Environ 1 000 × 2 611, soit 2,6 millions de comparaisons
Avec le dictionnaire, O(1)Environ 1 000 × 6, soit 6 000 recherches

Et le chemin est recalculé à chaque fois que la souris change de case. Ce n'est pas une optimisation de confort : sans le dictionnaire, le pathfinding est inutilisable.

La méthode pour optimiser

  1. Mesurer. Afficher clock.get_fps(), ou chronométrer une fonction. Ne pas deviner.

  2. Trouver le point chaud. Ce qui s'exécute le plus souvent, avec la plus mauvaise complexité.

  3. Changer la structure de données ou l'algorithme. Pas les détails d'écriture.

  4. Mesurer à nouveau. Si rien n'a changé, annuler.

Pour chronométrer :

Python
import time start = time.perf_counter() self.map.draw_tiles() print(f"draw_tiles : {(time.perf_counter() - start) * 1000:.1f} ms")

À 60 images par seconde, une image dispose de 16,7 millisecondes au total.

Ne pas optimiser trop tôt

L'auteur du jeu a écrit une règle sage en bas de game.py : rendre le jeu jouable avant de l'optimiser.

  • Un code clair et lent se corrige facilement.
  • Un code rapide et illisible ne se corrige plus.
  • La plupart du code n'a pas besoin d'être rapide.

Les deux seuls cas où il faut y penser dès le début : ce qui tourne à chaque image, et le choix des structures de données, parce qu'il est pénible à changer ensuite.

À retenir

  • La complexité dit comment le temps grandit avec les données.
  • Une boucle : O(n). Deux boucles imbriquées : O(n²).
  • in sur une liste est une boucle cachée.
  • Fréquence × complexité = priorité.
  • Mesurer avant et après.

Exercices

  1. Donner la complexité de Map.find_possible_neighbors. Comment la rendre O(1) ?
  2. Dans City.expand, combien de fois return_neighbors_tiles est-elle appelée pour une ville de 15 cases sur la plus grande carte ? Combien de comparaisons au total ?
  3. Afficher le nombre d'images par seconde dans un coin de l'écran. Comparer une carte de 7 anneaux et une de 30.
  4. Chronométrer generate_map pour 10, 20 et 30 anneaux. Le temps est-il proportionnel au nombre de cases ?