gpt4 book ai didi

python - 加速 python/numpy 中的动态编程

转载 作者:行者123 更新时间:2023-12-02 09:37:59 33 4
gpt4 key购买 nike

我有一个 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 秒 - 也许是内存访问?

有没有办法以某种方式并行执行此操作?我认为可能有,但对我来说,似乎每次迭代都是依赖的,除非有更聪明的方法来内存事物。

与此问题有相似之处:Can I avoid Python loop overhead on dynamic programming with numpy?

如果有必要,我很乐意切换到 C,但我喜欢 Python 快速测试的灵 active 以及文件 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

新的“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 编写如此不符合 Python 风格的代码很有趣。请注意,对于有兴趣编写 Numba 代码的任何人,您需要在代码中显式表达循环。之前,我有简洁的 Numpy 单行代码,

abs(left[row,:][:,newaxis] - right[row,:])

计算成本。 Numba 大约花了 7 秒。正确地写出循​​环需要 0.5 秒。

将其与原生 Python 代码进行比较是不公平的,因为 Numpy 可以很快做到这一点,但是:

Numba 编译:0.509318113327s

本地:172.70626092s

这些数字和转换的简单程度都给我留下了深刻的印象。

最佳答案

如果您不难切换到Anaconda Python的发行版,您可以尝试使用Numba ,对于这个特定的简单动态算法来说,它可能会提供大量加速,而无需让您离开 Python。

关于python - 加速 python/numpy 中的动态编程,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20428541/

33 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com