Discussion :

[cal23]

Bonjour.
J'ai programmé une interface graphique pour représenter un tri à bulles.
J'ai un problème au niveau de la rapidité : c'est très lent par rapport à la valeur que j'ai mise dans la méthode after:

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
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
# -*- coding: latin-1 -*-
"""
Created on Sun Oct 23 17:45:08 2016
 
@author: Jean-Christophe
"""
 
from random import shuffle
from Tkinter import *
from tkFont import Font
 
def liste_aleatoire(taille):
    """ crée une liste aléatoire d'entiers distincts entre 0 et taille """
    liste = range(taille)
        #Attention: la fonction shuffle ne renvoie rien:
        #elle agit directement sur liste_a_trier
    shuffle(liste)
    return liste
 
 
def tri_bulles(liste):
    """ Trie la liste avec la méthode du tri à bulles 
    et stocke chaque changement dans la liste liste_deplacements, qui est renvoyée """
 
    liste_deplacements = []
    echange_effectue=True
    #Tant qu'au moins un échange a été effectué, on continue
    while echange_effectue:
        echange_effectue = False
        #On parcourt la totalité du tableau à chaque fois
        for j in range(len(liste)-1):
            if liste[j]>liste[j+1]:
                #Si liste[j]>liste[j+1], on les échange
                liste[j], liste[j+1] = liste[j+1], liste[j]
                #Si au moins un échange a été effectué, echange_effectue passe à True
                echange_effectue = True
                liste_deplacements.append([j,liste[j]])
                liste_deplacements.append([j+1, liste[j+1]])
    return liste_deplacements       
 
def initialise_liste():
    """ Initialise la liste et lance l'animation """
    global liste_deplacements, indice_liste_deplacements, liste_bulles
 
    canevas.delete("all")
    label_resultat.config(text="")
    liste_a_trier = liste_aleatoire(taille)
    liste_bulles = []
    for i in range(taille):
        liste_bulles.append(canevas.create_oval(i*5-2+10, HAUTEUR_CANEVAS-(liste_a_trier[i]*5-2+10), i*5+2+10, HAUTEUR_CANEVAS-(liste_a_trier[i]*5+2+10), fill='red'))
    liste_deplacements = tri_bulles(liste_a_trier)
    indice_liste_deplacements = 0
    #bouton_animation.config(state=DISABLED)
    tri_bulles_dessin()
 
def tri_bulles_dessin():
    global indice_liste_deplacements
    """ fonction récursive qui dessine les déplacements des bulles """
    j = liste_deplacements[indice_liste_deplacements][0]
    yj = liste_deplacements[indice_liste_deplacements][1]
    canevas.coords(liste_bulles[j],j*5-2+10, HAUTEUR_CANEVAS-(yj*5-2+10), j*5+2+10, HAUTEUR_CANEVAS-(yj*5+2+10))
    indice_liste_deplacements += 1
    if indice_liste_deplacements <len(liste_deplacements):
        fenetre.after(1,tri_bulles_dessin)
    else:
        bouton_animation.config(state=NORMAL)
        label_resultat.config(text="Il y a eu {} échanges.".format(len(liste_deplacements)/2))
 
 
#Interface graphique *****************************************************************************
LARGEUR_CANEVAS = 700
HAUTEUR_CANEVAS = 500
 
def clic_listbox_taille(event):
    global taille
    taille = listbox_taille.get(listbox_taille.curselection())    
    bouton_animation.config(state=NORMAL)
 
 
fenetre = Tk()
fenetre.resizable(width=False, height=False)
# Panneau au nord qui contient la liste et le bouton
panneau_nord = Frame(fenetre)
panneau_nord.pack(side="top")
 
#Panneau qui contient la liste des tailles 
panneau_taille = Frame(panneau_nord, relief=RIDGE, borderwidth=2)
panneau_taille.pack(side="left", padx=5, pady=5, ipadx=10, ipady=10)
label_taille = Label(panneau_taille, text="Taille de la liste")
label_taille.pack(side="top")
panneau_listbox_taille = Frame(panneau_taille)
scrollbar_taille = Scrollbar(panneau_listbox_taille)
listbox_taille = Listbox(panneau_listbox_taille, height=1, width=4, exportselection=0)
listbox_taille.insert(0, *range(40,140,10))
scrollbar_taille.config(command=listbox_taille.yview)
listbox_taille.bind('<ButtonRelease-1>', clic_listbox_taille)
listbox_taille.config(yscrollcommand=scrollbar_taille.set)
listbox_taille.pack(side="left", fill=Y)
scrollbar_taille.pack(side="left", fill=Y)
panneau_listbox_taille.pack(side="top")
 
 
#Panneau qui contient le bouton
panneau_bouton = Frame(panneau_nord, relief=RIDGE, borderwidth=2)
bouton_animation = Button(panneau_bouton, text="Animation", command=initialise_liste, state=DISABLED)
bouton_animation.pack(side="top", expand=1, anchor=CENTER, pady=5)
panneau_bouton.pack(side="left", fill=Y, padx=5, pady=5, ipadx=20, ipady=10)
 
#Canevas
canevas = Canvas(fenetre, width=LARGEUR_CANEVAS, height=HAUTEUR_CANEVAS, bg='white', border=2, relief=SUNKEN)
canevas.pack(side="top", padx=30, pady=20)
 
#Panneau qui contient le nombre d'échanges
panneau_sud = Frame(fenetre, height=50, bg='white', relief=SUNKEN, borderwidth=2)
police_resultat = Font(family='Times', size=16, weight='bold')
label_resultat = Label(panneau_sud, text="", font=police_resultat, bg='white')
label_resultat.pack(anchor=W, padx=20)
panneau_sud.pack(side="top", expand=1, fill="x", padx=30, pady=20)
 
fenetre.mainloop()

Quand on appuie sur le bouton Animation, la fonction initialise_liste est exécutée; elle appelle la fonction tri_bulles qui stocke dans une liste tous les déplacements des bulles.
Ensuite, la fonction récursive tri_bulles_dessin est appelée et affiche le déplacement des bulles dans le canvas.
Le résultat est beaucoup trop lent par rapport à la valeur de 1ms dans la méthode after.
Si on appuie plusieurs fois de suite sur le bouton Animation, ça accélère

J'ai testé sur plusieurs ordinateurs: même résultat.
A quoi ça peut être dû ?
merci.

[wiztricks]

Salut,

Ensuite, la fonction récursive tri_bulles_dessin est appelée et affiche le déplacement des bulles dans le canvas.
Le résultat est beaucoup trop lent par rapport à la valeur de 1ms dans la méthode after.
Si on appuie plusieurs fois de suite sur le bouton Animation, ça accélère

1 ms, c'est très petit et vous n'êtes pas dans un environnement temps réel: de temps en temps, le système d'exploitation va suspendre l'exécution de votre programme pendant quelques dizaines de Ms parce qu'il distribue le CPU aux différents programmes/processus en attente. Donc en gros, si vous arrivez à afficher un déplacement toutes les 3-5 Ms en moyenne, c'est pas si mal et si vous avez des centaines de déplacements, la durée sera en nombre de secondes.
Compte tenu de la persistance rétinienne, çà ne changera pas grand chose d'effectuer 20 déplacements toutes les 20 Ms.

Lorsque vous appuyez plusieurs fois sur animation, vous appelez tri_bulles_dessin encore une fois. çà bouge plus vite car vous avez maintenant plusieurs tri_bulles_dessin qui se déclenchent dans l'intervalle.

- W

[cal23]

Bonjour. J'avais mis 1ms pour exagérer, je me doute bien que c'est trop court
Donc quand je clique plusieurs fois sur Animation, plusieurs processus sont lancés.
Alors pourquoi l'OS a du temps à donner à plusieurs processus (ce qui fait que ça va vite) et moins de temps quand il y en a un seul de lancé (plus lent)?
Je suis clair, là ?

[wiztricks]

Alors pourquoi l'OS a du temps à donner à plusieurs processus (ce qui fait que ça va vite) et moins de temps quand il y en a un seul de lancé (plus lent)?

L'OS donne du temps de calcul aux processus qui attendent pour "calculer".
Si votre programme ayant le CPU exécute 3 instructions puis le rend en lui disant réveille moi dans 1 Ms, le CPU sera alloué à un autre processus. Ce n'est que lorsque le temps de calcul excède une certaine durée (quelques dizaines de Ms) que l'OS va suspendre (pré-empter) votre programme pour l'assigner à un autre programme qui est en attente de CPU.
note: attendre d'avoir le CPU et attendre que la ms soit écoulé sont des états différents.

- W

[cal23]

OK.
Si je mets par exemple 50ms, on voit bien que les bulles ne se déplacent pas toutes les 50ms (c'est plus lent).
Est-ce que c'est possible de demander plus de temps CPU pour ce processus ?

[wiztricks]

Si je mets par exemple 50ms, on voit bien que les bulles ne se déplacent pas toutes les 50ms (c'est plus lent).
Est-ce que c'est possible de demander plus de temps CPU pour ce processus ?

Vous avez le CPU... Le problème est que quand vous l'avez vous le rendez trop vite.
Faites plusieurs déplacements au lieu d'un seul lorsque vous avez le CPU résoudra votre problème (et visuellement vous ne verrez pas de différence sinon que çà ira plus vite).

- W