Discussion :

[deusyss]

Bonjour à tous.

Je suis en train d'écrire un script dont j'aimerais optimiser la vitesse d'exécution. J'ai ce tableau:
[ [[x0,y0,z0],[x1,y1,z1],[x2,y2,z2]]
...
[xN,yN,zN]]]
(bref une matrice créée à partir d'un tableau) ; ou N est totalement variable, pour mes tests, N vaut 3326. Ce tableau abrite les coordonnées spatiales de points permettant de créer des triangles, puis par assemblages des triangles, une pièces en 3D (format STL, voir wiki anglais pour les curieux).

Je scanne l'ensemble du fichier, triangle après triangle (XN à XN+2) et effectue des calculs sur chaque triangle (temps de calcul négligeable: juste quelques additons et multiplications)

Mon problème est dans le temps d'exécution. Au début du programme, je scanne près de 2 triangles par seconde (c'est déjà pas trop rapide, mais c'était deux à trois fois pire avec l'ancien algo), mais vers la fin, il me faut plusieurs seconde par triangle.

J'aurais aimé savoir si quelqu'un savait d'où pouvait venir ce ralentissement qui apparait au fur et à mesure, et aussi si j'aurai éventuellement un vrai gain en utilisant numpy (mes premiers essais numpy avec l'ancien algorithme était cependant catastrophique).

Je vous remercie d'avance pour votre aide et vos conseils à venir

[rambc]

Bonjour,
il faudrait regarder ce que cela donne avec numpy.

[Tyrus]

Ça va être difficile de t'aider sans un bout de code

[deusyss]

Merci pour vos réponses. J'ai essayé avec numpy, mais ce fut une catastrophe, aucun gain, bien au contraire. Tout le code ça serait long, mais je peut vous en mettre la partie concernée


tabletemp est créé comme suis, dans une boucle dont je ne peut me passer:
tabletemp.append([[x1,y1,z1],[x2,y2,z2],[x3,y3,z3]])

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
 
        x=y=0.0
        xtab=ytab=0
        xtabmax=int(5*xmax)
        ytabmax=int(5*ymax)
        N=xtabmax*ytabmax #on determine le nombre de point qu'il y a a scanné
        flagx=0
        z=0.0
        while (ytab<ytabmax):
            if (flagx <>1):
                while( xtab<xtabmax):
                    #print "E4 ", z
                    z=self.stl_z(tabletemp,x,y)
                    tablez.append([xtab,ytab,z])
                    x=x+0.2
                    xtab=xtab+1
                flagx=1
                xtab=xtab-1
            else:
                while (xtab>=0):
                    #print "E5 ", z
                    z=self.stl_z(tabletemp,x,y)
                    tablez.append([xtab,ytab,z])
                    x=x-0.2
                    xtab=xtab-1
                flagx=0
                xtab=0
            y=y+0.2
            ytab=ytab+1
            print ytab

et voici la fonction appelée:

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
    def stl_z(self,table, x=0.0, y=0.0):
        j=0
        z=zmax=0.0
        L=len(table)
        x1=y1=x2=y2=x3=y3=0.0
        tablez=[]
 
        while (j<L): #on scanne tout le fichier jusqu'a trouver le bon point
            y1=table[j][0][1]
            y2=table[j][1][1]
            y3=table[j][2][1]
 
            if ((y1<y and y2>y) or (y1<y and y3>y)or (y2<y and y1>y) or (y2<y and y3>y) or (y3<y and y1>y) or (y3<y and y2>y) or y1==y or y2==y or y3==y):
                x1=table[j][0][0]
                x2=table[j][1][0]
                x3=table[j][2][0]
                if ((x1<x and x2>x) or (x1<x and x3>x) or (x2<x and x1>x) or (x2<x and x3>x) or (x3<x and x1>x) or (x3<x and x2>x)or x1==x or x2==x or x3==x):
                    value=self.triangle(x1,x2,x3,y1,y2,y3,x,y)
                    if (value==TRUE):
                        z1=table[j][0][2]
                        z2=table[j][1][2]
                        z3=table[j][2][2]
                        z=self.z_plan3D(x1,y1,z1,x2,y2,z2,x3,y3,z3,x,y)
                        tablez.append(z)
            j=j+1
 
        i=0
        L2=len(tablez)
        while (i<L2):
            if (tablez[i]>zmax):
                zmax=tablez[i]
            i=i+1
        return zmax

voilà, juste ces parties de code, sa représente 90 à 95% du temps d'exécution de mon code (la fonction z_plan3D consiste en une série de quelques soustraction et multiplication; et en la chuntant, le gain n'est pas visible, idem pour la fonction triangle).

J'espère qu'on aboutira a une solution. Merci pour votre aide

[miawaw]

Hello,

J'ai l'impression que tu n'es pas encore habitué au style de python (je me trompe peut-être). Je crois que tu peux réécrire la 2eme fonction que tu as donnée de la manière suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
def stl_z(self,table, x=0.0, y=0.0):
    tablez=[]
    for [[x1,y1,z1],[x2,y2,z2],[x3,y3,z3]] in table:
        if (min(x1,x2,x3) <= x <= max(x1,x2,x3)) \
            and (min(y1,y2,y3) <= max(y1,y2,y3)) \
            and self.triangle(x1,x2,x3,y1,y2,y3,x,y):
                tablez.append(self.z_plan3D(x1,y1,z1,x2,y2,z2,x3,y3,z3,x,y))
    if tablez: # si la liste tablez n'est pas vide
        return max(tablez)
    else: # la liste tablez est vide
        # erreur, retourner une valeur abérrante ou lancer une exception

En python, on ne doit pas déclarer des variables (mais il faut faire attention au 'scope' de la variable).

Dans la première fonction, on dirait que tu effectues alternativement une boucle avec une variable x qui va de 0 à 0.2*(xtabmax-1) et puis une autre boucle avec x qui va de 0.2*(xtabmax-1) à 0.
Tu pourrais t'en sortir avec une grande boucle qui a moins d'itérations, et sans 'flagx':

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
xtabmax=int(5*xmax)
ytabmax=int(5*ymax)
N=xtabmax*ytabmax
for ytab in range(0, ytabmax, 2): # 0, 2, 4, ..., ytabmax - 1 (ou ytabmax - 2) car on fait deux petites boucles dans un seul passage de boucle
    for xtab in range(xtabmax):
        z=self.stl_z(tabletemp,xtab * 0.2,y)
        tablez.append([xtab,ytab,z])
    y += 0.2
    print ytab
    for xtab in reversed(range(xtabmax)):
        z=self.stl_z(tabletemp,xtab * 0.2,y)
        tablez.append([xtab,ytab,z])
    y += 0.2
    print ytab + 1

Faudrait vérifier les bornes dans les boucles ci-dessus.
Il y encore moyen d'optimiser mais je crois que ça fais avancer le schmilblick.
bye

[miawaw]

j'ai oublié un y quelque part:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 ... and (min(y1,y2,y3) <= y<= max(y1,y2,y3)) ... \

[deusyss]

Bonsoir, et bien vu Miawaw

Effectivement, cela ne fait qu'une semaine que je fais du python. Auparavant j'étais plus basic/C/vb.net. C'est vrai que le for in n'est pas encore trop un réflexe, mais j'apprends jour après jour.

Effectivement vu comme ça c'est beaucoup plus propre. Qu'est ce que le "scope variable"? Je n'en ai jamais entendu parler. Concernant le x qui croit puis décroit, c'est pas une obligation, mais sa peut me servir pour plus tard donc, je préfère garder

Je fais le test et...ya un léger gain. Sur les 30 premier points de mon fichier de test, on gagne 7/8 secondes. Bon extrapoler sur un fichier complet... (pr celui de tests, on gagne 6-7mn d'après mes calculs, mais sur un total de 4h)

Quoiqu'il en soit, merci beaucoup quand même, car si le gain n'est pas énorme, au moins, j'apprends sur la façon d'écrire le code.

La route ne s'arrête pas là, mais on avance.

[deusyss]

Re-bonsoir,

Bon, je repasse pour dire que j'ai fais quelque tests supplémentaires sur le code corrigé pour plus ciblé la source de mon problème.

Bon alors le problème semble venir, du moins la plus grosse partie du code suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
    def stl_z(self,table, x=0.0, y=0.0):
        tablez=[]
        for [x1,y1,z1,x2,y2,z2,x3,y3,z3] in table:
            if (min(x1,x2,x3) <= x <= max(x1,x2,x3)) and (min(y1,y2,y3) <= y <= max(y1,y2,y3)) and (self.triangle(x1,x2,x3,y1,y2,y3,x,y)):
                    tablez.append(self.z_plan3D(x1,y1,z1,x2,y2,z2,x3,y3,z3,x,y))
        if tablez: # si la liste tablez n'est pas vide
            return max(tablez)
        else: # la liste tablez est vide
            return 0

Voici donc la fonction à réellement optimisée, j'ai changé la façon dont je créé mon tableau ( de [[x1,y1,z1],[x2,y2,z2], [x3,y3,z3],] à [x1,y1,z1,x2,y2,z2,x3,y3,z3] pensant gagné en performance, mais rien. Quelqu'un a une idée?

[dividee]

table_z est inutile; tu peux calculer le maximum à la volée:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
    def stl_z(self,table, x=0.0, y=0.0):
        z_max = None
        for [x1,y1,z1,x2,y2,z2,x3,y3,z3] in table:
            if (min(x1,x2,x3) <= x <= max(x1,x2,x3)) and (min(y1,y2,y3) <= y <= max(y1,y2,y3)) and (self.triangle(x1,x2,x3,y1,y2,y3,x,y)):
                z = self.z_plan3D(x1,y1,z1,x2,y2,z2,x3,y3,z3,x,y)
                if z_max < z : z_max = z # ou z_max = max(z,z_max) il faudrait tester si c'est plus rapide
        return z_max

Suivant la vitesse relative de z_plan3D et des différents tests, il pourrait être plus rapide de calculer z en premier, ce qui permet de le rejeter sans tester les autres conditions s'il n'est pas supérieur au meilleur z trouvé jusque là:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
    def stl_z(self,table, x=0.0, y=0.0):
        z_max = None
        for [x1,y1,z1,x2,y2,z2,x3,y3,z3] in table:
            z = self.z_plan3D(x1,y1,z1,x2,y2,z2,x3,y3,z3,x,y)
            if z_max < z and (min(x1,x2,x3) <= x <= max(x1,x2,x3)) and (min(y1,y2,y3) <= y <= max(y1,y2,y3)) and (self.triangle(x1,x2,x3,y1,y2,y3,x,y)):
                z_max = z
        return z_max

Maintenant, si z_plan3D est 10 fois plus lentes que les autres tests réunis, ce ne sera pas une bonne idée... Le gain (ou la perte) dependra également des données. Il est peut-être (?) possible d'ordonner table à l'avance, afin de maximiser les chances d'obtenir un z élevé dès le début, ce qui accélérerait cette version de l'algorithme.

Si les méthodes z_plan3D et triangle sont courtes, il serait certainement intéressant de les "inliner", c'est à dire de recopier leur corps dans la fonction stl_z afin d'éviter un appel de méthode. Le coût d'un appel de méthode en Python n'est pas négligeable.

[deusyss]

Bonsoir!!!!!

J'ai testé les deux fonctions Dividee. La première est plus efficace que la première, mais au niveau timing, pas de changement . Mais bon, c'est en essayant qu'on arrive. Cependant, je me demande si je peut réellement améliorer la vitesse de mon code.

Pour ça, il faudrait réussir a scanner plusieurs milliers de triangles très rapidement. J'estime que 5 a 10 mn serait acceptable. A l'heure actuelle, sa oscille entre 2 et 4h, donc sa met pas mal de temps en plus de ce que je désire

Peut être que la méthode que j'utilise n'est pas bonne. Le tableau nommé "table" contient les coordonnées des points permettant de créer des triangles dans l'espace, et l'assemblage de ces triangles me donne ma pièce. il faudrait trier mes triangles dans le tableau pour optimiser les calculs. Une idée??

[dividee]

C'est effectivement le nombre élevé d'itérations qui tue les performances. Tu as décrit ce que contient la table, mais pas ce que fait ton code. Si tu expliques ce que fais le code, cela nous aidera à t'aider à trouver un meilleur algorithme, s'il y en a.

[deusyss]

Bonjour, je vais tacher de résumer l'action de mon code. Le but est de convertir un fichier STL (3D), en fichier dit depth maps, c'est à dire un fichier dont les couleurs varient du blanc au noir, et ou chaque nuance de gris correspond à une différente hauteur. Ce genre de fichier sert pour tout ce qui est fraiseuse numérique ou CNC, notamment dans linuxCNC EMC2.

Habituellement, ce genre de fichier se fabrique avec une methode complexe qui consiste à agir sur un ensemble de photos.

Mon script, lui, le fait a partir d'un fichier STL. On indique le chemin, les coordonnées des vertex de chaque triangles (les points formants les triangles) sont alors stockés dans un tableau. Ensuite j'appelle une fonction de scan.

Cette fonction de scan commence par déplacer le fichier 3D à l'origine, puis va scanner le fichier en y, puis en x (y=0, x de 0 a xmax / y=0.2, x de 0 à xmax...) afin de déterminer les differentes hauteur de z aux coordonnées demandées. Un tableau est alors généré comprenant la coordonnées des points et la hauteur z.

Par la suite, une fonction converti ces hauteur en niveau de gris puis génère une image.

Mon problème est le scannage du fichier qui me prend énormément de temps. Pour préciser mes explication, je joint ci dessous qulques images pour illustrer mes propos. Le résultat necessite 4h de calcul pour un fichier STL parmis les plus petit que j'ai.

Voilà, j'espère avoir été claire, aucun soucis pour redétailler si besoin

[dividee]

Bon, je m'y connais pas trop en 3D, mais il doit y avoir des algorithmes très efficaces pour cela. Ce qui me vient à l'idée:
* Si les surfaces sont fermées, tu peux éliminer tous les triangles dont la normale est orientée "vers l'arrière".
* Au lieu de scanner le plan comme pour du raytracing, tu peux "dessiner" chaque triangle un par un, en utilisant un Z-buffer. D'ailleurs c'est en fait un genre de Z-buffer que tu calcules.

Si tu pouvais demander au GPU de la carte graphique de le faire, je suis sûr qu'il te ferait ça en une fraction de seconde...

[rambc]

Bonjour,
il faudrait regarder ce que cela donne avec numpy.

Je me répète, je sais...

[deusyss]

Bonjour,

RAMBC, comme je l'i dit dans mes deux premiers posts, j'ai essayé avec numpy, à deux reprise, et sa ne m'apporte rien du tout, puisqu'au final, le code va encore plus lentement. Peut etre cela est du a une mauvaise utilisation, mais a l'heure actuelle du coup, je ne m'y attarde pas. J'ai lu sur internet que le gain était non negligeable mais pour moi, j'ai pas été convaincu

Dividee, ton idée d'utiliser les normales est terrible. J'y avait pas penser et effectivement, cela supprimerais à chaque fois plus de la moitié des triangles, entre ceux qui sont derrière, et ceux qui sont parallèle a l'axe z.

Pour le z buffer, je ne sait pas ce que c'est, mais je vais me renseigner pour voir. Merci de l'info.

EDIT: Je viens de regarde le z buffer, et c'est tout à fait ce que je veut, terrible, on apprend tous les jours. Je reviendrais vous dire ce qu'il en est dans mon script.

[rambc]

RAMBC, comme je l'i dit dans mes deux premiers posts, j'ai essayé avec numpy, à deux reprise, et sa ne m'apporte rien du tout, puisqu'au final, le code va encore plus lentement. Peut etre cela est du a une mauvaise utilisation

Qu'as-tu fait avec numpy ? As-tu essayé de "vectoriser" tes calculs ?

[deusyss]

Bonjour, rambc.

Pour repondre a ta question, avec numpy, j'ai créé un array, dans lequel j'ai mis mes valeurs, et je m'en suis servi ensuite comme je me sert du tableau. J'ai lu quelques pdf sur numpy, mais j'avoue sans honte que le concept de "vectorisation" m'echappe totalement, meme si je pense avoir qd meme compris qu'il s'agit d'effectuer une operation non pas élément par element, mais sur la totalité. J'ai lu aussi que mal utilisé numpy était pire que du python pur, et vu mes resultats je pense que je m'en sert mal, mais faute d'explications claires, j'utilise donc les tableaux

Si j'ai bien compris cela, du coup je ne voit pas trop comment "vectoriser" vu les opérations que j'effectue, mais je suis preneur d'explications et d'exemples pr comprendre ce principe qui a l'air fondamental en python.

Concernant le z-buffer, après renseignements pris sur le net je ne pense pas que cela me convienne. Le principe est celui que j'applique, mais apparemment, le z-buffer effectue son opération d'un point de vue fixe, afin d'effectuer un rendu comme l'oeil humain. De mon coté, il s'agit d'un scannage complet, d'où un petit problème...

Je n'ai pas le temps de refaire des essais pdt 2-3 jours, mais apres avoir discuter avec un ami, une solution supplémentaire apparait. il s'agirait dans le tableau des x, y, z, de rajouter les éléments composant l'equation du plan de chaque triangle, au lieu de la recalculer a chaque fois, meme si ce calcul est tres rapide et n'est pas effectuer systematiquement. Je suis pas sur que le gain soit enorme, mais bon sa serait eventuellement un petit plus.

[miawaw]

Hello

pour le 'scope' en question, je me suis peut-être planté.
En fait, en Java/C/C++ etc, il faut faire attention au bloc dans lequel on déclare une variable car elle n'existe pas en dehors

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
int ma_fonction(int n){
    if (n > 0)
        int x = 2 * n;
    else
        int x = 0;
    return x;
}

En C/C++/... ceci conduit à une erreur. (ça tu devrais savoir,...) Mais en Python (et ça m'étonne), un truc du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
def f(n):
    if n > 0: x = 1
    else:     x = -1
    return x

fonctionne parfaitement.
J'ai téléchargé (pour windoz) le programme Python(x,y), et avec ça tu as automatiquement:

• Python
• PyQt
• Spyder ("Environnement de développement Python dédié à la visualisation de données et aux calculs scientifiques interactifs" http://www.pythonxy.com/)
• PyQwt
• wxPython
• numpy
• scipy
• matplotlib
• gnuplot

et plein d'autres.
Quelques manuels: SciPy reference Guide, Guide to NumPy.

Qu'as-tu fait avec numpy ? As-tu essayé de "vectoriser" tes calculs ?

Je ne m'y connais pas là dedans mais essaie de trouver des fonctions déjà existantes dans ces modules.
A ce propos, je me souviens d'un article ici de Guido van Rossum (intéressant), dans lequel il écrit :
Conclusion
If you feel the need for speed, go for built-in functions - you can't beat a loop written in C. Check the library manual for a built-in function that does what you want. If there isn't one, here are some guidelines for loop optimization:

• Rule number one: only optimize when there is a proven speed bottleneck. Only optimize the innermost loop. (This rule is independent of Python, but it doesn't hurt repeating it, since it can save a lot of work. :-)
• Small is beautiful. Given Python's hefty charges for bytecode instructions and variable look-up, it rarely pays off to add extra tests to save a little bit of work.
• Use intrinsic operations. An implied loop in map() is faster than an explicit for loop; a while loop with an explicit loop counter is even slower.
• Avoid calling functions written in Python in your inner loop. This includes lambdas. In-lining the inner loop can save a lot of time.
• Local variables are faster than globals; if you use a global constant in a loop, copy it to a local variable before the loop. And in Python, function names (global or built-in) are also global constants!
• Try to use map(), filter() or reduce() to replace an explicit for loop, but only if you can use a built-in function: map with a built-in function beats for loop, but a for loop with in-line code beats map with a lambda function!
• Check your algorithms for quadratic behavior. But notice that a more complex algorithm only pays off for large N - for small N, the complexity doesn't pay off. In our case, 256 turned out to be small enough that the simpler version was still a tad faster. Your mileage may vary - this is worth investigating.
• And last but not least: collect data. Python's excellent profile module can quickly show the bottleneck in your code. if you're considering different versions of an algorithm, test it in a tight loop using the time.clock() function.

J'espère que ça pourra t'inspirer...
ciao

[dividee]

Note pour miawaw:

En Python, l'assignation crée une nouvelle variable locale, si elle n'existait pas. Cette variable a pour portée toute la portée locale, y compris la partie de code qui se situe avant l'assignation. C'est comme si la variable était déclarée au début de la portée.
Cela donne des situations étonnantes:

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
>>> x = 0	
>>> def f():
	y = x
	return y
 
>>> f()
0
>>> def g():
	y = x
	x = 2
	return y
 
>>> g()
 
Traceback (most recent call last):
  File "<pyshell#18>", line 1, in <module>
    g()
  File "<pyshell#17>", line 2, in g
    y = x
UnboundLocalError: local variable 'x' referenced before assignment

Dans f(), on va chercher x dans la portée englobante car il n'y a pas de variable x dans la portée locale.
Dans g(), x est une variable locale, de par l'assignation x = 2, et la référence à x au-dessus est donc une erreur.

Cela casse un peu l'image d'un langage purement interprété ligne par ligne qu'on pourrait avoir de Python...

[miawaw]

Merci pour l'info dividee . J'ignorais ce fait.

Ciao