Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Nouveau Candidat au Club
    Femme Profil pro
    Enseignant
    Inscrit en
    juillet 2019
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Aube (Champagne Ardenne)

    Informations professionnelles :
    Activité : Enseignant
    Secteur : Enseignement

    Informations forums :
    Inscription : juillet 2019
    Messages : 3
    Points : 1
    Points
    1

    Par défaut 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 ??
    Nom : Capture d’écran 2019-07-22 à 09.13.22.png
Affichages : 158
Taille : 19,8 KoNom : Capture d’écran 2019-07-22 à 09.13.35.png
Affichages : 158
Taille : 16,6 Ko

    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

  2. #2
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 821
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 821
    Points : 9 285
    Points
    9 285

    Par défaut

    Bonjour

    [Hors-sujet] Pourquoi ta boucle de gauche a pour condition while (i>0): plutôt que while (i>=0): ? [/Hors-sujet]
    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 ]
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  3. #3
    Nouveau Candidat au Club
    Femme Profil pro
    Enseignant
    Inscrit en
    juillet 2019
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Aube (Champagne Ardenne)

    Informations professionnelles :
    Activité : Enseignant
    Secteur : Enseignement

    Informations forums :
    Inscription : juillet 2019
    Messages : 3
    Points : 1
    Points
    1

    Par défaut

    Merci beaucoup pour te réponse rapide.
    Les deux algorithmes sont efficaces, ils trient bien les listes données en arguments.
    Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
    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 Python : Sélectionner tout - Visualiser dans une fenêtre à part
    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 Python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    >>> def temps(l):
    	tps=time.clock()
    	L=tri_rapide(l)
    	duree=time.clock-tps
    	return duree
    A bientôt

  4. #4
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    juillet 2018
    Messages
    41
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juillet 2018
    Messages : 41
    Points : 70
    Points
    70

    Par défaut

    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:
    Nom : Courbes.png
Affichages : 40
Taille : 53,4 Ko

    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 Python : 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
    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.

  5. #5
    Nouveau Candidat au Club
    Femme Profil pro
    Enseignant
    Inscrit en
    juillet 2019
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Aube (Champagne Ardenne)

    Informations professionnelles :
    Activité : Enseignant
    Secteur : Enseignement

    Informations forums :
    Inscription : juillet 2019
    Messages : 3
    Points : 1
    Points
    1

    Par défaut 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

Discussions similaires

  1. [Python 3.X] Mesure temps d'exécution de 3 algorithmes de tri et création de graphique.
    Par redplayer dans le forum Général Python
    Réponses: 4
    Dernier message: 29/10/2017, 19h25
  2. Réponses: 2
    Dernier message: 24/04/2011, 08h43
  3. Temps d'exécution d'un algorithme génétique
    Par debalgo dans le forum Intelligence artificielle
    Réponses: 1
    Dernier message: 24/03/2011, 00h53
  4. Réponses: 1
    Dernier message: 24/02/2009, 21h31
  5. [TP] Mesure du temps d'exécution d'un algorithme
    Par williamdunord dans le forum Turbo Pascal
    Réponses: 19
    Dernier message: 18/05/2007, 06h47

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo