Picassciences

Travail à rendre pour le 15 avril

>> Travail à rendre avant le mercredi 15 avril dans la rubrique Messagerie de picassciences, (sous forme d’un fichier zip, si vous avez séparé votre travail en plusieurs scripts).

La performance d’un algorithme de tri est très importante, notamment quand il s’agit de traiter de grandes quantités de données, comme c’est le cas pour le Big data.

Quel est l’impact du nombre d’éléments à trier sur le temps d’exécution ?

Consigne :

Reprendre les trois algorithmes de tris de la semaine dernière (bulle, insertion, sélection) et créer un algorithme qui mesure le temps d’exécution de ces 3 algorithmes en fonction de la taille de la liste à trier. Ce travail est dirigé ci dessous en 3 grandes étapes à suivre.

Etape 1 : Mesurer les temps d’exécution en fonction du nombre de valeurs à trier.

Les listes seront générées automatiquement, pour donner des suites descendantes de 1000, 2000, 3000 entiers, etc…. comme suit :

[1000, 999, 998, ..... , 9, 8, 7, 6, 5, 4, 3, 2, 1]

Cela permet d’obtenir le pire cas en terme de nombre d’échanges de valeurs si on trie la liste dans l’ordre croissant.

Pour mesurer le temps de tri de chaque longueur de liste, vous utiliserez l’import time, que nous avons déjà utilisé cette année dans plusieurs projets.

import time

start = time.time()

end = time.time()

Temps = end - start 

Etape 2 : En graphique

Vous grapherez ensuite en utilisant matplotlib le temps d’exécution (ordonnées) en fonction de la taille de la liste (abscisse 1000, 2000, 3000, …).

import matplotlib

import matplotlib.pyplot as plt

#Vous devez créer au préalable deux listes de valeurs, ici les tailles des listes et leur temps d’exécution.

plt.xlabel('Taille')

plt.ylabel('TempsCalcul')

plt.title("Temps d'execution en foncion de la taille de la liste")

plt.plot(Taille,TempsCalcul )

plt.show()

Pour le tri par insertion, voici le résultat à obtenir (attention, pour des listes de plus de 5000, les temps de calculs peuvent être importants).

Etape 3 : Modélisation

Les coûts en temps de ces algorithmes suit souvent une loi quadratique (comme par exemple t(x) = ax^3 + bx^2 + cx avec x étant la taille de la liste)

Nous allons donc réaliser une modélisation pour déterminer l’équation de la courbe obtenue. Voici ci-dessous, un exemple d’une modélisation en utilisant la librairie numpy, d’un nuage de point de coordonnées (x,y).

import numpy as np

import matplotlib.pyplot as plt

x = [0,1,2,3,4,5,6,7,8,9]

y = [2,8,10,23,45,89,120,256,358,688]

p = np.poly1d(np.polyfit(x, y, 3))

print(p)

plt.plot(x, y, 'o', x, p(x), '-') 

plt.show() 

On obtient pour cet exemple la figure ci dessous

En ce qui concerne toujours le tri par insertion, on obtient la courbe suivant avec l’équation

Evidemment, ces valeurs seront propres à la machine sur laquelle vous exécutez l’algorithme.