python - 在 Numpy 中运行 max/limsup : what optimization?

Question

为了计算limsup对于一个序列，让我们为每个 i 计算 max(A[i:]):

import numpy as np
n = 10
A = np.random.random(n)
M = np.zeros(n)

for i in range(n):
    M[i] = np.max(A[i:])

这是一个例子:

[ 0.85436167  0.92015564  0.44302976  0.56030154  0.16415721  0.39810583   0.65692947  0.5884984   0.57646131  0.0774121 ]
[ 0.92015564  0.92015564  0.65692947  0.65692947  0.65692947  0.65692947   0.65692947  0.5884984   0.57646131  0.0774121 ]

---

当 n 为 100 万时，这非常非常慢。

可以使用什么优化来有效地计算数组 M？

Answer 1

您可以用以下代码替换您的 for 循环:

M = np.maximum.accumulate(A[::-1])[::-1]

这会查看 A 的反转并计算累积最大值，然后反转这个新数组。

这段代码的性能应该明显更好:for 循环方法具有二次复杂度 O(n²)，它会导致 Python 的开销解释器在每次迭代中执行的字节码。另一方面，np.maximum.accumulate 方法只是在编译代码中单次遍历数组。