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

[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