Pourquoi mon code est-il lent ?

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 !

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

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.

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.

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

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 ?

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.

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.

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).

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.

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.

En effet, vu la nature de mon code, en deux lignes openmp, c'est fait (si c'est aussi simple qu'en C). Je le ferai peut-être à la fin, quand j'aurai fini d'implémenter les fonctions que je veux.

Merci encore