有效的算法而不是循环

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个小时才能得到结果.我正在寻找一种更好的方法来实现这个算法.PS:我在考虑多线程或多处理,但我不确定它是否有帮助？!

我很感激任何建议!

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元素:

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)

这只是每个初始列表中求和向量的点积.