Pourquoi mon code est-il lent ?

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour,

J'ai commencé aujourd'hui un code python pour dessiner des fractales, en me basant sur les ensembles de Julia. Même conceptuellement, il peut y avoir des erreurs. Pour l'instant je refuse de regarder les codes dispos en ligne pour me forcer à réfléchir un peu plus.

Il me reste de bien nombreuses choses à faire, mais pour l'instant, je voulais voir le résultat en utilisant simplement $z^2-1=0$. Du coup, je l'ai tracé sur un million de pixels. J'ai décidé de calculer jusqu'au 8ème terme de la série. Donc ça fait quand même beaucoup de calculs, mais ça reste raisonnable. C'est un nombre que je peux évidemment réduire, mais j'aimerais déjà accelerer le code sans toucher à ce paramètres, si possible.

Je vous joins le code ci-après. Il n'est pas très long et devrait être assez facile à comprendre.

J'ai bien quelques idées, comme le fait que je reprogramme les opérations complexes au lieu d'utiliser une librairie toute faite. Je pourrais aussi choisir de colorer le pixel directement, au lieu de colorer un carré d'un pixel de coté, mais le faire comme ça me permet de faire des tests avec bien moins de points. J'ai aussi quelques importations inutiles.

En gros, est-ce que je fais quelque chose qui ralentit fortement l'execution du code, ou est-ce que c'est seulement dû au sujet ? Je rajoueterai aussi que mes connaissances en Python sont extrêmement limitées, mais j'essaierai de comprendre vos réponses.

  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
import sys,  math, random, os
from graphics import *

#Parameters

 #Complex numbers tested
Xmin=-2
Xmax=+2
Ymin=-1
Ymax=+1

Xsampling=1000
Ysampling=1000

 #Image
ImageWidth=1000
ImageHeight=1000

Convmin=0.01
Convmax=1.5
Repetitions=8

 #Enter it as C0+C1X+C2X2+...
Equation=[-1,0,1]

 #Not yet used
Color1=[255,0,0]
Color2=[130,0,130]

#Variables
Xrec=ImageWidth/(2*Xsampling*1.0)
Yrec=ImageHeight/(2*Ysampling*1.0)


#Define complex mathematics
def ComplexAddition(nb1,nb2):
  return [nb1[0]+nb2[0],nb1[1]+nb2[1]]

def ComplexMultiplication(nb1,nb2):
  return [nb1[0]*nb2[0]-nb1[1]*nb2[1],nb1[0]*nb2[1]+nb1[1]*nb2[0]]

def ComplexNorm(nb):
  return math.sqrt(nb[0]*nb[0]+nb[1]*nb[1])

def ComplexPower(nb,power):
  if power==0:
    return [1,0]
  else:
    if power==1:
      return nb
    else:
      return ComplexMultiplication(nb,ComplexPower(nb,power-1))

def ComplexEquation(eq,nb):
  order=0
  result=[0,0]
  for coeff in eq:
    result=ComplexAddition(result,ComplexMultiplication([coeff,0],ComplexPower(nb,order)))
    order=order+1
  return result

def ComplexEquationIteration(eq,nb,Repetitions):
  if Repetitions==0:
    return nb
  else:
    return ComplexEquationIteration(eq,ComplexEquation(eq,nb),Repetitions-1)


#Operations on the graphics
def GetPointCoordinates(nb):
  x=(nb[0]-Xmin)/(Xmax-Xmin*1.0)*ImageWidth
  y=(nb[1]-Ymin)/(Ymax-Ymin*1.0)*ImageHeight
  return [x,y]

def ColorAroundPoint(nb,color):
  nb2=GetPointCoordinates(nb)
  r=Rectangle(Point(nb2[0]-Xrec,nb2[1]-Yrec),Point(nb2[0]+Xrec,nb2[1]+Yrec))
  r.setFill(color)
  r.setOutline(color)
  r.draw(fig)

def Color(nb):
  if ComplexNorm(ComplexEquationIteration(Equation,nb,Repetitions)) < Convmax:
    return 'blue'
  else:
    return 'black'


# Main part of the program
fig = GraphWin("My Fractal", ImageWidth, ImageHeight)

for x in range(Xsampling+1):
  for y in range(Ysampling+1):
    X=Xmin+x/(Xsampling*1.0)*(Xmax-Xmin)
    Y=Ymin+y/(Ysampling*1.0)*(Ymax-Ymin)
    ColorAroundPoint([X,Y],Color([X,Y]))


fig.getMouse() # pause for click in window
fig.close()

Merci !

Édité par Rockaround

Staff

Cette réponse a aidé l'auteur du sujet

Il faudrait profiler le code pour être sûr, mais déjà à première vue, ce code crée beaucoup de listes inutilement. Je le ferais bien mais je ne sais pas quelle bibliothèque tu utilises…

Je pense que ton code gagnerait à la fois en lisibilité et en vitesse si tu utilisais tout bêtement une paire de variables real et img au lieu de listes, et que tu retournais des paires (return real, img).

Je pense que la troisième ligne de la boucle (où tu dessines effectivement la figure) doit probablement ponctionner aussi un bon nombre d'opérations.

Par contre d'un point de vue lisibilité pure, je t'encourage vraiment à lire et respecter la PEP-08.

I was a llama before it was cool

+0 -0
Staff

Cette réponse a aidé l'auteur du sujet

for x in range(Xsampling+1): for y in range(Ysampling+1):

je vois déjà une boucle au carré (qui d'ailleurs serait admirablement remplaçable par for x,y in itertools.product(range(Xsampling + 1), range(Ysampling + 1)) il me semble) de $10^6$ itérations. On devrait donc être aux alentours de 10/20 secondes d'exécutions.

Mais le pire vient clairement que tu fais un draw à chaque itération. Ce que ton processeur ne doit pas trop aimer.

+0 -0
Auteur du sujet

Merci pour ces commentaires. J'avais essayé de mettre les deux boucles en une, sans connaître itertools, mais ca n'avait pas fonctionné.

Si je ne trace pas à chaque fois, il faut que je stocke tout quelque part, et que je lance de toute facon tous les draws à la fin. Je vois mal comment je vais gagner au change. Ou alors il faut que je traite les données pour voir si j'ai des pixels de même couleur à coté, pour pouvoir tracer un rectangle plus grand ?

L'utilisation des deux variables au lieu du tableau est complètement faisable. J'essaierai. Pour la bibliothèque, si tu ne parles pas des premières lignes du code, aucune idée. J'utilise python 2.7 (il me semble, je n'ai pas accès à l'ordinateur où j'ai programmé avant demain) qui est installé par défaut sur Ubuntu. J'ai dû rajouter la lib graphics.py.

J'implémenterai vos suggestions dans les prochains jours. J'en profiterai pour jeter un oeil à la PEP-08, et essayer de lancer un profilage.

Merci

Staff

Si je ne trace pas à chaque fois, il faut que je stocke tout quelque part, et que je lance de toute facon tous les draws à la fin. Je vois mal comment je vais gagner au change.

Rockaround

Quand tu calcules puis trace et recommence, le processeur doit attendre le système graphique avant de continuer. Ça introduit un temps mort. Et puis rester à l'intérieur du processeur permet de tirer parti du cache etc. A voir comment ça fonctionne vraiment en Python par contre.

+0 -0
Staff

Cette réponse a aidé l'auteur du sujet

Voilà comment moi je le ferais :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def ColorAroundPoint(nb,color):
  nb2=GetPointCoordinates(nb)
  r=Rectangle(Point(nb2[0]-Xrec,nb2[1]-Yrec),Point(nb2[0]+Xrec,nb2[1]+Yrec))
  r.setFill(color)
  r.setOutline(color)
  yield r

def Color(nb):
  if ComplexNorm(ComplexEquationIteration(Equation,nb,Repetitions)) < Convmax:
    return 'blue'
  else:
    return 'black'

# Main part of the program
fig = GraphWin("My Fractal", ImageWidth, ImageHeight)

def get_all_rect():
    for x,y in itertools.product(range(Xsampling + 1), range(Ysampling+1)):
        X=Xmin+x/(Xsampling*1.0)*(Xmax-Xmin)
        Y=Ymin+y/(Ysampling*1.0)*(Ymax-Ymin)
        yield ColorAroundPoint([X,Y],Color([X,Y]))

for r in list(get_all_rect()):  # list() force à tout exécuter avant d'entrer dans la boucle
    r.draw(fig)

Édité par artragis

+1 -0
Auteur du sujet

Bonjour,

J'ai donc commencé à implémenter vos suggestions. Avant de donner les résultats, j'ai remarqué que les premiers rectangles vont beaucoup plus vite à tracer que les suivants. Une raison pour ça ? Si oui, je peux peut-être trouver une optimisation venant de cet effet. Pour le même nombre de rectangles, on passe de 10-15 secondes au début à environ 2 minutes à la fin.

Concernant les ressources, python utilise l'équivalent de 100% d'un cpu, mais réparti en 4*25%, sur 4 cpus. est-ce possible d'augmenter ces pourcentages ?

Maintenant, les résultats. J'ai implémenté vos suggestions une à une pour bien se rendre compte. Le cas que j'ai lancé nest pas le même que dans le code du premier message (discrétisation différente).

Pour tout tracer à la fin, le code ne fonctionnait pas. J'ai changé la dernière ligne, de r.draw(fig) en r.next().draw(fig) qui tourne. Je n'avais jamais entendu parlé de générateurs avant, du coup je n'aurais peut-être pas du faire ça.

Optimisation Temps (s) 350x350 gain (%) Temps (s) 200x200 gain(%)
Aucune 777 - 131(30) -
Itertools 804 -3.5 131(30) 0
Tout tracer à la fin 895 (300) -11.3 131(28) 0
2 var Au lieu d'un tableau - - - -

Entre parenthèses, je mets le temps nécessaire pour arriver à la moitié du tracé.

Je n'ai pas encore fait la modification suggérée par Nohar, puisqu'en traçant tout à la fin, j'ai pu voir que les calculs me prennent 5 secondes, et que tracer ensuite m'en prend 890. Ce qui veut dire que les calculs sont 0.6% du temps.

Un problème avec la bibliothèque utilisée ?

Merci encore

Staff

OK, c'est ça qu'un profiling aurait pu montrer tout de suite.

Je te recommande de jeter un oeil aux module profile/cProfile (inclus dans la bibliothèque standard) et line_profiler (dispo sur le Pypi, donc installable avec pip). En général, j'utilise profile pour identifier le goulot d'étranglement, puis je bosse ensuite avec line_profiler quand j'ai identifié la/les fonctions qui bouffent le plus de temps.

Pour ton problème actuel, visiblement si le calcul prend 0.6% du temps, ton problème principal vient soit de ta façon de dessiner le fractale, soit de la bibliothèque graphique que tu utilises. C'est laquelle ?

Édité par nohar

I was a llama before it was cool

+1 -0
Auteur du sujet

J'utilise graphics.py, et pour tracer, un rectangle à la fois, donc les deux points diagonaux sont calculés avant (je suppose au moins. J'ai une ligne r=Rectangle(Point(nb2[0]-Xrec,nb2[1]-Yrec),Point(nb2[0]+Xrec,nb2[1]+Yrec)), je ne suis pas sûr du fonctionnement, mais les expressions sont évaluées directement, non?)

Je ferai le profiling plus tard.

Staff

OK, je vois. Tu utilises une surcouche de tkinter, ce qui est effectivement plutôt moyen niveau perfs : elle n'est pas faite pour ça. :)

Il y a sûrement moyen de faire mieux, en utilisant une bibliothèque plus performante (pyglet, peut-être ? ou Pygame ? ou plus simplement Pillows ?) qui te permette de dessiner efficacement avant d'afficher l'image.

Édité par nohar

I was a llama before it was cool

+0 -0

Cette réponse a aidé l'auteur du sujet

Je me pose une question par rapport aux nombres complexes : sais-tu que Python sait les gérer nativement ? Je ne dis pas que ça augmenterait les performances (il y a des chances vu que tu ne créerais plus autant de listes), mais ça assurerait une meilleure lisibilité du code.

1
2
3
4
>>> x = 5
>>> y = 8
>>> x + y * 1j
(5+8j)
Staff

Ah tiens j'avais complètement zappé que Python gérait les complexes. En fait ça ferait bien plus qu'optimiser le code : ça supprimerait deux fonctions inutiles (addition et multiplication complexes). L'impact en perfs devrait être assez sensible sur le temps de calcul de l'image (mais négligeable au total).

Édité par nohar

I was a llama before it was cool

+0 -0
Auteur du sujet

Je n'ai pas encore eu le temps de changer de biblio pour la partie graphique, qui est donc toujours très lente, mais en utilisant l'implémentation native des nombres complexes, je suis passé de 40 secondes à 13 secondes pour les calculs sur 1000*1000 pixels. Avec un autre changement sur l'algo, je le ramène à 8 secondes, ce qui me semble pas mal. merci !

Je changerai de biblio prochainement.

Auteur du sujet

Je me permets de reposter, pour vous dire que mon problème est résolu. Merci à vous quatre ! Le passage à pillow et l'utilisation des nombres complexes ont grandement amélioré les choses.

Le cas à 350x350 rectangles, qui prenait 12-14 minutes prend maintenant moins de 5 secondes.

Le cas à 1000x1000 rectangles, que j'avais dû laisser tourner la nuit pour le finir, prend maintenant 19 secondes.

Édité par Rockaround

Staff

Cette réponse a aidé l'auteur du sujet

:)

J'en profite juste pour rebondir sur ce passage d'un post plus haut :

Concernant les ressources, python utilise l'équivalent de 100% d'un cpu, mais réparti en 4*25%, sur 4 cpus. est-ce possible d'augmenter ces pourcentages ?

Cette limite des 100% de CPU est celle du GIL. Le seul moyen assez simple (compte tenu de la nature de ton code) que tu puisses mettre en oeuvre pour augmenter la charge CPU est de paralléliser ton calcul entre plusieurs processus grâce au module standard multiprocessing.

Il existe d'autres méthodes qui permettent de dépasser ces 100% dans un contexte multithread, mais à l'heure actuelle (en attendant les subinterpreters de python 3.6), elles impliquent toutes d'écrire ton module en C ou avec Cython et son context manager with nogil:. Ça se fait bien mais c'est vraiment une artillerie lourde à ne sortir que lorsque tout le reste ne suffit pas.

Édité par nohar

I was a llama before it was cool

+1 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte