Projet 3 - Durée d'exécution de plusieurs tris
L'objectif de ce projet est de comparer la durée d'exécution de plusieurs tris afin de savoir lequel est le plus efficace pour des listes de tailles différentes.
Accéder aux scripts du projet
Les différentes importations
Avant de pouvoir commencer le programme, j'ai importé différentes bibliothèques : la bibliothèque time qui permet de calculer le temps nécessaire aux tris des listes, la bibliothèque random afin de générer des nombres aléatoirement pour remplir les listes, la bibliothèque matplotlib.pyplot pour faire des graphiques afin de représenter les données obtenus, la bibliothèque numpy qui permet de créer les modèles pour chacun des tris, la bibliothèque sys pour ne plus avoir de problèmes lors des tris par récursivités et la bibliothèque math qui sert pour le tri à peigne.
Les listes utiles au programme
Pour pouvoir stocker les résultats que l'on va obtenir, on va utiliser des listes. Avant ces listes, j'ai une méthode sys.setrecursionlimit() qui me permet d'augmenter le nombre de fois qu'une fonction peut s'appeler elle-même. Après, j'ai crée 9 listes pour mes 9 tris différents afin de stocker dans chaque une d'entre elles les résultats des tris. J'ai ensuite 2 listes : n_list et n2_list qui me permettent de stocker le nombre d'éléments qu'il y a dans chaque liste. J'ai avec cela les tris les plus lents qui fonctionnent avec entre 1000 et 10000 éléments et les tris les plus rapides qui fonctionnent avec entre 50000 et 500000 éléments.
Fonction permettant de créer des listes
Pour pouvoir trier des éléments, il faut d'abord créer des listes. Pour cela, j'ai une fonction list_create avec un paramètre x pour créer des listes de tailles différentes. Je commence par affecter à une variable blank_list une liste vide. Puis, si mon paramètre x est égal à 1000, je mets dans la liste n_list les éléments que je souhaite (entre 1000 et 10000), par contre, si ce n'est pas 1000, je mets dans une autre liste n2_list les éléments (ici, de 50000 à 500000). Après ceci, j'ai une boucle for qui va remplir ma liste, elle prend en paramètre un range de i (une variable qui est dans une boucle for plus bas dans le programme) multiplié par x. Je vais alors remplir avec la fonction random.randint ma liste avec des valeurs allant de 0 à 99. Pour finir, je renvoie ma liste.
Fonctions pour calculer le temps que mettent les méthodes sort et sorted
Afin de savoir combien de temps mettent à s'exécuter les méthodes sort et sorted, j'ai crée 2 fonctions. Les 2 fonctions prennent en paramètre une liste. La fonction sort_time est constituée de 2 variables aux quels j'affecte à chaque fois la méthode time, issue de la bibliothèque time, cela permet d'avoir le temps du microprocesseur en seconde. Je mets entre ces 2 variables, ma liste sort_list que je dois trier avec la méthode sort(). J'ai une 3ème variable que j'ai nommé delta, qui soustrait les variables t2 et t1 afin d'obtenir le temps qu'a mis la méthode sort à être exécuter. Pour finir, je vais mélanger la liste avec la méthode shuffle de la bibliothèque random afin de garder la même liste à trier pour mes autres tris à effectuer. La fonction sorted_time est pratiquement la même que la fonction précédente, seul la méthode sorted est utilisée à la place de la méthode sort. La différence de cette méthode est qu'il faut passer en paramètre la liste que l'on souhaite trier. Également, j'ai mis la méthode dans une variable pour ne pas avoir à re-trier la liste par la suite.
Je vais utiliser le même principe pour mes 7 autres tris, je ne vais pas expliquer à chaque fois cette partie, tous est disponible sur le GitHub (lien dans l'entête de cette page)
Exemple d'un autre tri : le tri par insertion
Je mets l'exemple d'un algorithme de tri différent, j'ai choisi le tri par insertion. Le fonctionnement est assez simple, tout d'abord, j'ai une fonction avec comme paramètre une liste insert. Je commence par créer une boucle for avec comme compteur j qui va varier de 1 à la longueur de la liste insert. Je crée 2 variables, key où j'affecte l'élément j de la liste insert, et j'affecte à la variable i la valeur de j - 1. Ensuite, je définis une autre boucle, mais ici while, qui dit que tant que i est supérieur à 0 et que la liste insert avec comme clé i est supérieur à key, on fait les actions ci-dessous. On va affecter à l'élément i + 1, l'élément i, puis on décrémente i de 1. Pour finir, on affecte à l'élément i + 1 de la liste insert la valeur de key. Je fais le même processus que la partie du dessus pour calculer le temps nécessaire à l'exécution de cette fonction / de ce tri.
Fonction qui me trace les modèles des différents tris
Afin d'avoir les modèles sur mes graphiques, j'ai crée cette fonction model avec 6 paramètres : num1, num2 et inter servent à faire varier l'intervalle du nombre d'éléments de la liste. n correspond à la liste des différentes tailles de listes utilisées (n_list et n2_list), list qui prend la liste de résultats afin de tracer la courbe et enfin color me permet de choisir la couleur de la courbe que je souhaite avoir. Je commence par créer 2 variables : x qui met en abscisse les différentes tailles de listes et y qui prend la liste des résultats des tris. Ces 2 variables commence à chaque fois avec np.array(), ceci permet de transformer les listes de Python en tableau Numpy afin de calculer les modèles. Ensuite, j'ai une autre variable model à laquelle j'affecte la fonction np.polyfit() avec comme paramètre x, y et 2, ces paramètres permettent de créer la fonction de degré 2 correspondant aux différents résultats des chaque tris. Cette méthode crée une liste, je peux donc appeler plus tard mes coefficients afin de les afficher. Ensuite, je crée une dernière variable : poly, celle-ci prend en argument la méthode de Numpy poly1d, ceci permet de dessiner la courbe sur le graphique. C'est une variable / fonction, dans la ligne de mon return, j'appelle la variable poly et je lui mets un paramètre, ici, x. Dans cette dernière ligne, je fais un plt.plot() afin d'afficher le modèle sur le graphique, je mets les paramètres que je souhaite afin d'avoir la bonne couleur, la bonne courbe et l'affichage de l'équation.
Fonction permettant de dessiner le graphique
Ma fonction graphical prend 11 paramètres, afin de dessiner 2 graphiques pour 9 tris et 2 tailles de listes différentes. Je ne vais pas rentrer dans les détails mais je fais plt.plot() avec la liste de résultats du tri que je souhaite afficher, je mets plusieurs paramètres : je mets des marker différents à chaque fois, je change la couleur, je désactive les lignes entre les points et je mets un label afin de mieux reconnaitre mes tris. Ensuite, j'appelle ma fonction model qui va afficher le modèle sur le graphique avec tous les paramètres requis. Puis, je mets des légendes et un titre.
La boucle for qui va lancer tous les tris
Cette boucle for est placée à la fin de mon programme. Je crée une boucle qui prend en argument un range(1, 11), c'est-à-dire que je vais faire 10 tours de boucles à chaque fois, pour avoir 10 longueurs de listes différentes à trier. Je fais un print(i) afin de savoir où en est la boucle dans l'exécution du programme et savoir si elle ne répond plus. Je crée ensuite 2 variables L et L2 pour avoir 2 tailles de listes différentes, les tris les plus lents iront avec la taille de la liste L (qui va de 1000 à 10000 éléments) et les tris les plus rapide iront avec la taille de la liste L2 (qui va de 50000 à 500000 éléments). Pour finir, j'appelle mes 9 tris avec les listes qui leur sont attribuées. La dernière ligne de mon programme appelle la fonction graphical qui va dessiner les 2 graphiques.
Les résultats finaux !
Cliquez sur les images afin de les agrandir et de mieux observés les résultats obtenus
Mes difficultés lors de la réalisation de ce projet
Lors de la réalisation de ce projet, j'ai été confronté à peu d'erreurs ou de problèmes mais ces erreurs ont pris longtemps à être résolu :
- lors de la mise en place du tri rapide récursif j'ai été confronté à une erreur : RecursionError: maximum recursion depth exceeded in comparison. Pour résoudre cette erreur, j'ai chercher sur Internet une solution simple afin de ne pas devoir changer de tri. C'est pour cela que j'ai ajouté la bibliothèque sys afin de modifier la limite de récursion possible dans un programme Python. Depuis que j'ai ajouté cela, je n'ai plus eu de problème de ce type.
- pour trouver la manière de faire les modèles, j'ai mis beaucoup de temps à trouver une méthode simple et que j'arrivais à faire fonctionner. J'ai d'abord regarder sur la documentation, et j'ai essayé de reproduire les exemples mais aucun ne donnaient de résultats. J'ai ensuite regarder sur Internet afin de voir si d'autres personnes ont essayés de faire la même chose que moi, mais là encore, je ne comprenais pas la manière de faire, je trouvais des résultats qui se servaient d'une autre bibliothèque et pas celle que je souhaitais. J'ai cherché ainsi durant quelques heures, j'ai fait une centaine de sites sur le sujet, et j'ai décidé de retourner sur les sites que j'avais vu en premier. Je suis retourner sur un site que je n'avais regarder qu'en diagonale, et en le lisant bien et en comprenant le code, j'ai enfin pu réaliser les modèles. Je n'avais pas compris que la méthode poly1d() devait être appelé avec un paramètre, c'est ce qui m'a fait bloquer au moins 3 heures.
- enfin, quand j'avais tous terminer, j'ai remarquer que les tris les plus rapides avaient des temps d'exécution de 0 seconde, ce qui est compliqué pour comparer les différents tris, j'ai alors décider de modifier mon programme existant afin de pouvoir avoir la possibilité d'avoir 2 tailles de listes différentes. Cela ne m'a pas pris 1 heure, mais une bonne quinzaine de minutes.
Je n'ai pas eu tant d'erreurs que ça mais ceci sont les difficultés que j'ai pu rencontrer et que j'ai souhaitais résoudre seul. Maintenant, je sais que je pourrais refaire ceci sans aucun soucis.
Ma conclusion sur la rapidité des tris
Après avoir crée ce programme, on peut enfin analyser les résultats que l'on a obtenu et les comparer. La première chose que l'on voit c'est que le tri à bulle est de loin le tri le plus lent. Mais alors, pourquoi cela ?
La manière dont est codée ce tri fait qu'il est le plus lent comparée aux autres. Pour fonctionner, on met 2 boucles for imbriquées l'une dans l'autre, à cela, on ajoute une instruction conditionnel if afin de comparer si les 2 éléments côte à côte sont plus grands ou plus petits. Cela fait augmenter le nombre de tours de boucles à faire de manière considérable. Pour trier une liste de 10000 éléments, il met environ 18 secondes. On remarque que le modèle suit pratiquement les points, cela signifie que le temps et le nombres d'éléments augmente ensemble de la même façon.
Si je compare ce tri, au deuxième tri le plus lent, qui est le tri par insertion, on voit que le tri par insertion contient lui aussi 2 boucles, mais seulement 1 boucle for et 1 boucle while, cela lui permet de faire la comparaison en même temps que de défiler les éléments. Grâce à cela, ce tri est pratiquement 2 fois plus rapide que le tri à bulles.
Si je prend maintenant les tris les plus rapides, on voit que le tri sort et le tri sorted sont de loin les tris les plus rapides. Mais pourquoi ? Le tri sort et sorted sont un mélange du tri par insertion et du tri par fusion. Le mélange des deux donne un tri qui est très rapide. Il considère qu'une partie de la liste et déjà triée et qu'il reste qu'une partie à trier. Les tours de boucles effectuées par ces 2 tris sont beaucoup moins important que le tri à bulles.
Le tri par comptage est lui assez intéressant surtout la manière dont il fonctionne. Il va compter tous les éléments de la même valeur pour après reconstitué la liste triée dans le bon sens. Pour des petites listes, ce tri n'est pas très intéressant mais pour des listes qui commence à 400000 éléments, on remarque avec le modèle que le temps commence à être de plus en plus stable. On peut donc supposer pour les très grandes listes (+ de 1 million d'éléments) que ce tri à des capacités importantes.
Pour conclure, il faut savoir que les tris que propose Python sont des tris qui sont très efficace. Donc pour une liste de plus de 100000 voir 1 million d'éléments, il vaut mieux privilégier le tri sort, le tri sorted et le tri par comptage. Je n'ai parler ici que de 5 tris, les 4 autres sont des très bons tris mais leurs résultats sont tous assez similaires. J'ai choisi ceux que me paraissait les plus intéressant à décortiquer.