python - 更快的 numpy.polynomial？

Question

我有一个非常简单的问题:在我的 python 工具箱中，我必须从一个大向量(大小 >> 10^6)计算多项式的值(通常是 3 或 2 次，很少有其他次数，总是整数次)。将结果存储在缓冲区中不是一种选择，因为我有几个这样的向量，所以我很快就会耗尽内存，而且在任何情况下我通常只需要计算一次。 numpy.polyval 的性能其实还不错，但这仍然是我的瓶颈。我能否以某种方式加快多项式的计算速度？

附录

我认为 Joe Kington 的纯 numpy 解决方案对我有好处，特别是因为它避免了其他库或 cython 安装时的潜在问题。对于那些提问的人，向量中的数字很大(10^4 阶)，所以我认为建议的近似值不会起作用。

Answer 1

实际上，您可以通过就地执行操作(或使用 numexpr 或 numba，它们会自动执行我在下面手动执行的操作)来稍微加快速度。

numpy.polyval 是一个非常短的函数。省略一些类型检查等，它相当于:

def polyval(p, x):
    y = np.zeros_like(x)
    for i in range(len(p)):
        y = x * y + p[i]
    return y

这种方法的缺点是将在循环内创建一个临时数组，而不是就地执行操作。

我要做的是微优化，并且只对非常大的 x 输入有值(value)。此外，我们必须假设浮点输出，而不是让向上转换规则确定输出的 dtype。但是，它会稍微加快速度并使用更少的内存:

def faster_polyval(p, x):
    y = np.zeros(x.shape, dtype=float)
    for i, v in enumerate(p):
        y *= x
        y += v
    return y

例如，假设我们有以下输入:

# Third order polynomial
p = [4.5, 9.8, -9.2, 1.2]

# One-million element array
x = np.linspace(-10, 10, 1e6)

结果是一样的:

In [3]: np_result = np.polyval(p, x)

In [4]: new_result = faster_polyval(p, x)

In [5]: np.allclose(np_result, new_result)
Out[5]: True

我们得到了适度的 2-3 倍加速(这主要与数组大小无关，因为它与内存分配有关，而不是操作数):

In [6]: %timeit np.polyval(p, x)
10 loops, best of 3: 20.7 ms per loop

In [7]: %timeit faster_polyval(p, x)
100 loops, best of 3: 7.46 ms per loop

对于非常大的输入，内存使用差异比速度差异更重要。 “裸”numpy 版本在峰值使用时使用的内存比 faster_polyval 版本多 ~2 倍。