Partie 6 : mesurer et comparer#
Dans les parties précédentes, vous avez déterminé la complexité des quatre tris en comptant leurs opérations. Il est temps de vérifier si la théorie se retrouve dans la pratique : dans cette partie, vous mesurez le temps d'exécution de vos tris sur des listes de plus en plus grandes, et vous représentez les résultats sur des graphiques.
Vos fonctions tri_selection et tri_insertion doivent fonctionner correctement avant de commencer cette partie : mesurer le temps d'exécution d'un tri faux n'aurait aucun sens !
Installer matplotlib#
Les graphiques sont tracés avec matplotlib, la bibliothèque de graphiques la plus utilisée en Python. Elle ne fait pas partie de Python lui-même et doit être installée :
Avec Thonny : menu Outils, puis Gérer les paquets.... Cherchez
matplotlib, puis cliquez sur Installer.Avec Visual Studio Code : ouvrez un terminal (menu Terminal, puis Nouveau terminal) et tapez la commande
pip install matplotlib(oupy -m pip install matplotlibsi la commandepipn'est pas reconnue).
Pour vérifier l'installation, exécutez le programme ci-dessous : il doit afficher le numéro de version de matplotlib, sans erreur.
import matplotlib
print(matplotlib.__version__)
Mesurer un temps d'exécution#
Le module time de Python contient une fonction perf_counter(), qui retourne la valeur d'un chronomètre très précis, en secondes. Pour mesurer la durée d'une partie d'un programme, on lit le chronomètre juste avant et juste après, et on calcule la différence.
1import time
2
3debut = time.perf_counter()
4total = 0
5for i in range(1000000):
6 total = total + i
7fin = time.perf_counter()
8
9print("Durée :", fin - debut, "secondes")
Exécutez ce programme plusieurs fois sur votre ordinateur : la durée n'est jamais exactement la même ! Elle dépend aussi de ce que fait l'ordinateur au même moment (autres programmes, mises à jour, navigateur...). Pour obtenir des mesures fiables :
on répète chaque mesure plusieurs fois, et on calcule la moyenne ;
on ferme les programmes inutiles pendant les mesures, et on branche l'ordinateur portable sur le secteur.
Avertissement
Les tris par sélection, par insertion et rapide trient la liste sur place. Après une première
mesure, la liste est donc déjà triée, et une deuxième mesure sur la même liste ne mesurerait plus
du tout la même chose ! Il faut toujours trier une copie de la liste, obtenue avec
liste.copy().
Tracer un graphique avec matplotlib#
Le programme ci-dessous trace un graphique avec deux courbes : les températures minimales et maximales d'une semaine (valeurs inventées pour l'exemple).
1import matplotlib.pyplot as plt
2
3jours = [1, 2, 3, 4, 5, 6, 7]
4minimales = [2, 4, 3, 6, 7, 5, 3]
5maximales = [9, 12, 11, 15, 17, 14, 10]
6
7plt.plot(jours, minimales, marker="o", label="Température minimale")
8plt.plot(jours, maximales, marker="o", label="Température maximale")
9plt.title("Températures d'une semaine")
10plt.xlabel("Jour")
11plt.ylabel("Température (°C)")
12plt.legend()
13plt.grid(True)
14plt.savefig("temperatures.png", dpi=150)
15plt.show()
import matplotlib.pyplot as pltimporte la partie de matplotlib qui sert à tracer des graphiques, sous le nom abrégéplt.plt.plot(x, y)trace une courbe qui relie les points dont les abscisses sont dans la listexet les ordonnées dans la listey. Les deux listes doivent donc avoir la même longueur. Chaque appel àplt.plotajoute une courbe au graphique.marker="o"dessine un point à chaque mesure, etlabeldonne le nom de la courbe, affiché dans la légende parplt.legend().plt.title,plt.xlabeletplt.ylabelajoutent le titre du graphique et le nom des axes. N'oubliez pas les unités !plt.grid(True)ajoute une grille, qui facilite la lecture des valeurs.plt.savefig("temperatures.png", dpi=150)enregistre le graphique dans une image, dans le même dossier que le programme. Le paramètredpirègle la résolution de l'image.plt.show()affiche le graphique dans une fenêtre. Le programme est en pause tant que cette fenêtre est ouverte.
Important
Appelez
plt.savefigavantplt.show: une fois la fenêtre fermée, le graphique est effacé, et l'image enregistrée serait vide.Pour tracer plusieurs graphiques dans le même programme, commencez chaque nouveau graphique par
plt.figure(). Sinon, les nouvelles courbes s'ajoutent au graphique précédent.Pour tracer une courbe en traitillés, ajoutez le paramètre
linestyle="--"àplt.plot.
Le programme de mesure#
Le code ci-dessous contient le tri fusion et le tri rapide, déjà programmés, ainsi que les outils pour mesurer les temps d'exécution et tracer le graphique. Dans votre fichier tris.py, supprimez les lignes de vérification (les print) qui suivent vos deux fonctions, puis copiez ce code à la suite. Tel quel, il mesure le temps moyen du tri par sélection pour des listes aléatoires de 500 à 5000 éléments, puis trace la courbe correspondante.
1# ---------- Tris fournis : ne pas modifier ----------
2
3# Fusionne deux listes triées en une nouvelle liste triée
4def fusion(gauche, droite):
5 resultat = []
6 i = 0
7 j = 0
8 while i < len(gauche) and j < len(droite):
9 if gauche[i] <= droite[j]:
10 resultat.append(gauche[i])
11 i = i + 1
12 else:
13 resultat.append(droite[j])
14 j = j + 1
15 while i < len(gauche):
16 resultat.append(gauche[i])
17 i = i + 1
18 while j < len(droite):
19 resultat.append(droite[j])
20 j = j + 1
21 return resultat
22
23# Retourne une nouvelle liste triée
24def tri_fusion(liste):
25 if len(liste) <= 1:
26 return liste
27 milieu = len(liste) // 2
28 gauche = tri_fusion(liste[:milieu]) # trie la moitié gauche
29 droite = tri_fusion(liste[milieu:]) # trie la moitié droite
30 return fusion(gauche, droite)
31
32# Partitionne la zone de debut à fin autour du pivot liste[fin],
33# puis retourne la position finale du pivot
34def partition(liste, debut, fin):
35 pivot = liste[fin]
36 i = debut
37 for j in range(debut, fin):
38 if liste[j] < pivot:
39 if i != j:
40 temp = liste[i]
41 liste[i] = liste[j]
42 liste[j] = temp
43 i = i + 1
44 if i != fin:
45 temp = liste[i]
46 liste[i] = liste[fin]
47 liste[fin] = temp
48 return i
49
50# Trie sur place la zone de debut à fin
51def tri_rapide_zone(liste, debut, fin):
52 if debut < fin:
53 p = partition(liste, debut, fin)
54 tri_rapide_zone(liste, debut, p - 1) # trie la zone des petits
55 tri_rapide_zone(liste, p + 1, fin) # trie la zone des grands
56
57def tri_rapide(liste):
58 tri_rapide_zone(liste, 0, len(liste) - 1)
59 return liste
60
61# ---------- Outils de mesure ----------
62
63import time
64from random import randint
65import matplotlib.pyplot as plt
66
67def liste_aleatoire(n):
68 liste = []
69 for i in range(n):
70 liste.append(randint(1, 1000000))
71 return liste
72
73# Retourne le temps (en secondes) nécessaire pour trier une copie de la liste
74def temps_tri(tri, liste):
75 copie = liste.copy()
76 debut = time.perf_counter()
77 tri(copie)
78 fin = time.perf_counter()
79 return fin - debut
80
81# Retourne le temps moyen (en secondes) pour trier plusieurs listes aléatoires de n éléments
82def temps_moyen(tri, n, repetitions):
83 total = 0
84 for k in range(repetitions):
85 total = total + temps_tri(tri, liste_aleatoire(n))
86 return total / repetitions
87
88# ---------- Mesures ----------
89
90tailles = [500, 1000, 1500, 2000, 2500, 3000, 3500, 4000, 4500, 5000]
91temps_selection = []
92for n in tailles:
93 t = temps_moyen(tri_selection, n, 3)
94 temps_selection.append(t)
95 print("Tri par sélection,", n, "éléments :", round(t, 4), "s")
96
97# ---------- Graphique ----------
98
99plt.plot(tailles, temps_selection, marker="o", label="Tri par sélection")
100plt.title("Temps d'exécution des tris sur des listes aléatoires")
101plt.xlabel("Taille de la liste (nombre d'éléments)")
102plt.ylabel("Temps moyen (s)")
103plt.legend()
104plt.grid(True)
105plt.savefig("graphique_aleatoires.png", dpi=150)
106plt.show()
Le tri fusion et le tri rapide sont des fonctions récursives :
tri_fusionettri_rapide_zones'appellent elles-mêmes pour trier des parties plus petites de la liste, exactement comme dans les arbres des appels des visualisations du tri fusion et du tri rapide. Vous pouvez comparer leur code aux descriptions des parties 4 et 5, mais vous n'avez pas besoin de le comprendre en détail.temps_tri(tri, liste)mesure le temps nécessaire pour trier une copie de la liste. Une fonction peut recevoir une autre fonction en paramètre, comme n'importe quelle valeur :temps_trireçoit dans son paramètretrila fonction de tri à mesurer, par exempletri_selection, et l'appelle avectri(copie).temps_moyen(tri, n, repetitions)trie plusieurs listes aléatoires différentes denéléments, et retourne le temps moyen.La boucle des mesures remplit la liste
temps_selection: pour chaque taille de la listetailles, elle contient le temps moyen correspondant. Les deux listes ont donc la même longueur, et peuvent être passées àplt.plot.
Astuce
Les mesures prennent du temps : avec les quatre tris, le programme complet peut tourner une à deux minutes. Pendant la mise au point de votre programme, travaillez avec moins de tailles et une seule répétition, puis lancez les mesures définitives une fois que tout fonctionne.
Les expériences#
Complétez les parties « Mesures » et « Graphique » du programme pour réaliser les expériences ci-dessous. Chaque expérience produit un graphique, enregistré dans sa propre image. Pour les questions qui demandent des calculs, utilisez les valeurs affichées par le programme.
Question 14#
Complétez le programme pour mesurer le temps moyen des quatre tris sur des listes aléatoires de 500 à 5000 éléments, et tracez les quatre courbes sur le même graphique. Décrivez la forme de chaque courbe. Classez les quatre tris du plus rapide au plus lent.
Question 15#
Pour chacun des quatre tris, calculez par combien le temps est multiplié lorsque la taille de la liste double : de 1000 à 2000 éléments, puis de 2000 à 4000 éléments. Présentez vos résultats dans un tableau. Ces rapports sont-ils cohérents avec la complexité de chaque tri, déterminée dans les parties 2 à 5 ? Justifiez en calculant le rapport attendu par la théorie.
Question 16#
Sur le graphique précédent, les courbes du tri fusion et du tri rapide sont presque plates. Pour mieux les comparer, tracez un nouveau graphique avec le tri fusion et le tri rapide uniquement, pour des listes aléatoires de 10 000 à 100 000 éléments (par pas de 10 000). Ajoutez sur ce graphique une troisième courbe : celle de la fonction sorted de Python, que vous pouvez mesurer exactement comme vos propres tris, avec temps_moyen(sorted, n, 3).
Lequel de vos deux tris est le plus rapide ? Est-ce cohérent avec les parties 4 et 5 ?
Combien de fois
sortedest-elle plus rapide que votre tri le plus rapide, pour 100 000 éléments ?Faites une petite recherche sur l'algorithme utilisé par
sorted, appelé Timsort. Sur quels tris est-il basé ? Pourquoi est-il si rapide ? Indiquez vos sources.
Question 17#
Le temps d'exécution d'un tri dépend-il de l'ordre initial des éléments ? Écrivez deux fonctions liste_triee(n) et liste_inverse(n), qui retournent respectivement la liste [1, 2, ..., n] et la liste [n, ..., 2, 1]. Mesurez ensuite, pour des listes de 500 à 5000 éléments, le temps du tri par sélection et du tri par insertion sur des listes déjà triées, aléatoires et triées à l'envers, et tracez les six courbes sur un même graphique. Expliquez ce que vous observez à l'aide de vos réponses aux questions 5 et 8.
Question 18#
Mesurez le temps du tri rapide sur des listes déjà triées de 100 à 900 éléments (par pas de 100), et comparez-le, sur un même graphique, au temps du tri rapide sur des listes aléatoires de mêmes tailles. Expliquez ce que vous observez à l'aide de votre réponse à la question 13.
Note
Ne dépassez pas 900 éléments. Sur une liste déjà triée, le tri rapide accumule un appel en attente
par élément dans la pile d'appels, et Python arrête le programme avec une erreur
RecursionError au-delà d'environ 1000 appels en attente.
Question 19#
Comparons enfin les mesures à la théorie. D'après la théorie, le temps du tri par sélection devrait être proportionnel à \(n^2\), c'est-à-dire de la forme \(c \cdot n^2\), où \(c\) est un nombre qui dépend de l'ordinateur.
Calculez \(c\) à partir de votre mesure pour 5000 éléments : \(c = \frac{\text{temps pour 5000 éléments}}{5000^2}\).
Sur un nouveau graphique, tracez la courbe des temps mesurés du tri par sélection, et, en traitillés, la courbe théorique \(c \cdot n^2\) pour les mêmes tailles. Les deux courbes se superposent-elles ?
Faites de même pour le tri fusion, avec les mesures de la question 16 et une courbe théorique de la forme \(c \cdot n \cdot \log_2(n)\). La fonction
log2s'importe avecfrom math import log2.
Synthèse#
Question 20#
À l'aide de vos réponses aux parties 2 à 5 et de vos mesures, recopiez et complétez le tableau suivant. Pour chaque tri, indiquez sa complexité dans le meilleur cas, en moyenne (sur une liste aléatoire) et dans le pire cas, en précisant à chaque fois quel type de liste correspond au meilleur et au pire cas. Dans la dernière colonne, indiquez si le tri travaille directement dans la liste d'origine (sur place) ou s'il crée de nouvelles listes.
Tri |
Meilleur cas |
Cas moyen |
Pire cas |
Sur place ? |
|---|---|---|---|---|
Sélection |
||||
Insertion |
||||
Fusion |
||||
Rapide |
Pour le rapport
Questions 14 à 19 : les graphiques, chacun accompagné de sa description, ainsi que les tableaux, les calculs et les réponses aux questions.
Question 20 : le tableau récapitulatif complété.
Pour finir, rédigez la conclusion du rapport, comme décrit dans la présentation du projet.