在Python中实现Horner方法的问题

作者：KING树林_944 | 来源：互联网 | 2023-05-24 10:08

如何解决《在Python中实现Horner方法的问题》经验，为你挑选了2个好方法。

所以我用三种不同的方法写下了用于评估多项式的代码.霍纳的方法应该是最快的,而天真的方法应该是最慢的,对吗？但是,为什么计算它的时间不是我所期望的呢？对于itera和naive方法,计算时间有时会变得完全相同.它出什么问题了？

import numpy.random as npr
import time

def Horner(c,x):
    p=0
    for i in c[-1::-1]:
        p = p*x+i
    return p

def naive(c,x):
    n = len(c)
    p = 0
    for i in range(len(c)):
        p += c[i]*x**i 
    return p

def itera(c,x):
    p = 0
    xi = 1
    for i in range(len(c)):
        p += c[i]*xi
        xi *= x 
    return p

c=npr.uniform(size=(500,1))
x=-1.34

start_time=time.time()
print Horner(c,x)
print time.time()-start_time

start_time=time.time()
print itera(c,x)
print time.time()-start_time

start_time=time.time()
print naive(c,x)
print time.time()-start_time

以下是一些结果:

[  2.58646959e+69]
0.00699996948242
[  2.58646959e+69]
0.00600004196167
[  2.58646959e+69]
0.00600004196167

[ -3.30717922e+69]
0.00899982452393
[ -3.30717922e+69]
0.00600004196167
[ -3.30717922e+69]
0.00600004196167

[ -2.83469309e+69]
0.00999999046326
[ -2.83469309e+69]
0.00999999046326
[ -2.83469309e+69]
0.0120000839233

Paul Draper.. 16

您的分析可以大大改进.此外,我们可以使您的代码运行速度提高200-500倍.

(1)冲洗并重复

由于两个原因,您无法仅运行性能测试的一次迭代.

你的时间分辨率可能不够好.这就是为什么你有时会为两个实现获得相同的时间:一次运行的时间接近你的计时机制的分辨率,所以你只记录了一个"tick".

有各种因素会影响性能.对于有意义的比较而言,最好的选择是进行大量的迭代.

你不需要进行大量的运行(当然,这并没有伤害),但你估计并调整迭代次数,直到方差在你的目的可接受的水平之内.

timeit 是一个很好的小模块,用于分析Python代码.

我将其添加到脚本的底部.

import timeit

n = 1000

print 'Horner', timeit.timeit(
    number = n,
    setup='from __main__ import Horner, c, x',
    stmt='Horner(c,x)'
)
print 'naive', timeit.timeit(
    number = n,
    setup='from __main__ import naive, c, x',
    stmt='naive(c,x)', 
)
print 'itera', timeit.timeit(
    number = n,
    setup='from __main__ import itera, c, x',
    stmt='itera(c,x)', 
)

哪个产生

Horner 1.8656351566314697
naive 2.2408010959625244
itera 1.9751169681549072

霍纳是最快的,但它并没有完全打破其他两个门.

(2)仔细看看发生了什么......

Python有运算符重载,所以很容易错过这个.

npr.uniform(size=(500,1)) 给你一个500 x 1 numpy结构的随机数.

所以呢？

好吧,c[i]不是一个数字.这是一个有一个元素的numpy数组.Numpy会重载运算符,因此您可以执行诸如使用标量乘以数组之类的操作.

这很好,但是为每个元素使用数组会产生大量开销,因此很难看出算法之间的差异.

相反,让我们尝试一个简单的Python列表:

import random
c = [random.random() for _ in range(500)]

现在,

Horner 0.034661054611206055
naive 0.12771987915039062
itera 0.07331395149230957

哇! 所有的时间都变得更快(10-60倍).按比例,霍纳的实施比其他两个更快.我们删除了所有三个的开销,现在可以看到"裸骨"的差异.

Horner比天真快4倍,比itera快2倍.

(3)备用运行时

你正在使用Python 2.我假设2.7.

让我们看看Python 3.4的票价.(语法调整:你需要在参数列表周围添加括号print.)

Horner 0.03298933599944576
naive 0.13706714100044337
itera 0.06771054599812487

差不多.

让我们试试PyPy,一个Python的JIT实现.("普通"Python实现称为CPython.)

Horner 0.006507158279418945
naive 0.07541298866271973
itera 0.005059003829956055

太好了!现在每个实现的运行速度提高了2-5倍.霍纳现在是天真的速度的10倍,但比itera略慢.

JIT运行时比解释器更难以分析.让我们将迭代次数增加到50000,并尝试确保它.

Horner 0.12749004364013672
naive 3.2823100090026855
itera 0.06546688079833984

(请注意,我们有50倍的迭代次数,但只有20倍的时间...... JIT在前1000次运行中的许多次都没有完全生效.)相同的结论,但差异更加明显.

当然,JIT的想法是在运行时分析,分析和重写程序,所以如果你的目标是比较算法,这将增加许多非显而易见的实现细节.

尽管如此,比较运行时可能有助于提供更广泛的视角.

还有一些事情.例如,您的天真实现计算它从未使用过的变量.你用range而不是xrange.您可以尝试使用索引而不是反向切片向后迭代.等等.

这些都没有改变我的结果,但他们值得考虑.

1> Paul Draper..：