更快numpy.polynomial？

Question

我有一个非常简单的问题：在我的 python 工具箱中，我必须从一个大向量（大小 > > 10^6)。将结果存储在缓冲区中不是一种选择，因为我有几个这样的向量，所以我很快就会运行内存不足，而且在任何情况下我通常只需要计算一次。 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 输入有价值。此外，我们必须假设浮点输出，而不是让向上转换规则确定输出的 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

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

更快numpy.polynomial？

A faster numpy.polynomial?

python

numpy

optimization

polynomial-math