一个更快的numpy.polynomial？

Question

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

附录

我认为Joe Kington的纯粹解决方案对我有好处,特别是因为它避免了其他库或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输入才有价值.此外,我们必须假设浮点输出而不是让upcasting规则确定输出的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倍的内存.