Debian-facile

Maximilien LIX

Membre

Distrib. : Archlinux

(G)UI : GNOME

Inscription : 17-12-2013

Site Web

Algo pour trier des données rapidement en Python

Hello world,
j'aimerais vous partager des algorithmes qui permettent de ranger dans l'ordre croissant une série de nombres. En même temps, j'aimerais avoir vos conseils afin de pouvoir améliorer le temps d'exécution des fonctions pour trier les données encore plus rapidement !

(ici je teste le temps d'exécution par rapport à une liste de 1000 valeurs variant de 0 à 999)

1 - Le tri bulle :

def tri_bulle(liste):
    permutation = True
    while permutation:
        permutation = False
        for x in range(0, len(liste)-1):
            if liste[x] > liste[x+1]:
                permutation = True
                liste[x], liste[x+1] = liste[x+1], liste[x]
    return liste

Temps d'exécution par tri-bulle : 2.500e-01 secondes

2 - Le tri par sélection :

def maxi(liste, n):
    indice = 0
    for i in range(n):
        if liste[i] > liste[indice]:
            indice = i
    return [liste[indice], indice]

def tri_selection(liste):
    i = len(liste) - 1
    while i > 0:
        j = maxi(liste, i + 1)[1]
        if j != i:
            liste[j], liste[i] = liste[i], liste[j]
        i -= 1
    return liste

Temps d'exécution par sélection : 7.147e-02 secondes

3 - Le tri par insertion :

def insertion(liste, n):
    while liste[n] < liste[n-1] and n > 0:
        liste[n], liste[n-1] = liste[n-1], liste[n]
        n -= 1
    return liste

def tri_insertion(liste):
    n = len(liste)
    for i in range(1, n):
        liste = insertion(liste, i)
    return liste

Temps d'exécution par insertion : 1.240e-01 secondes

4 - Le tri rapide :

def tri_rapide(liste):
    if liste == []:
        return []
    else:
        return (tri_rapide([x for x in liste[1:] if x < liste[0]])
                + [liste[0]] + tri_rapide([x for x in liste[1:] if x >= liste[0]]))

Temps d'exécution par tri-rapide : 4.888e-03 secondes


Bon je constate que le tri-rapide porte bien son nom mais j'aimerais faire mieux que ça encore ! Si vous avez des recommandations je suis preneur.

Dunatotatos

Invité

Re : Algo pour trier des données rapidement en Python

Fais attention à quelques petits détails lors d'une évaluation d'efficacité d'algorithme :
* Ne lance pas le tri qu'une seule fois, mais une centaine, voire un millier de fois, mesure le temps que ces 1000 tris ont pris, puis divise par 1000. Ça te permet d'avoir une mesure plus précise, mais surtout de minimiser l'influence des opérations annexes (copie des variables, lancement de Python, ...)
* Compare tes tris sur différents types de données d'entrée. Je ne parle pas d'utiliser des flottants au lieu d'entier (quoique, ça peut être intéressant), mais de prendre une liste déjà triée, une liste triée à l'envers, une liste mélangée "au hasard", une liste "presque triée", ... Selon les cas, certains algorithmes sont meilleurs que d'autres.
* Fais aussi varier la longueur de ta liste. La complexité d'un algorithme s'évalue en O(qqch). J'imagine que tu comprends ce concept si tu connais différents types de tris. Mais attention ! Un tri en O(n log n) qui s'avère avoir en réalité un facteur 1000 quand on évalue sa complexité en temps sera beaucoup moins bon qu'un tri en O(n²) qui a un facteur de seulement 2. Mais seulement sur les petits tableaux. Pour les tableaux plus longs que 4168 cases, la tendance s'inverse.

L'idéal reste toujours l'analyse théorique de la complexité d'un algorithme, puis la vérification expérimentale, pour le fun, pour vérifier qu'on n'a pas fait de faute, pour découvrir une fonctionnalité cachée de Python, ...

Maximilien LIX

Membre

Distrib. : Archlinux

(G)UI : GNOME

Inscription : 17-12-2013

Site Web

Re : Algo pour trier des données rapidement en Python

Merci du conseil J'avais lu sur OC que le tri rapide est particulièrement nul dans le cas où il doit trier une liste dont des nombres sont rangés dans l'ordre décroissant. Je vais revoir les algos.

Dernière modification par Maximilien LIX (09-08-2016 19:22:02)

Dunatotatos

Invité

Re : Algo pour trier des données rapidement en Python

Il y a sur Wikipedia un tableau récapitulatif :
https://fr.wikipedia.org/wiki/Algorithm … lgorithmes

De manière plus générale, la page en totalité est intéressante.

Maximilien LIX

Membre

Distrib. : Archlinux

(G)UI : GNOME

Inscription : 17-12-2013

Site Web

Re : Algo pour trier des données rapidement en Python

Ah nickel ! Merci pour le lien