高效算法代替循环

Question

我有一个数据组，其中每个样本具有类似于此

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

例如的结构：

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") 

所以每个样本我需要计算在x的每个元素与相同索引的y的对应元素之间的点积并且求和结果。即：

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] 

这是我的全部代码：

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  

正如你所看到的这个算法的复杂度太高，也是我的样本比这大得多。所以即使是一个小的数据集，即包含400个样本，我也要等4个小时才能得出结果。我正在寻找更好的方法来实现这个算法。 P.S：我正在考虑多线程或多处理，但我不确定它是否有帮助？！

我很欣赏任何建议！

Answer 1

而不是汇总每对的点积，这需要n * m操作，您可以将每个列表中的所有矢量求和，并只做最后一个点积，这将仅执行n + m操作。

前：

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

后：

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) 

编辑：更快速的版本，以numpy的优势：

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

输出是一样的：

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

个

打印：

[[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 

时序它表明，有显著的改善。计时代码：

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) 

样本输出：

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 

为20000个元件的两个列表的操作中，每个只用了约2秒，而我预测这将需要几个小时的老方法。

---

其原因是您可以将操作组合在一起。假设你有以下列表：

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

然后总结每对的点积是这样的：

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 

可以分解出u，v，w，x，y，和z elements：

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

然后你可以进一步将这些因素总和：

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

这就是每个初始列表中求和矢量的点积。

Answer 2

这里没什么可以做的。你想得到所有乘法的结果，你只需要做它们，这就是你的算法所做的。你可以做的唯一的事情就是将你的结果存储在散列表中，以防止你知道你有很多重复的结果，但是如果你不知道它会花费很多内存。顺便说一句，多线程可能会让你的程序运行得更快，但它永远不会改进它的复杂性，这是所需的操作次数。

Answer 3

您也可以直接做在内部矩阵的点积绕过需要itertools.product：

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

编辑：

在短名单（小于几千元素）这将比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