Problème d'optimisation Python?

Question

Très bien, j'ai fait ce travail récemment (ne vous inquiétez pas, je l'ai déjà fait, mais en C++) mais je me suis demandé comment je pourrais le faire en python. Le problème est d'environ 2 sources de lumière qui émettent de la lumière. Je ne vais pas entrer dans les détails.

Voici le code (que j'ai réussi à optimiser un peu dans la dernière partie):

import math, array 
import numpy as np 
from PIL import Image 

size = (800,800) 
width, height = size 

s1x = width * 1./8 
s1y = height * 1./8 
s2x = width * 7./8 
s2y = height * 7./8 

r,g,b = (255,255,255) 
arr = np.zeros((width,height,3)) 
hy = math.hypot 
print 'computing distances (%s by %s)'%size, 
for i in xrange(width): 
    if i%(width/10)==0: 
     print i,  
    if i%20==0: 
     print '.', 
    for j in xrange(height): 
     d1 = hy(i-s1x,j-s1y) 
     d2 = hy(i-s2x,j-s2y) 
     arr[i][j] = abs(d1-d2) 
print '' 

arr2 = np.zeros((width,height,3),dtype="uint8")   
for ld in [200,116,100,84,68,52,36,20,8,4,2]: 
    print 'now computing image for ld = '+str(ld) 
    arr2 *= 0 
    arr2 += abs(arr%ld-ld/2)*(r,g,b)/(ld/2) 
    print 'saving image...' 
    ar2img = Image.fromarray(arr2) 
    ar2img.save('ld'+str(ld).rjust(4,'0')+'.png') 
    print 'saved as ld'+str(ld).rjust(4,'0')+'.png' 

j'ai réussi à optimiser la plus grande partie, mais il y a encore un énorme écart de performance dans la partie avec le 2 pour-s, et je ne peux pas sembler penser à un moyen de contourner cela en utilisant des opérations de tableau commun ... Je suis ouvert aux suggestions: D

Modifier: En réponse à la suggestion de Vlad, je ' ll poster les détails du problème: Il y a 2 sources de lumière, chacune émettant une lumière comme une onde sinusoïdale: E1 = E0 * sin (omega1 * temps + phi01) E2 = E0 * sin (omega2 * temps + phi02) on considère omega1 = omega2 = omega = 2 * PI/T et phi01 = phi02 = phi0 pour simplifier en considérant x1 comme la distance de la première source d'un point sur le plan, l'intensité de la lumière dans ce point est Ep1 = E0 * sin (omega * temps - 2 * PI * x1/lambda + phi0) où lambda = vitesse de lumière * T (période d'oscillation) En considérant les deux sources de lumière sur le plan, la formule devient Ep = 2 * E0 * cos (PI * (x2-x1)/lambda) sin (omega temps - PI * (x2 -x1)/lambda + phi0) et à partir de là nous avons pu constater que l'intensité de la lumière est maximale lorsque (x2-x1)/lambda = (2 * k) * PI/2 et minimum lorsque (x2-x1)/lambda = (2 * k + 1) * PI/2 et varie entre les deux, où k est un nombre entier

Pour un moment donné de temps, étant donné les coordonnées de les sources de lumière, et pour un lambda connu et E0, nous avons dû faire un programme pour dessiner comment la lumière ressemble IMHO je pense que j'ai optimisé le problème autant qu'il pourrait être fait ...

Answer 1

Les motifs d'interférence sont amusants, n'est-ce pas? Donc, tout d'abord cela va être mineur car l'exécution de ce programme tel quel sur mon ordinateur portable prend seulement douze secondes et demi. Mais voyons ce que l'on peut faire pour faire le premier bit à travers les opérations numpy array, n'est-ce pas?Nous avons essentiellement que vous voulez:

arr[i][j] = abs(hypot(i-s1x,j-s1y) - hypot(i-s2x,j-s2y)) 

Pour tous i et j. Donc, comme numpy a une fonction hypot qui fonctionne sur des tableaux numpy, utilisons ceci. Notre premier défi est d'obtenir un tableau de la bonne taille avec chaque élément égal à i et un autre avec chaque élément égal à j. Mais ce n'est pas trop dur. en fait, une réponse précise en dessous de mon au merveilleux numpy.mgrid que je ne connaissais pas avant cela ne ceci:

array_i,array_j = np.mgrid[0:width,0:height] 

Il y a la question légère de rendre votre (width, height) tableau -sized en (width,height,3) pour être compatible avec vos relevés de génération d'image, mais c'est assez facile à faire:

arr = (arr * np.ones((3,1,1))).transpose(1,2,0) 

Ensuite, nous brancher sur votre programme, et que les choses soient faites par des opérations de tableau:

import math, array 
import numpy as np 
from PIL import Image 

size = (800,800) 
width, height = size 

s1x = width * 1./8 
s1y = height * 1./8 
s2x = width * 7./8 
s2y = height * 7./8 

r,g,b = (255,255,255) 

array_i,array_j = np.mgrid[0:width,0:height] 

arr = np.abs(np.hypot(array_i-s1x, array_j-s1y) - 
      np.hypot(array_i-s2x, array_j-s2y)) 

arr = (arr * np.ones((3,1,1))).transpose(1,2,0) 

arr2 = np.zeros((width,height,3),dtype="uint8") 
for ld in [200,116,100,84,68,52,36,20,8,4,2]: 
    print 'now computing image for ld = '+str(ld) 
    # Rest as before 

Et la nouvelle heure est ... 8,2 secondes. Donc, vous économisez peut-être quatre secondes entières. D'un autre côté, c'est presque exclusivement dans les étapes de génération d'image, alors peut-être vous pouvez les resserrer en générant seulement les images que vous voulez.

Answer 2

Les seuls changements que vient à mon esprit est de déplacer certaines opérations hors de la boucle:

for i in xrange(width): 
    if i%(width/10)==0: 
     print i,  
    if i%20==0: 
     print '.', 
    arri = arr[i] 
    is1x = i - s1x 
    is2x = i - s2x 
    for j in xrange(height): 
     d1 = hy(is1x,j-s1y) 
     d2 = hy(is2x,j-s2y) 
     arri[j] = abs(d1-d2) 

L'amélioration, si tout, sera probablement mineur cependant.

Answer 3

Les compréhensions de liste sont beaucoup plus rapides que les boucles. Par exemple, au lieu de

for j in xrange(height): 
     d1 = hy(i-s1x,j-s1y) 
     d2 = hy(i-s2x,j-s2y) 
     arr[i][j] = abs(d1-d2) 

Vous écririez

arr[i] = [abs(hy(i-s1x,j-s1y) - hy(i-s2x,j-s2y)) for j in xrange(height)] 

D'autre part, si vous êtes vraiment essayer de « optimiser », alors vous pouvez ré-écrire cet algorithme en C, et utilisez SWIG ou similaire pour l'appeler à partir de python.

Answer 4

Si vous utilisez des opérations de tableau au lieu de boucles, c'est beaucoup, beaucoup plus rapide. Pour moi, la génération d'image est maintenant ce qui prend tellement de temps. Au lieu de vos deux boucles i,j, j'ai ceci:

I,J = np.mgrid[0:width,0:height] 
D1 = np.hypot(I - s1x, J - s1y) 
D2 = np.hypot(I - s2x, J - s2y) 

arr = np.abs(D1-D2) 
# triplicate into 3 layers 
arr = np.array((arr, arr, arr)).transpose(1,2,0) 
# .. continue program 

Les bases que vous souhaitez retenir pour l'avenir est la suivante: c'est pas sur l'optimisation; utiliser des formes de tableau en numpy, c'est juste l'utiliser comme il est censé être utilisé. Avec l'expérience, vos futurs projets ne devraient pas faire le détour par des boucles python, les formes de tableaux devraient être la forme naturelle. Ce que nous avons fait ici était vraiment simple. Au lieu de math.hypot nous avons trouvé numpy.hypot et l'avons utilisé. Comme toutes ces fonctions numpy, elle accepte ndarrays comme arguments, et fait exactement ce que nous voulons.