我有一个2D成本矩阵M
,可能是400x400,我正在尝试计算通过它的最佳路径.因此,我有一个像以下的功能:
M[i,j] = M[i,j] + min(M[i-1,j-1],M[i-1,j]+P1,M[i,j-1]+P1)
这显然是递归的.P1是一些加性常数.我的代码或多或少有效,是:
def optimalcost(cost, P1=10):
width1,width2 = cost.shape
M = array(cost)
for i in range(0,width1):
for j in range(0,width2):
try:
M[i,j] = M[i,j] + min(M[i-1,j-1],M[i-1,j]+P1,M[i,j-1]+P1)
except:
M[i,j] = inf
return M
现在我知道在Numpy中循环是一个糟糕的想法,对于像初始成本矩阵的计算这样的事情,我已经能够找到缩短时间的捷径.但是,由于我需要对整个矩阵进行评估,因此我不确定如何做到这一点.这在我的机器上每次通话大约需要3秒钟,并且必须应用于这些成本矩阵中的大约300个.我不确定这个时间来自何处,因为分析表明,对min的200,000次调用仅需0.1秒 - 也许内存访问?
有办法以某种方式并行执行此操作吗?我假设可能有,但对我来说,似乎每次迭代都依赖,除非有一种更聪明的方式来记忆事物.
这个问题有相似之处:我可以避免使用numpy进行动态编程时的Python循环开销吗?
如果有必要,我很乐意切换到C,但我喜欢Python的灵活性,以便进行快速测试,并且缺乏文件IO的faff.脱离我的头脑,类似下面的代码可能会明显更快?
#define P1 10
void optimalcost(double** costin, double** costout){
/*
We assume that costout is initially
filled with costin's values.
*/
float a,b,c,prevcost;
for(i=0;i<400;i++){
for(j=0;j<400;j++){
a = prevcost+P1;
b = costout[i][j-1]+P1;
c = costout[i-1][j-1];
costout[i][j] += min(prevcost,min(b,c));
prevcost = costout[i][j];
}
}
}
return;
更新:
我在Mac上,我不想安装一个全新的Python工具链,所以我用过Homebrew
.
> brew install llvm --rtti > LLVM_CONFIG_PATH=/usr/local/opt/llvm/bin/llvm-config pip install llvmpy > pip install numba
新的"numba'd"代码:
from numba import autojit, jit import time import numpy as np @autojit def cost(left, right): height,width = left.shape cost = np.zeros((height,width,width)) for row in range(height): for x in range(width): for y in range(width): cost[row,x,y] = abs(left[row,x]-right[row,y]) return cost @autojit def optimalcosts(initcost): costs = zeros_like(initcost) for row in range(height): costs[row,:,:] = optimalcost(initcost[row]) return costs @autojit def optimalcost(cost): width1,width2 = cost.shape P1=10 prevcost = 0.0 M = np.array(cost) for i in range(1,width1): for j in range(1,width2): M[i,j] += min(M[i-1,j-1],prevcost+P1,M[i,j-1]+P1) prevcost = M[i,j] return M prob_size = 400 left = np.random.rand(prob_size,prob_size) right = np.random.rand(prob_size,prob_size) print '---------- Numba Time ----------' t = time.time() c = cost(left,right) optimalcost(c[100]) print time.time()-t print '---------- Native python Time --' t = time.time() c = cost.py_func(left,right) optimalcost.py_func(c[100]) print time.time()-t
在Python中编写非常Pythonic的代码很有意思.对于有兴趣编写Numba代码的人,请注意,您需要在代码中明确表示循环.之前,我有整齐的Numpy单线,
abs(left[row,:][:,newaxis] - right[row,:])
计算成本.Numba花了大约7秒钟.正确地写出循环给出0.5秒.
将它与本机Python代码进行比较是一种不公平的比较,因为Numpy可以很快地做到这一点,但是:
Numba编译:0.509318113327s
原产地:172.70626092s
数字和转换的简单程度让我印象深刻.