Discussion :

[mumut]

Bonjour à toute et à tous,
j'ai écrit un script qui donne le temps que mettent deux algorithmes de tri (à savoir le tri à bulle et le tri rapide) pour trier une liste.
La liste (générée aléatoirement) contient 20 000 entiers et se trouve dans le fichier donnee.py donnees.py.zip

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import time
from donnee import *
 
def quick_sort(liste):
    if len(liste) <= 1:
        return liste
    else:
        i = 1; j = len(liste) - 1
       while i < j:
            while i < j and  liste[i] <= liste[0]: i += 1
            while i < j and  liste[j] >= liste[0]: j -= 1    
            if i-j != 0:
                liste[i],liste[j] = liste[j],liste[i]
                i += 1;                j -= 1
        if liste[i] <= liste[0]:  return quick_sort(liste[1:i+1])+[liste[0]]+ quick_sort(liste[i+1:len(liste)])
        else:  return quick_sort(liste[1:i])+[liste[0]]+ quick_sort(liste[i:len(liste)])
 
 
def tri_a_bulle(liste):
    permutation = True
    while permutation == True:
        permutation = False
        for i in range(0,len(liste)-1):
            if  liste[i] > liste[i+1]:
                liste[i],liste[i+1] = liste[i+1],liste[i]
                permutation = True
    return liste
 
 
T = [quick_sort,tri_a_bulle]
 
for func in T:
    debut = time.time()
    func(liste)
    fin= time.time()
    print("{} secondes pour la fonction {}".format(fin-debut,func.__name__))

Mon problème est le suivant :

• Si dans le code ci-dessus je remplace T = [quick_sort,tri_a_bulle] par T = [tri_a_bulle] (càd si je veux juste le temps mis par le tri_a_bulle), il me renvoie un temps de 14s
• Si je laisse T = [quick_sort,tri_a_bulle], il me renvoie un temps de 0.03s pour le tri rapide et de 9s pour le tri à bulle !! (le tri à bulle est accéléré )
• Si je remplace T = [quick_sort,tri_a_bulle] par T = [tri_a_bulle, quick_sort], le temps renvoyé pour le tri à bulle est de 14s mais le programme plante pour le quicksort et renvoie un "RuntimeError: maximum recursion depth exceeded in comparison" (le tri rapide est un algorithme récursif)

Pourquoi le comportement des deux fonctions change-t-il suivant l'ordre d'appel ? il n'y a à priori aucune intéraction entre les deux.
J'ai bien sur essayé avec d'autres listes générées aléatoirements. Le problème de dépassement de pile se pose d'ailleurs à partir d'une taille de liste de 1000 éléments, alors que lancé tout seul, le quick_sort supporte aisément des listes à 1 000 000 d'entrée !

Quelqu'un pourrait m'éclairer ?

[__dardanos__]

Salut,
La fonction tri_a_bulle modifie la liste fournie en argument (et pas quick_sort). Pour s'en rendre compte :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
if __name__ == '__main__':
    from random import shuffle
    from time import clock
    N = 7000
    T = [ quick_sort, tri_a_bulle ]
    for func in T:
        my_list = list(range(N))
        shuffle(my_list)
        debut = clock()
        list_res = func(my_list)
        fin= clock()
        print("{:.3f} secondes pour la fonction {}".format(fin-debut,func.__name__))
        print(my_list[:10],list_res[:10],sep='\n')

et on obtient :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
0.044 secondes pour la fonction quick_sort
[6577, 3533, 183, 6006, 1636, 3120, 766, 5722, 2249, 3063]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
10.452 secondes pour la fonction tri_a_bulle
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Je laisse les membres plus expérimentés nous expliquer pourquoi.

[Sve@r]

Je laisse les membres plus expérimentés nous expliquer pourquoi.

Salut
Je pense que la récursivité génère à chaque appel un espace dédié au travail, espace décorrélé de l'appel précédent et de l'appel suivant.
Alors que le tri à bulle travaille dans un seul et même niveau.

Moi, ce qui me gêne dans ces deux algos, c'est ces "return liste". Ca me parait bizarre qu'une fonction ait besoin de renvoyer un élément qu'on lui a passé et donc que l'appelant possède déjà. Après-tout, un tri rapide c'est
1) choisir un pivot
2) placer de part et d'autre les éléments par rapport au pivot
3) trier la partie gauche puis la partie droite du pivot
Nul besoin ici de faire remonter vers l'appelant les deux parties triées. Surtout que l'élément étant complexe (liste, tableau, dictionnaire), la fonction ne reçoit qu'un pointeur vers cet élément et a donc toute latitude pour aller le modifier directement à son emplacement mémoire.

[mumut]

Bonjour,
merci à vous deux de vous être penché sur mon problème

(...) La fonction tri_a_bulle modifie la liste fournie en argument (et pas quick_sort) (...)

Effectivement, j'aurai du commencer par vérifier ceci. Les fonctions modifient les listes (après vérification sur des petites listes, quick_sort aussi, mais seulement quelques termes !)
Il faut donc que je rajoute un "liste=list(liste)" en début de fonction.

Mais du coup je n'y comprend plus rien ! Je croyais que les variables passées en paramètre devenaient dans la fonction une variable locale, supprimée après l'exécution.
Le code "liste[i]=a" fait-il appel à une méthode du type list ??

(...) Moi, ce qui me gêne dans ces deux algos, c'est ces "return liste". Ca me parait bizarre qu'une fonction ait besoin de renvoyer un élément qu'on lui a passé et donc que l'appelant possède déjà. (...)

L'appellant ne possède pas vraiment l'élément puisque la fonction lui renvoie la version triée, donc une version modifiée de l'élément original.

(...) Nul besoin ici de faire remonter vers l'appelant les deux parties triées. Surtout que l'élément étant complexe (liste, tableau, dictionnaire), la fonction ne reçoit qu'un pointeur vers cet élément et a donc toute latitude pour aller le modifier directement à son emplacement mémoire. (...)

Tu réponds sans doute à ma première question. Si je te comprends bien, contrairement aux entiers, float et string les listes, tableaux et dictionnaires sont passées aux fonctions via un pointeur et ne seraient donc pas des variables locales. C'est bien ça ?

[Marc3001]

Fait une copie de ta liste avant de tester ton trie.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
T = [quick_sort,tri_a_bulle]
 
for func in T:
    listeToWork = copy.deepcopy(liste)
    debut = time.time()
    func(listeToWork)
    fin= time.time()
    print("{} secondes pour la fonction {}".format(fin-debut,func.__name__))

[tyrtamos]

Bonjour,

Tout a été dit sur l'explication de la bizarrerie signalée. Je voudrais juste dire que dans le codage du quicksort, on peut simplement travailler avec des indices comme le code ci-dessous, ce qui évite de fabriquer des sous-listes pendant le tri:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def _quicksort(L, g, d):
    """utilitaire: utiliser quicksort"""
    pivot, i, j = L[(g+d)//2], g, d
    while True:
        while L[i]<pivot:
            i += 1
        while L[j]>pivot:
            j -= 1
        if i>j:
            break
        if i<j:
            L[i], L[j] = L[j], L[i]
        i += 1
        j -= 1
    if g<j:
        _quicksort(L, g, j)
    if i<d:
        _quicksort(L, i, d)
 
def quicksort(L):
    """tri rapide (quicksort de Hoare) sur place de la liste L"""
    _quicksort(L, 0, len(L)-1)

Comme ça a été dit, la liste étant passée par adresse, il s'agit d'un tri de la liste "sur place". Exemple d'utilisation:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
from random import randint
n = 1000000
liste = [randint(n, n*10-1) for i in xrange(0,n)]
quicksort(liste)
# => liste est triée

Si on ne veut pas modifier la liste initiale, on en fait une copie et on trie la copie

Enfin, il est bien connu que la performance des algorithmes de tri sont sensibles à la forme de la liste à trier: hasard, déjà triée, triée en inverse.

[mumut]

Merci à tous pour vos réponse

Comme ça a été dit, la liste étant passée par adresse, il s'agit d'un tri de la liste "sur place".

Après recherche, je viens d'apprendre que tous les passages de paramètres se font par référence. Mais suivant que l'objet soit mutable ou non, il sera modifié ou pas dans la fonction.
Un peu flou pour moi tout ça. Si quelqu'un dispose d'un lien ou tout est clairement expliqué, je suis preneur...

Si on ne veut pas modifier la liste initiale, on en fait une copie et on trie la copie

A ce sujet, vaut-il mieux faire une copie de la liste avant de lancer la fonction et d'enlever les returns (et donc d'en faire une procédure), ou plutôt de faire la copie dans la liste par un "liste=list(liste)" et de garder le return ?

[rambc]

Tout a été dit sur l'explication de la bizarrerie signalée.

Ah bon... C'est écrit où ?