Mesure du temps d’exécution#
Python dispose d’un module time qui permet de mesurer le temps. La fonction time de ce module donne le temps
écoulé en seconde depuis epoch sous la forme d’un flottant. Le terme epoch désigne la date du 1/1/1970 à partir de
laquelle le temps est mesuré en informatique.
La fonction mesure_tri prend en paramètre fct qui est une chaine de caractères dont la valeur est le nom de la
fonction à mesurer. Un second paramètre n indique la taille du tableau à créer et à trier.
1from random import randint
2from time import time
3
4def mesure_tri(fct,n):
5
6 tps = 0.0
7
8 # on effectue 100 mesures de temps d'exécution de la fonction
9 for _ in range(50):
10 # on crée un tableau de dimension n
11 t = [randint(0,100000) for i in range(n)]
12 expression = fct + "(t)"
13
14 # relevé du temps initial
15 t_0 = time()
16
17 # on exécute la fonction de tri
18 eval(expression)
19
20 # relevé du temps final
21 t_1 = time()
22
23 # on ajoute le temps d'exécution de la fonction
24 tps = tps + (t_1-t_0)
25
26 # on renvoie le temps moyen d'exécution de la fonction
27 return tps/50
La fonction mesure_tri effectue 50 exécutions de la fonction à mesurer et calcule le temps total dans la variable
tps. La fonction renvoie le temps moyen d’exécution en divisant le temps total par 50.
Les 2 fonctions de tri sont regroupées dans le fichier tris.py. On les importe dans le fichier de travail.
# on importe les fonctions de tri à mesurer
from tris import tri_selection, tri_insertion
Effectuer une première mesure du tri par selection avec un tableau de dimension
n=100. Quel est le temps d’exécution du tri par selection dans ce cas ?Effectuer une première mesure du tri par insertion avec un tableau de dimension
n=100. Quel est le temps d’exécution du tri par selection dans ce cas ?Effectuer une mesure pour chaque tri avec un tableau de dimension
n=500. Par quel facteur a été multiplié le temps d’exécution par rapport au temps d’exécution d’un tableau de dimensionn=100?Vérifier que le temps d’exécution est 100 fois plus long pour chaque tri en prenant un tableau de dimension
n=1000.En réalisant plusieurs tests, contrôler que lorsque la dimension du tableau est multipliée par un facteur \(k\), alors le temps d’exécution est multiplié par \(k^{2}\).