C17.3 : TD - Visualisation graphique du coût d'un algorithme

But du TP

On souhaite visualiser, sous la forme d’un graphique, le coût des deux algorithmes de recherche que l’on a vu (voir C15.2) en fonction de la taille n de la liste dans laquelle se fait la recherche.

Ici, le coût sera estimé par le temps mis par l’ordinateur pour faire la recherche.

On travaillera avec des listes contenant les entiers de 0 à n-1. On se placera dans le pire cas en recherchant la position de l'entier n.

Finalement, on souhaite tracer le graphique suivant :

Quelques outils en python

Tracer un graphique : la bibliothèque Matplotlib

Présentation

Le module Matplotlib est une bibliothèque en python qui permet de tracer des graphiques de qualité.

Lien : Module matplotlib pour Python

Exemple

Tracé de la fonction \(y = f(x)\) où \(f(x) = x²\)

import matplotlib.pyplot as plt

#création de la liste pour les abscisses
liste_x = [x for x in range(0,101,10)]

#création de la liste pour les ordonnées
liste_y = [x*x for x in liste_x]

#choix des limites des axes [xmin, xmax, ymin, ymax] (facultatif)
plt.axis([0, 100, 0, 10000])

#tracé du graphqiue
#dans 'rx ' 'r' ⇨ rouge, 'x' ⇨ croix, ' ' ⇨ pas de lien
plt.plot(liste_x,liste_y,'rx ')

#génération de la fenêtre du tracé
plt.show()

Résultat :

A faire

🖥️ Modifier le code précédent pour tracer la courbe \(y = x\) en bleu.

Mesurer une durée : la fonction perf_counter() de la bibliothèque time

Présentation

La bibliothèque time permet de disposer d'un compter (en ms) qui se déclenche automatiquement au lancement du programme. La fonction perf_counter() permet de connaitre le temps écoulé.

Exemple

Mesure du temps mis pour créer une liste

from time import perf_counter

t0 = perf_counter()
liste = [x**2 for x in range(100)]
t1 = perf_counter()
duree = t1 - t0
print(duree)

A faire

🖥️ Modifier le programme précédent afin de mesurer le temps mis pour faire \(1 + 1 + … + 1\), \(1000000\) fois.

Programme à écrire

Structure du programme

Le programme qui va permettre de répondre au but du TD est constitué de quelques fonctions et d'une partie principale.

• Les deux fonctions de recherche :

On les appellera rech_seq(val, liste) et rech_dic(val, liste).

Ces deux fonctions  prennent un entier val et une liste liste comme paramètres et renvoient la position de l'entier dans la liste.

• Deux fonctions de mesure du temps mis pour faire une recherche avec la valeur et la liste en paramètre :

On les appellera tps_rech_seq(val, liste) et tps_rech_dic(val, liste). Ces deux fonctions prennent un entier val et une liste liste comme paramètres et renvoient le temps mis pour faire la recherche.

• Deux fonctions de mesure du temps mis pour faire une recherche, avec la taille de la liste souhaitée en paramètre :

On les appellera taille_to_tps_seq(n) et taille_to_tps_dic(n).

Ces deux fonctions prennent un entier n comme paramètre (cet entier n correspond à la longueur de la liste dans laquelle la recherche sera faite) et renvoie le temps mis pour faire une recherche.

Ces deux fonction vont :

Remarque : en recherchant la valeur n dans une liste contenant les entiers de 0 à n-1, on se place dans le pire cas pour les deux algorithmes de recherche.

• Le programme principal

Le programme principal contient :

Travail à faire

🖥️ Écrire le programme qui réponde au but du TP en respectant la structure ci-dessus.