Pourquoi une appli ralentit avec 10 000 photos
Comparer deux algorithmes, c’est regarder comment leur nombre d’étapes grandit quand les données grandissent. C’est ce qui sépare une appli toujours fluide d’une appli qui rame.
Avec 20 photos, toutes les méthodes semblent rapides. Avec 10 000, la différence saute aux yeux.
À la fin de cette leçon
Remarque
Je peux comparer deux algorithmes selon la façon dont leur nombre d’étapes grandit.
Mots clés
| Mot | Ce que ça veut dire |
|---|---|
| Étape | une opération que l’algorithme fait, comme une comparaison |
| Pire cas | la situation où l’algorithme a le plus d’étapes à faire |
| Complexité | la façon dont le nombre d’étapes grandit avec la taille des données |
| Linéaire | le nombre d’étapes grandit comme la taille des données |
| Quadratique | le nombre d’étapes grandit comme la taille multipliée par elle-même |
| Logarithmique | on coupe en deux à chaque étape : le nombre d’étapes grandit très lentement |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
On compte des étapes, pas des secondes
Un chronomètre dépend de la machine : ton téléphone et un gros ordinateur ne donnent pas les mêmes secondes.
Le nombre d’étapes ne dépend pas de la machine. On le compte dans le pire cas, par exemple une valeur absente. Ce chiffre est exact et se compare partout.
Compte les étapes de trois méthodes
def etapes_lineaire(n):
return n
def etapes_dichotomie(n):
etapes = 0
while n > 0:
n = n // 2
etapes = etapes + 1
return etapes
def etapes_bulles(n):
total = 0
for passe in range(n - 1):
total = total + (n - 1 - passe)
return total
for n in [10, 100, 1000]:
print(n, etapes_lineaire(n), etapes_dichotomie(n), etapes_bulles(n))
# Ajoute 10000 à la liste : que devient la dernière colonne ?
Exemple travaillé : les étapes selon la taille
| Taille n | Recherche linéaire | Dichotomie | Tri à bulles |
|---|---|---|---|
| 10 | 10 | 4 | 45 |
| 100 | 100 | 7 | 4 950 |
| 1 000 | 1 000 | 10 | 499 500 |
| 10 000 | 10 000 | 14 | 49 995 000 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Que devient le travail quand les données doublent ?
C’est la bonne question. Pour une recherche linéaire, le travail double. Pour une dichotomie, on ajoute une seule étape.
Pour un tri à bulles, le travail est multiplié par quatre : on dit qu’il est quadratique. Les informaticiens écrivent O(n) pour linéaire, O(log n) pour logarithmique et O(n²) pour quadratique.
Exemple travaillé : doubler les données
| Méthode | Étapes pour 1 000 | Étapes pour 2 000 | Le travail est… |
|---|---|---|---|
| Recherche linéaire, O(n) | 1 000 | 2 000 | multiplié par 2 |
| Dichotomie, O(log n) | 10 | 11 | augmenté d’une étape |
| Tri à bulles, O(n²) | 499 500 | 1 999 000 | multiplié par environ 4 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Chronomètre toi-même dans le lab
Le lab te donne JupyterLab, un carnet où tu écris du Python et lis les résultats. Ouvre un carnet et chronomètre une cellule avec %timeit.
Ce que tu mesures dépend de ta machine, donc cette leçon ne donne aucun chiffre. Double la taille de la liste, mesure encore, et compare ton rapport à celui du tableau.
Une cellule de carnet pour chronométrer un tri
# À écrire dans une cellule de JupyterLab, pas ici.
liste = list(range(1000, 0, -1))
%timeit sorted(liste)
liste = list(range(2000, 0, -1))
%timeit sorted(liste)
# Compare les deux temps que ta machine affiche.
Calcule les étapes de dix à dix mille
docker exec jupyter python3 -c "import math; print([(n, math.floor(math.log2(n)) + 1, n * n) for n in [10, 100, 1000, 10000]])"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Compte les comparaisons du tri sur 365 jours
docker exec jupyter python3 -c "print(365, 365 * 364 // 2)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Ce que disent les deux Runs
Le premier Run affiche pour chaque taille trois nombres : la taille, le nombre d’étapes d’une dichotomie, puis la taille au carré, soit (10, 4, 100).
Le second Run affiche 365 66430. Un tri à bulles sur les 365 jours du fichier du lab fait 66 430 comparaisons. Une dichotomie en fait 9 au plus.
Une erreur fréquente
Attention
Beaucoup pensent qu’une méthode rapide sur une petite liste le reste sur une grande. Sur 10 valeurs, 45 étapes ou 10 étapes ne se voient pas. Sur 10 000 valeurs, 49 995 000 étapes se voient très bien. Regarde la croissance, pas un seul essai.
Pour aller plus loin : le tri fusion
Le tri fusion fait à peu près n fois log n étapes. Pour 1 000 valeurs, cela fait environ 10 000 étapes, contre 499 500 pour le tri à bulles.
Dans ton carnet, chronomètre sorted sur 1 000 puis 10 000 valeurs. Le temps est-il multiplié par environ dix, ou par cent ?