如何向量化此python代码? [英] How to vectorize this python code?
问题描述
我正在尝试使用NumPy和矢量化操作来使一段代码运行得更快.但是,我似乎对如何矢量化此代码有误解(可能是由于对矢量化的理解不完整).
I am trying to use NumPy and vectorization operations to make a section of code run faster. I appear to have a misunderstanding of how to vectorize this code, however (probably due to an incomplete understanding of vectorization).
这是带有循环的工作代码(A和B是已设置大小的2D数组,已经初始化):
Here's the working code with loops (A and B are 2D arrays of a set size, already initialized):
for k in range(num_v):
B[:] = A[:]
for i in range(num_v):
for j in range(num_v):
A[i][j] = min(B[i][j], B[i][k] + B[k][j])
return A
这是我对上述代码进行矢量化的尝试:
And here is my attempt at vectorizing the above code:
for k in range(num_v):
B = numpy.copy(A)
A = numpy.minimum(B, B[:,k] + B[k,:])
return A
为了测试这些,我使用了以下代码,并将上面的代码包装在称为算法"的函数中:
For testing these, I used the following, with the code above wrapped in a function called 'algorithm':
def setup_array(edges, num_v):
r = range(1, num_v + 1)
A = [[None for x in r] for y in r] # or (numpy.ones((num_v, num_v)) * 1e10) for numpy
for i in r:
for j in r:
val = 1e10
if i == j:
val = 0
elif (i,j) in edges:
val = edges[(i,j)]
A[i-1][j-1] = val
return A
A = setup_array({(1, 2): 2, (6, 4): 1, (3, 2): -3, (1, 3): 5, (3, 6): 5, (4, 5): 2, (3, 1): 4, (4, 3): 8, (3, 4): 6, (2, 4): -4, (6, 5): -5}, 6)
B = []
algorithm(A, B, 6)
预期的结果,以及我用第一个代码得到的结果:
The expected outcome, and what I get with the first code is:
[[0, 2, 5, -2, 0, 10]
[8, 0, 4, -4, -2, 9]
[4, -3, 0, -7, -5, 5]
[12, 5, 8, 0, 2, 13]
[10000000000.0, 9999999997.0, 10000000000.0, 9999999993.0, 0, 10000000000.0]
[13, 6, 9, 1, -5, 0]]
第二个(向量化)函数返回:
The second (vectorized) function instead returns:
[[ 0. -4. 0. 0. 0. 0.]
[ 0. -4. 0. -4. 0. 0.]
[ 0. -4. 0. 0. 0. 0.]
[ 0. -4. 0. 0. 0. 0.]
[ 0. -4. 0. 0. 0. 0.]
[ 0. -4. 0. 0. -5. 0.]]
我想念什么?
推荐答案
该问题是由该行中的数组广播引起的:
The problem is caused by array broadcasting in the line:
A = numpy.minimum(B, B[:,k] + B[k,:])
B是6乘6的大小,B [:,k]是具有6个元素的数组,B [k ,:]是具有6个元素的数组.
B is size 6 by 6, B[:,k] is an array with 6 elements, B[k,:] is an array with 6 elements.
(因为您使用的是numpy数组类型,所以B [:,k]和B [k ,:]均会返回形状为N的1列数组)
(Because you are using the numpy array type, both B[:,k] and B[k,:] return a rank-1 array of shape N)
Numpy会自动更改大小以匹配:
Numpy automatically changes the sizes to match:
- 将第一个B [:,k]添加到B [k ,:],以得到一个包含6个元素的中间数组结果. (这不是您想要的)
- 第二个6元素数组通过重复行广播到6 x 6矩阵
- 原始矩阵的最小值的三倍,并计算出此广播矩阵.
这意味着您的numpy代码等效于:
This means that your numpy code is equivalent to:
for k in range(num_v):
B[:] = A[:]
C=[B[i][k]+B[k][i] for i in range(num_v)]
for i in range(num_v):
for j in range(num_v):
A[i][j] = min(B[i][j], C[j])
修复代码的最简单方法是使用矩阵类型而不是数组类型:
The easiest way to fix your code is to use the matrix type instead of the array type:
A = numpy.matrix(A)
for k in range(num_v):
A = numpy.minimum(A, A[:,k] + A[k,:])
矩阵类型使用更严格的广播规则,因此在这种情况下:
The matrix type uses stricter broadcasting rules so in this case:
- A [:,k]通过重复列扩展为6 x 6矩阵
- A [k ,:]通过重复行扩展为6 x 6矩阵
- 将广播的矩阵相加在一起,组成一个6 x 6的矩阵
- 已应用最小值
这篇关于如何向量化此python代码?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!