Temps d'exécution d'un algorithme

Version imprimable

22/07/2019, 10h25
Cantorine

2 pièce(s) jointe(s)

Temps d'exécution d'un algorithme

Bonjour
J'ai programmé trois types de tri : le tri par sélection, le tri par insertion et le tri rapide.
Je voulais faire apparaître le temps d'exécution en plus de la liste triée. (la liste non triée est donnée en argument).
Seulement voilà, mes résultats sont en opposition totale avec la réalité (le tri rapide semble le plus long !!)
Où est le problème ??
Pièce jointe 492705 Pièce jointe 492707

j'ai remplacé time.clock() par time.perf_counter(), même problème ...

Merci beaucoup à quelqu'un qui saura me mettre sur la bonne piste :)
22/07/2019, 10h50
Flodelarab

Bonjour :coucou:

[Hors-sujet] Pourquoi ta boucle de gauche a pour condition while (i>0): plutôt que while (i>=0): ? [/Hors-sujet]
:weird: Ah ! Mais je vois que les 2 codes ont le même problème. Tu as une liste de n objets et tu parcours de 1 à (n-1).

N'aie pas peur de copier coller ton code entre 2 balises [ code ]

Merci beaucoup pour te réponse rapide.
Les deux algorithmes sont efficaces, ils trient bien les listes données en arguments.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 def maxi(l,n): indice=0 for i in range(n): if l[i]>l[indice]: indice=i return [l[indice],indice] def insertion(l,n): while l[n]<l[n-1] and n>0: l[n-1],l[n]=l[n],l[n-1] n-=1 return l
Je t'ai mis en copie les programmes maxi et insertion que j'appelle dans les deux autres.
Le problème c'est les temps d'exécution qui semble contraires à la théorie (le tri par insertion est plus rapide que celui par sélection). J'ai fait aussi le quick sort, je le joins aussi du coup
Code:

1 2 3 >>> def tri_rapide(l): if l==[]:return [] return (tri_rapide([x for x in l[1:]if x<l[0]])+[l[0]]+tri_rapide([x for x in l[1:]if x>=l[0]]))
puis, pour en évaluer le temps d'exécution :
Code:

1 2 3 4 5 >>> def temps(l): tps=time.clock() L=tri_rapide(l) duree=time.clock-tps return duree
A bientôt :)

1 pièce(s) jointe(s)

Bonjour,

j'ai recopié et testé tes fonctions. J'ai fait les courbes sur des listes aléatoires de différentes tailles (abscisse), en prenant la moyenne de temps (ordonnée) sur 10 essais, et j'obtiens ces courbes:
Pièce jointe 492760

Je ne sais donc pas quels tests tu as fait pour obtenir tes résultats, mais les résultats semblent tout à fait normaux.

Voici le code final pour mes tests. J'ai repris tes fonctions et restructuré un peu pour rendre plus lisible:

Code:

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import time
import random
import matplotlib.pyplot as plt
 
 
def maxi(l,n):
    indice=0
    for i in range(n):
        if l[i]>l[indice]:
            indice=i
    return [l[indice],indice]
 
def tri_selec(l):
    tps = time.clock()
    i = len(l) - 1
    while i>0:
        j = maxi(l, i+1)[1]
        if j != i:
            l[j], l[i] = l [i], l[j]
        i -= 1
    duree = time.clock() - tps
    return l, duree
 
 
 
def insertion(l,n):
    while n>0 and l[n]<l[n-1]:
        l[n-1],l[n]=l[n],l[n-1]
        n-=1
    return l
 
def tri_inser(l):
    tps = time.clock()
    n = len(l)
    for i in range(1, n):
        l = insertion(l, i)
    duree = time.clock() - tps
    return l, duree
 
 
 
def tri_rapide(L):
    tps = time.clock()
    def tri_aux(l):
        if l==[]:
            return []
        return tri_aux([x for x in l[1:] if x<l[0]]) + \
            [l[0]] + \
            tri_aux([x for x in l[1:] if x>=l[0]])
    L = tri_aux(L)
    duree = time.clock()-tps
    return L, duree
 
 
 
def liste_alea(n):
    return [random.randint(0, 1000) for _ in range(n)]
 
def courbes(m, n):
    X = range(n)
    Y = [(sum(tri_selec(liste_alea(x))[1] for _ in range(m)) / m) for x in X]
    plt.plot(X, Y)
    Y = [(sum(tri_inser(liste_alea(x))[1] for _ in range(m)) / m) for x in X]
    plt.plot(X, Y)
    Y = [(sum(tri_rapide(liste_alea(x))[1] for _ in range(m)) / m) for x in X]
    plt.plot(X, Y)
    plt.legend(['selec', 'inser', 'rapide'])
    plt.show()

Ensuite, je me suis abstenu de faire quelques petites optimisations possibles, mais rien de bien important vu les résultats normaux des courbes. Néanmoins, un petit rappel, modifier une liste en paramètre dans une fonction la modifie également à l'extérieur. Pas besoin de la retourner.

22/07/2019, 14h39
Cantorine

Merci AbsoluteLogic

Merci beaucoup pour cette aide précieuse.
Dans un livre, j'avais lu que le tri par sélection était moins rapide que le tri par insertion.
Je suis donc soulagée que visiblement le livre dit faux et que mes programmes sont corrects.
Merci d'avoir travaillé avec mes codes, je vais pouvoir aussi exploiter la partie avec la représentation graphique :)
Bonne journée