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

Algorithmes et structures de données Discussion :

Temps d'exécution d'un algorithme


Sujet :

Algorithmes et structures de données

  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 : 341
Taille : 19,8 KoNom : Capture d’écran 2019-07-22 à 09.13.35.png
Affichages : 335
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
    4 013
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 013
    Points : 9 865
    Points
    9 865
    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.

  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
    46
    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 : 46
    Points : 71
    Points
    71
    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 : 70
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, 20h25
  2. Réponses: 2
    Dernier message: 24/04/2011, 09h43
  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, 01h53
  4. Réponses: 1
    Dernier message: 24/02/2009, 22h31
  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, 07h47

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