如何显著提高嵌套循环的速度?

Question

我试着在网上搜索，但没有找到任何太有用的

我正在尝试通过多个嵌套循环来循环查找值:

for i in range(10):
val = 0
for j in range(10):
for k in range(10):
for l in range(10):
for m in range(10):
for n in range(10):
if i != j:
val += x[k, l, m, n] * r[k, i] * r[l, i] * r[m, j] * r[n, j]
values.append(val)

其中x为(10, 10, 10, 10)数组，r为(10, 10)数组。

我觉得应该有一个比迭代它们更快的解决方案。

如何加快这些嵌套循环?

编辑:

我正在寻找一种方法来加速巢循环或一种方法来重写脚本，使其提高速度。

Answer 1

示例计算:

In [76]: x = np.random.rand( 10, 10, 10, 10); r=np.random.rand(10, 10 )
In [77]: values=[]
...: for i in range(10):
...:     val = 0
...:     for j in range(10):
...:         for k in range(10):
...:             for l in range(10):
...:                 for m in range(10):
...:                     for n in range(10):
...:                         if i != j:
...:                             val += x[k, l, m, n] * r[k, i] * r[l, i] * r[m, j] * r[n, j]
...:     values.append(val)
...: 

我没有计时，但是有一个明显的延迟。

In [78]: values
Out[78]: 
[2405.069869674815,
1906.3583547360959,
1934.09600942877,
1583.4551649741236,
2441.8509094338756,
2018.3416769619837,
2508.333484796075,
1664.3574504516193,
2889.949142416882,
1914.4720528808432]

用广播数组替换内部4循环:

In [79]: values=[]
...: for i in range(10):
...:     val = 0
...:     for j in range(10):
...:        if i != j:
...:           temp = x *  r[:, i,None,None,None] * r[:, i,None,None] * r[:, j,None] * r[:, j]
...:           val += temp.sum()
...:     values.append(val)
...: 
...: 
In [80]: values
Out[80]: 
[2405.0698696748414,
1906.3583547360881,
1934.0960094287668,
1583.4551649741336,
2441.8509094339124,
2018.3416769619737,
2508.3334847960673,
1664.3574504516007,
2889.9491424168923,
1914.4720528808484]

相同的值，而且肯定更快。

经过更多的思考，我可能会替换i和j循环，但i!=j步骤使这有点困难。但这是很好的第一步。

%%timeit循环:

1.22 s ± 2.12 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
10.8 ms ± 15.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

如果我定义一个效用函数:

def foo(x,i,j):
temp =  x *  r[:, i,None,None,None] * r[:, i,None,None] * r[:, j,None] * r[:, j]
return temp.sum()

然后

[sum([foo(x,i,j) for j in range(10)])-foo(x,i,i) for i in range(10)]

产生没有i!=j测试的值。这有点慢，但我可以调整foo来处理j的数组值，从而消除j循环。但稍后会详细介绍。

Answer 2

必须注意的第一点是，从数组中访问成员是通过间接访问完成的。例如，在第三个嵌套循环中添加rki = r[k, i]，并直接在sum中使用rki。

Answer 3

减少间接访问的数量会有帮助。例如，在第三个嵌套循环中添加rki = r[k, i]，并直接在sum中使用rki…等等。