Debian-facile

Bienvenue sur Debian-Facile, site d'aide pour les nouveaux utilisateurs de Debian.

Vous n'êtes pas identifié(e).

#1 07-08-2016 18:10:50

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 ! smile

(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. big_smile


Acer AX3810  (Archlinux & Debian )
Acer Aspire V5 (ubuntu-Mate)
Lenovo Thinkpad Edge E330 ( Archlinux )

Hors ligne

#2 09-08-2016 09:55:45

Dunatotatos
Membre
Lieu : Arabie Saoudite
Distrib. : Sid
Noyau : linux-image-amd64
(G)UI : tty
Inscription : 24-04-2012

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, ...

Never trust Windows output.

Hors ligne

#3 09-08-2016 14:50:33

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 smile 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 20:22:02)


Acer AX3810  (Archlinux & Debian )
Acer Aspire V5 (ubuntu-Mate)
Lenovo Thinkpad Edge E330 ( Archlinux )

Hors ligne

#4 09-08-2016 16:26:36

Dunatotatos
Membre
Lieu : Arabie Saoudite
Distrib. : Sid
Noyau : linux-image-amd64
(G)UI : tty
Inscription : 24-04-2012

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.

Never trust Windows output.

Hors ligne

#5 09-08-2016 20:22:39

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 big_smile

Acer AX3810  (Archlinux & Debian )
Acer Aspire V5 (ubuntu-Mate)
Lenovo Thinkpad Edge E330 ( Archlinux )

Hors ligne

Pied de page des forums