Skip to main content
 首页 » 编程设计

python之使用 NumPy 加速嵌套循环

2024年12月31日9Leo_wl

我正在尝试解决一个动态规划问题,我想出了一个简单的基于循环的算法,该算法基于一系列 if 语句填充二维数组,如下所示:

s = # some string of size n 
opt = numpy.zeros(shape=(n, n)) 
 
for j in range(0, n): 
    for i in range(j, -1, -1): 
        if j - i == 0: 
            opt[i, j] = 1 
        elif j - i == 1: 
            opt[i, j] = 2 if s[i] == s[j] else 1 
        elif s[i] == s[j] and opt[i + 1, j - 1] == (j - 1) - (i + 1) + 1: 
            opt[i, j] = 2 + opt[i + 1, j - 1] 
        else: 
            opt[i, j] = max(opt[i + 1, j], opt[i, j - 1], opt[i + 1, j - 1]) 

不幸的是,这段代码对于大的 N 值非常慢。我发现使用 numpy.where 和 numpy.fill 等内置函数要好得多> 来填充数组的值而不是 for 循环,但我正在努力寻找任何示例来解释如何使这些函数(或其他优化的 numpy 方法)与一系列 if 语句,就像我的算法所做的那样。使用内置的 numpy 库重写上述代码以使其更好地针对 Python 进行优化的合适方法是什么?

请您参考如下方法:

我不认为 np.where 和 np.fill 可以解决你的问题。 np.where 用于返回满足特定条件的 numpy 数组的元素,但在您的情况下,条件是 NOT on VALUES 的 numpy 数组,但在来自变量 i 和 j 的值。

对于您的特定问题,我建议使用 Cython 专门针对较大的 N 值优化您的代码。Cython 基本上是 Python 和 C 之间的接口(interface)。Cython 的优点在于它允许您保留 python 语法,但是使用 C 结构对其进行优化。它允许您以类似 C 的方式定义变量类型,以加快计算速度。例如,使用 Cython 将 i 和 j 定义为整数会大大加快速度,因为在每次循环迭代时都会检查 i 和 j 的类型。

此外,Cython 将允许您使用 C 定义经典、快速的二维数组。然后您可以使用指针来快速访问此二维数组的元素,而不是使用 numpy 数组。在您的情况下,opt 将是二维数组。