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
| Notation | Nom | Si n est multiplié par 10 | Exemple |
|---|---|---|---|
| O(1) | Constant | Le temps ne change pas | Lire tiles_ |
| O(log n) | Logarithmique | Le temps augmente à peine | Retirer le plus petit élément d'un tas |
| O(n) | Linéaire | 10 fois plus long | Parcourir toutes les cases |
| O(n log n) | Quasi linéaire | Un peu plus de 10 fois | Trier une liste |
| O(n²) | Quadratique | 100 fois plus long | Pour 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 cases | 2 611 cases | Rapport |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(n) | 127 | 2 611 | 21 |
| O(n²) | 16 129 | 6 817 321 | 423 |
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
Une opération par case.
Deux boucles imbriquées : O(n²)
Python
Pour chaque case, on reparcourt toutes les cases.
La boucle cachée
Le cas le plus traître. Aucune seconde boucle visible :
Python
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 :
| Écriture | Sur une liste | Sur un dictionnaire ou un ensemble |
|---|---|---|
x in collection | O(n) | O(1) |
collection. | O(n) | sans objet |
collection. | O(n) | O(1) |
collection. | O(n) | sans objet |
collection. | O(1) | sans objet |
Une fonction appelée dans une boucle
Python
return_ parcourt toute la carte : O(n). Appelée dans une boucle, elle coûte O(n) à chaque tour.
Dans le jeu
| Code | Complexité | À quelle fréquence | Verdict |
|---|---|---|---|
Map. | O(n), plusieurs passes | 60 fois par seconde | Le principal coût à l'affichage |
| Survol de la souris, test sur chaque case | O(n) | 60 fois par seconde | Évitable : une conversion de coordonnées suffit |
Map. | O(n) | À chaque déplacement, expansion | Devient O(1) avec un dictionnaire |
Map. | O(n) | À chaque mouvement de caméra | Inévitable tant qu'on recalcule toutes les cases |
Player. | O(n × m) | À chaque fin de tour | Devient O(n) avec un ensemble |
Player. | O(u × n) | Au chargement | Sans gravité : une seule fois |
| Génération de la carte | Au moins O(n²) | À la création | L'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_, 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 voisins | Coû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
-
Mesurer. Afficher
clock., ou chronométrer une fonction. Ne pas deviner.get_ fps() -
Trouver le point chaud. Ce qui s'exécute le plus souvent, avec la plus mauvaise complexité.
-
Changer la structure de données ou l'algorithme. Pas les détails d'écriture.
-
Mesurer à nouveau. Si rien n'a changé, annuler.
Pour chronométrer :
Python
À 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²).
insur une liste est une boucle cachée.- Fréquence × complexité = priorité.
- Mesurer avant et après.
Exercices
- Donner la complexité de
Map.. Comment la rendre O(1) ?find_ possible_ neighbors - Dans
City.expand, combien de foisreturn_est-elle appelée pour une ville de 15 cases sur la plus grande carte ? Combien de comparaisons au total ?neighbors_ tiles - Afficher le nombre d'images par seconde dans un coin de l'écran. Comparer une carte de 7 anneaux et une de 30.
- Chronométrer
generate_mappour 10, 20 et 30 anneaux. Le temps est-il proportionnel au nombre de cases ?