Accélérer la sommation pour la boucle en python

Question

J'ai le goulot d'étranglement suivant et je me demande si quelqu'un peut suggérer des façons d'accélérer. J'ai trois listes x,y,z de longueur N. et j'applique ce qui suit summation.

def abs_val_diff(x1, x2, x3, y1, y2, y3): 
    """ Find the absolute value of the difference between x and y """ 
    return py.sqrt((x1 - y1) ** 2.0 + (x2 - y2) ** 2.0 + (x3 - y3) ** 2.0) 

R = 0.1 
sumV = 0.0 
for i in xrange(N): 
    for j in xrange(i + 1, N): 
     if R > abs_val_diff(x[i], y[i], z[i], 
          x[j], y[j], z[j]): 
       sumV += 1.0 

J'ai essayé d'utiliser des tableaux numpy, mais soit je fais quelque chose de mal ou il y a une réduction de la vitesse d'environ un facteur de 2.

Toutes les idées seraient très appréciés.

Answer 1

Je crois que vous pouvez utiliser numpy un peu plus efficacement en faisant quelque chose comme ce qui suit. Faire une petite modification à votre fonction pour utiliser le numpy.sqrt:

import numpy as np 

def abs_val_diff(x1, x2, x3, y1, y2, y3): 
    """ Find the absolute value of the difference between x and y """ 
    return np.sqrt((x1 - y1) ** 2.0 + (x2 - y2) ** 2.0 + (x3 - y3) ** 2.0) 

appellent ensuite les tableaux complets:

res = abs_val_diff(x[:-1],y[:-1],z[:-1],x[1:],y[1:],z[1:]) 

Ensuite, parce que vous ajoutez 1 pour chaque match, vous pouvez simplement prend la longueur du tableau résultant d'une requête sur le résultat:

sumV = len(res[R>res]) 

Cela permet de gérer numpy l'itération. Espérons que cela fonctionne pour vous

Answer 2

Il s'avère que les compréhensions de liste longues et laides sont généralement plus rapides que les boucles explicites en python car elles peuvent être compilées en un bytecode plus efficace. Je ne sais pas si ça vous aidera pour vous, mais il faut essayer quelque chose comme ceci:

sumV = sum((1.0 for j in xrange(1+1, N) for i in xrange(N) if R > abs_val_diff(x[i], y[i], z[i], x[j], y[j], z[j]))) 

Oui, il semble tout à fait atroce, mais vous allez. Plus d'informations peuvent être trouvées here et here.

Answer 3

Y a-t-il une raison pour laquelle vous avez réellement besoin de prendre la racine carrée dans votre fonction? Si tout ce que vous faites avec le résultat est de le comparer à une limite, pourquoi ne pas simplement mettre les deux côtés de la comparaison?

def abs_val_diff_squared(x1, x2, x3, y1, y2, y3): 
    """ Find the square of the absolute value of the difference between x and y """ 
    return (x1 - y1) ** 2.0 + (x2 - y2) ** 2.0 + (x3 - y3) ** 2.0 

R = 0.1 
R_squared = R * R 
sumV = 0.0 
for i in xrange(N): 
    for j in xrange(i + 1, N): 
     if R_squared > abs_val_diff_squared(x[i], y[i], z[i], 
          x[j], y[j], z[j]): 
       sumV += 1.0 

Je pense aussi qu'il devrait y avoir des économies beaucoup plus importantes tirées de trier les données en quelque chose comme un octtree donc il suffit de regarder les points à proximité plutôt que de comparer tout contre tout, mais c'est en dehors de ma connaissance.