我有一个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左右。我不确定这段时间是从哪里来的，因为分析表明200,000次调用min仅花费0.1s-也许是内存访问？
有没有办法以某种方式并行执行此操作？我认为可能存在，但是在我看来，除非有一种更聪明的方式来记忆事物，否则每次迭代都是依赖的。
这个问题有很多相似之处：Can I avoid Python loop overhead on dynamic programming with numpy?
如果有必要，我很高兴切换到C语言，但是我喜欢Python的灵活性，可以进行快速测试，并且缺少文件IO的支持。我的头顶上，下面的代码可能会更快吗？
#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
新的“数字”代码：
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.5s。
将其与本机Python代码进行比较是不公平的比较，因为Numpy可以很快完成，但是：
Numba编译：0.509318113327s
本地的：172.70626092s
数字和转换的简单程度都给我留下了深刻的印象。
最佳答案
如果您不难切换到Python的Anaconda发行版，则可以尝试使用Numba，对于这种特殊的简单动态算法，它可能会提供很多加速而不会离开Python。