我正在尝试解决一个动态规划问题,我想出了一个简单的基于循环的算法,该算法基于一系列 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 将是二维数组。
