numpy 更快的多项式?

inkz8wg9  于 2023-01-09  发布在  其他
关注(0)|答案(2)|浏览(222)

我有个很简单的问题:在我的python工具箱中,我必须计算多项式的值(通常为3或2次,很少为其他次数,总是整数次)(大小〉〉10^6)。将结果存储在缓冲区中不是一个选项,因为我有几个这样的向量,所以我会很快耗尽内存,而且我通常只需要计算一次,numpy.polyval的性能其实很好,但这仍然是我的瓶颈,我能不能让多项式的计算速度更快?

    • 增编**

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

carvr3hs

carvr3hs1#

实际上,您可以通过就地执行操作(或者使用numexprnumba,它们将自动执行下面手动执行的操作)来稍微加快速度。
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

对于真正巨大的输入,内存使用差异将比速度差异更重要。“裸”Numpy版本在峰值使用时将比X1 M4 N1 X版本多使用~ 2倍的内存。

gev0vcfq

gev0vcfq2#

当我想知道np.polyvalnp.polynomial.polynomial.polyval哪个更快的时候,我就到了这里。有趣的是,看到简单的实现更快,就像@Joe Kington展示的那样。(我希望numpy能做一些优化。)
所以这里是我与np.polynomial.polynomial.polyval和一个稍微快一点的版本的比较。

def fastest_polyval(x, a):
    y = a[-1]
    for ai in a[-2::-1]:
        y *= x
        y += ai
    return y

它避免了初始的零数组,并且需要少一个循环。
x一个一个一个一个x一个一个二个x

相关问题