logo标签列表

高效算法替代循环

pythonalgorithmnested-loopsnested-lists
8

我有一个数据集，其中每个样本的结构类似于这个样子

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个小时才能得到结果。我正在寻求更好的实现此算法的方法。 附言：我在考虑使用多线程或多进程，但我不确定是否有帮助？！

感谢任何建议！

你的问题是如何增长的？当你说200个样本需要4小时时，是指例如X[i]和Y[i]都有200个向量吗？ - Claudiu
你的“整个代码”没有引用 Y。 - Janne Karila
X和y只是例子...在代码中你会看到x1和x2。 - Moj
@Claudiu，我指的是具有样本的数据集。 - Moj
3个回答
14

不是将每对向量的点积相加，以求得总和，这需要 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)

这只是每个初始列表汇总向量的点积。

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（绝妙的）的答案更快。但是在这些数字以上，他的方法将更具可扩展性：

使用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
1
很好的想法，完全使用numpy进行编码！我也成功地做到了，我的更新答案（calc_superfast）与您的矩阵答案相比如何？我还将生成列表的代码更改为返回np.array，以消除执行转换所需的任何时间。 - Claudiu
将numpy与您的初始方法相结合，可以使小型列表稍微快一些，并且随着大小的增长而变得更快。最佳选择：两全其美 :)。 - mtth
-1

这里没有什么你可以做的。如果你想获取所有乘法的结果，你只需要进行计算，这就是你的算法所做的。你唯一能做的事情之一是将结果存储在哈希表中，以防你知道有许多重复的结果，但如果不这样做，它会占用很多内存。 顺便说一下，多线程可能会使你的程序运行得更快，但它永远不会改善它的复杂度，即所需的操作数。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接