Rapide en test, lent en production
Un développeur teste un programme qui cherche les clients en double. Avec 100 clients, il répond en un instant.
Le lundi suivant, on le lance sur les 200 000 clients de l’entreprise. Il tourne toute la matinée.
Le code n’a pas changé. Ce sont les données qui ont grandi. Savoir prévoir cela est une compétence que tout recruteur attend.
À la fin de cette leçon
Remarque
Je peux comparer comment deux algorithmes grandissent avec plus de données.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Étape | une opération de base, comme une comparaison | |
| Taille | le nombre d’éléments à traiter, souvent appelé n | |
| Croissance | comment les étapes augmentent quand la taille augmente | |
| Double boucle | une boucle à l’intérieur d’une autre | |
| Notation grand O | la façon courte de nommer une croissance | O(n) |
| Pire cas | les données qui demandent le plus d’étapes |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
On compte des étapes, pas des secondes
Le même programme est plus rapide sur un ordinateur neuf que sur un vieux portable. Les secondes ne disent donc pas grand-chose.
On compte plutôt les étapes : combien de comparaisons ou d’opérations pour n éléments.
La vraie question est : si les données doublent, que deviennent les étapes ?
À vous : compter les étapes
def etapes_une_boucle(n):
etapes = 0
for i in range(n):
etapes = etapes + 1
return etapes
def etapes_double_boucle(n):
etapes = 0
for i in range(n):
for j in range(n):
etapes = etapes + 1
return etapes
for n in [10, 100, 1000]:
print(n, "clients :", etapes_une_boucle(n), "étapes contre", etapes_double_boucle(n))
# Ajoutez 2000 à la liste des tailles. Que devient la double boucle ?
Trois façons de grandir
Une boucle simple fait une étape par élément. Deux fois plus de données, deux fois plus d’étapes. On écrit O(n).
La dichotomie divise par deux à chaque étape. Deux fois plus de données, une seule étape de plus.
Une double boucle compare chaque élément à tous les autres. Deux fois plus de données, quatre fois plus d’étapes.
Exemple travaillé : les étapes selon la taille
| Taille | Dichotomie | Boucle simple | Double boucle |
|---|---|---|---|
| 10 | 4 | 10 | 100 |
| 100 | 7 | 100 | 10 000 |
| 1 000 | 10 | 1 000 | 1 000 000 |
| 1 000 000 | 20 | 1 000 000 | 1 000 000 000 000 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une erreur fréquente
Attention
Beaucoup pensent qu’un programme rapide sur un petit test sera rapide partout. C’est faux pour une double boucle. Avec 100 éléments, 10 000 étapes passent inaperçues. Avec un million, il en faut mille milliards. Testez toujours avec une taille proche de la réalité.
Pour la suite : arbres et graphes
Deux structures vous attendent après ce module.
Un arbre range les données en branches, comme un organigramme ou les dossiers d’un ordinateur.
Un graphe relie des éléments entre eux, comme les stations d’un réseau de métro. Un GPS s’en sert pour trouver le plus court chemin.