algoritmo eficiente en lugar de bucle

Tengo un conjunto de datos donde cada muestra tiene una estructura similar a esta

X=[ [[],[],[],[]], [[],[]] , [[],[],[]] ,[[][]]] 

por ejemplo:

 X=np.array([ [ [1,2,3], [2,4,5] ,[2,3,4] ] , [ [5,6], [6,6] ] , [[2,3,1],[2,3,10],[23,1,2],[1,4,5]] ] ,"object") Y=np.array([ [ [12,14,15] ,[12,13,14] ] , [ [15,16], [16,16] ] , [[22,23,21],[32,33,11],[12,44,55]] ] ,"object") 

así que para cada muestra necesito calcular el producto de punto entre cada elemento de x con el elemento correspondiente de y del mismo índice y sumr el resultado. es decir:

 result=0 for i in range(3): for n,m in itertools.product(X[i],Y[i]): print "%s, %s" % (n,m) result+=np.dot(n,m) .....: [1, 2, 3], [12, 14, 15] [1, 2, 3], [12, 13, 14] [2, 4, 5], [12, 14, 15] [2, 4, 5], [12, 13, 14] [2, 3, 4], [12, 14, 15] [2, 3, 4], [12, 13, 14] [5, 6], [15, 16] [5, 6], [16, 16] [6, 6], [15, 16] [6, 6], [16, 16] [2, 3, 1], [22, 23, 21] [2, 3, 1], [32, 33, 11] [2, 3, 1], [12, 44, 55] [2, 3, 10], [22, 23, 21] [2, 3, 10], [32, 33, 11] [2, 3, 10], [12, 44, 55] [23, 1, 2], [22, 23, 21] [23, 1, 2], [32, 33, 11] [23, 1, 2], [12, 44, 55] [1, 4, 5], [22, 23, 21] [1, 4, 5], [32, 33, 11] [1, 4, 5], [12, 44, 55] 

Este es mi código completo:

  print "***build kernel***" K = np.zeros((n_samples, n_samples)) for i in range(n_samples): for j in range(n_samples): K[i,j] = self.kernel(X[i], X[j]) def kernel(x1,x2): N=8 #number of objects result=0 for i in xrange(N): for n,m in itertools.product(x1[i],x2[i]): result+=np.dot(n,m) return result 

Como puede ver, la complejidad de este algoritmo es demasiado alta y también mis muestras son mucho más grandes que esto. por lo que incluso para un pequeño conjunto de datos, es decir, contiene 400 muestras, tengo que esperar 4 horas para obtener el resultado. Estoy buscando una mejor manera de implementar este algoritmo. PD: Estaba pensando en multiproceso o multiproceso, pero no estoy seguro de si ayuda.

    Agradezco cualquier sugerencia!

    En lugar de sumr el producto de puntos de cada par, que requiere n * m operaciones, puede sumr todos los vectores en cada lista y simplemente hacer el producto de punto final, que solo tomará n + m operaciones.

    Antes de:

     def calc_slow(L1, L2): result = 0 for n, m in itertools.product(L1, L2): result += np.dot(n, m) return result 

    Después:

     def calc_fast(L1, L2): L1_sums = np.zeros(len(L1[0])) L2_sums = np.zeros(len(L2[0])) for vec in L1: L1_sums += vec for vec in L2: L2_sums += vec return np.dot(L1_sums, L2_sums) 

    EDITAR: Versión aún más rápida, aprovechando el numpy:

     def calc_superfast(L1, L2): return np.dot(np.array(L1).sum(0), np.array(L2).sum(0)) 

    La salida es la misma:

     print X[0], Y[0], calc_slow(X[0], Y[0]) print X[0], Y[0], calc_fast(X[0], Y[0]) 

    huellas dactilares:

     [[1, 2, 3], [2, 4, 5], [2, 3, 4]] [[12, 14, 15], [12, 13, 14]] 711 [[1, 2, 3], [2, 4, 5], [2, 3, 4]] [[12, 14, 15], [12, 13, 14]] 711.0 

    La sincronización muestra que hay una mejora significativa. Código de tiempo:

     import random import time def rand_vector(size=3): return [random.randint(1, 100) for _ in xrange(3)] def rand_list(length=200): return [rand_vector() for _ in xrange(length)] print "Generating lists..." L1 = rand_list(200) L2 = rand_list(200) print "Running slow..." s = time.time() print calc_slow(L1, L2) print "Slow for (%d, %d) took %.2fs" % (len(L1), len(L2), time.time() - s) print "Running fast..." s = time.time() print calc_fast(L1, L2) print "Fast for (%d, %d) took %.2fs" % (len(L1), len(L2), time.time() - s) 

    Salidas de muestra:

     Generating lists... Running slow... 75715569 Slow for (100, 100) took 1.48s Running fast... 75715569.0 Fast for (100, 100) took 0.03s Generating lists... Running slow... 309169971 Slow for (200, 200) took 5.29s Running fast... 309169971.0 Fast for (200, 200) took 0.04s Running fast... 3.05185703539e+12 Fast for (20000, 20000) took 1.94s 

    La operación para dos listas de 20000 elementos cada una solo tomó unos 2 segundos, mientras que predigo que tomaría varias horas con el método anterior.


    La razón por la que funciona es que puedes agrupar las operaciones. Suponiendo que tiene las siguientes listas:

     L1 = [a, b, c], [d, e, f], [g, h, i] L2 = [u, v, w], [x, y, z] 

    Luego, sumr el producto de puntos de cada par se vería así:

     a*u + b*v + c*w + a*x + b*y + c*z + d*u + e*v + f*w + d*x + e*y + f*z + g*u + h*v + i*w + g*x + h*y + i*z 

    Puedes factorizar los elementos u , v , w , x , y y z :

     u*(a + d + g) + v*(b + e + h) + w*(c + f + i) + x*(a + d + g) + y*(b + e + h) + z*(c + f + i) 

    Entonces puedes factorizar aún más esas sums:

     (u + x)*(a + d + g) + (v + y)*(b + e + h) + (w + z)*(c + f + i) 

    Que es solo el producto punto de los vectores sumdos de cada lista inicial.

    También puede evitar la necesidad de itertools.product haciendo directamente el producto de puntos en matrices internas:

     def calc_matrix(l1, l2): return np.array(l1).dot(np.array(l2).T).sum() def kernel(x1, x2): return sum( calc_matrix(l1, l2) for l1, l2 in zip(x1, x2) ) 

    Editar:

    En las listas cortas (menos de unos pocos miles de elementos) esto será más rápido que la respuesta de Claudiu (asombrosa). Su escalada mejor por encima de estos números:

    Usando los puntos de referencia de Claudiu:

     # len(l1) == 500 In [9]: %timeit calc_matrix(l1, l2) 10 loops, best of 3: 8.11 ms per loop In [10]: %timeit calc_fast(l1, l2) 10 loops, best of 3: 14.2 ms per loop # len(l2) == 5000 In [19]: %timeit calc_matrix(l1, l2) 10 loops, best of 3: 61.2 ms per loop In [20]: %timeit calc_fast(l1, l2) 10 loops, best of 3: 56.7 ms per loop 

    No hay nada que puedas hacer aquí. Quieres obtener los resultados de todas las multiplicaciones, solo tienes que hacerlas, y eso es lo que hace tu algoritmo. Una de las únicas cosas que puede hacer es almacenar sus resultados en una tabla hash, en caso de que sepa que tiene muchos resultados duplicados, pero le costará mucha memoria si no la tiene. Por cierto, el multihilo puede hacer que su progtwig se ejecute más rápido, pero nunca mejorará su complejidad, que es la cantidad de operaciones necesarias.