Acelerar nested para bucle con exponenciación de elementos.

Estoy trabajando en un código grande y me encuentro en la necesidad de acelerar un poco específico. He creado un MWE muestra a continuación:

 import numpy as np import time def random_data(N): # Generate some random data. return np.random.uniform(0., 10., N).tolist() # Lists that contain all the data. list1 = [random_data(10) for _ in range(1000)] list2 = [random_data(1000), random_data(1000)] # Start taking the time. tik = time.time() list4 = [] # Loop through all elements in list1. for elem in list1: list3 = [] # Loop through elements in list2. for elem2 in zip(*list2): A = np.exp(-0.5*((elem[0]-elem2[0])/elem[3])**2) B = np.exp(-0.5*((elem[1]-elem2[1])/elem[3])**2) list3.append(A*B) # Sum elements in list3 and append result to list4. sum_list3 = sum(list3) if sum(list3)>0. else 1e-06 list4.append(sum_list3) # Print the elapsed time. print time.time()-tik 

El formato extraño de list1 y list2 es porque así es como este bloque de código los recibe.

La parte obvia en la que se pasa la mayor parte del tiempo es en el cálculo recursivo de los términos A y B

¿Hay alguna manera de acelerar este bloque de código sin tener que paralelizarlo (lo he intentado antes y me dio muchos problemas )? Estoy abierto a usar cualquier paquete, numpy , scipy , etc.


Añadir

Este es el resultado de aplicar las optimizaciones de abarnert y también el consejo de Jaime de hacer una sola exponenciación. La función optimizada es en promedio ~ 60 veces más rápida en mi sistema.

 import numpy as np import timeit def random_data(N): return np.random.uniform(0., 10., N).tolist() # Lists that contain all the data. list1 = [random_data(10) for _ in range(1000)] list2 = [random_data(1000), random_data(1000)] array1 = np.array(list1) array2 = np.array(zip(*list2)) # Old non-optimezed function. def func1(): list4 = [] # Process all elements in list1. for elem in list1: # Process all elements in list2. list3 = [] for elem2 in zip(*list2): A = np.exp(-0.5*((elem[0]-elem2[0])/elem[3])**2) B = np.exp(-0.5*((elem[1]-elem2[1])/elem[3])**2) list3.append(A*B) # Sum elements in list3 and append result to list4. sum_list3 = sum(list3) if sum(list3)>0. else 1e-06 list4.append(sum_list3) # New optimized function. def func2(): list4 = [] # Process all elements in list1. for elem in array1: # Broadcast over elements in array2. A = -0.5*((elem[0]-array2[:,0])/elem[3])**2 B = -0.5*((elem[1]-array2[:,1])/elem[3])**2 array3 = np.exp(A+B) # Sum elements in array3 and append result to list4. sum_list3 = max(array3.sum(), 1e-10) list4.append(sum_list3) # Get time for both functions. func1_time = timeit.timeit(func1, number=10) func2_time = timeit.timeit(func2, number=10) # Print hom many times faster func2 is versus func1. print func1_time/func2_time 

Desea convertir gradualmente esto de usar listas y bucles a usar arreglos y transmisión, capturando las partes más fáciles y / o más críticas de tiempo primero hasta que sea lo suficientemente rápido.

El primer paso es no hacer ese zip(*list2) una y otra vez (especialmente si se trata de Python 2.x). Mientras estamos en ello, podríamos almacenarlo en una matriz y hacer lo mismo con list1 ; por el momento, todavía puede iterar sobre ellos. Asi que:

 array1 = np.array(list1) array2 = np.array(zip(*list2)) # … for elem in array1: # … for elem2 in array2: 

Esto no acelerará mucho las cosas (en mi máquina, nos lleva de 14.1 segundos a 12.9), pero nos da un lugar para comenzar a trabajar.

También debe eliminar el cálculo doble de la sum(list3) :

 sum_list3 = sum(list3) sum_list3 = sum_list3 if sum_list3>0. else 1e-06 

Mientras tanto, es un poco extraño que desee que el value <= 0 vaya a 1e-6 , pero que 0 < value < 1e-6 se quede solo. ¿Es eso realmente intencional? Si no, puedes arreglar eso y simplificar el código al mismo tiempo, simplemente haciendo esto:

 sum_list3 = max(array3.sum(), 1e-06) 

Ahora, vamos a transmitir los cálculos A y B :

 # Broadcast over elements in list2. A = np.exp(-0.5*((elem[0]-array2[:,0])/elem[3])**2) B = np.exp(-0.5*((elem[1]-array2[:, 1])/elem[3])**2) array3 = A*B # Sum elements in list3 and append result to list4. sum_list3 = max(array3.sum(), 1e-06) list4.append(sum_list3) 

Y esto nos lleva de 12.9 segundos a 0.12. También podría ir un paso más allá al transmitir sobre array1 y reemplazar list4 con un array asignado previamente, y así sucesivamente, pero esto probablemente ya sea lo suficientemente rápido.