在 Python 中实施霍纳方法的问题
Problems in implementing Horner's method in Python
所以我写下了使用三种不同方法评估多项式的代码。 Horner的方法应该是最快的，而naive的方法应该是最慢的吧？但是计算时间怎么不是我期望的呢？有时计算时间对于 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
你无法通过这样的测量获得准确的结果:
start_time=time.time()
print Horner(c,x)
print time.time()-start_time
估计大部分时间花在了print函数涉及的IO函数上。此外，要有显着性，你应该在大量迭代上进行测量，以平滑误差。在一般情况下，您可能还想对各种输入数据执行测试——根据您的算法，某些情况可能巧合地比其他情况更有效地解决。
您一定要看看 timeit 模块。类似的东西，也许：
import timeit
print 'Horner',timeit.timeit(stmt='Horner(c,x)',
setup='from __main__ import Horner, c, x',
number = 10000)
# ^^^^^
# probably not enough. Increase that once you will
# be confident
print 'naive',timeit.timeit(stmt='naive(c,x)',
setup='from __main__ import naive, c, x',
number = 10000)
print 'itera',timeit.timeit(stmt='itera(c,x)',
setup='from __main__ import itera, c, x',
number = 10000)
在我的系统上生成这个：
Horner 23.3317809105
naive 28.305519104
itera 24.385917902
但仍然有来自 运行 另一个的可变结果：
Horner 21.1151690483
naive 23.4374330044
itera 21.305426836
正如我之前所说，为了获得更有意义的结果，您应该明确地增加测试数量，并且 运行 在多个测试用例上增加测试数量以使结果更平滑。
如果您正在进行大量基准测试、科学计算、numpy 相关工作以及更多使用 ipython 的工作，将是一个非常有用的工具。
为了进行基准测试，您可以使用 ipython magic 使用 timeit 对代码进行计时，每个 运行 您将获得更一致的结果，这只是使用 timeit 然后使用函数或时间代码：
In [28]: timeit Horner(c,x)
1000 loops, best of 3: 670 µs per loop
In [29]: timeit naive(c,x)
1000 loops, best of 3: 983 µs per loop
In [30]: timeit itera(c,x)
1000 loops, best of 3: 804 µs per loop
要跨越一行以上的时间代码，您只需使用 %%timeit:
In [35]: %%timeit
....: for i in range(100):
....: i ** i
....:
10000 loops, best of 3: 110 µs per loop
ipython 可以 compile cython code, f2py 编码并使用不同的插件和 ipython 魔术命令完成许多其他非常有用的任务。
使用 cython 和一些非常基本的改进，我们可以将 Horner 的效率提高大约 25%：
In [166]: %%cython
import numpy as np
cimport numpy as np
cimport cython
ctypedef np.float_t DTYPE_t
def C_Horner(c, DTYPE_t x):
cdef DTYPE_t p
for i in reversed(c):
p = p * x + i
return p
In [28]: c=npr.uniform(size=(2000,1))
In [29]: timeit Horner(c,-1.34)
100 loops, best of 3: 3.93 ms per loop
In [30]: timeit C_Horner(c,-1.34)
100 loops, best of 3: 2.21 ms per loop
In [31]: timeit itera(c,x)
100 loops, best of 3: 4.10 ms per loop
In [32]: timeit naive(c,x)
100 loops, best of 3: 4.95 ms per loop
使用@Paul drapers 中的列表回答我们的 cythonised 版本 运行s 是原始函数的两倍，比 ietra 和 naive 快得多：
In [214]: import random
In [215]: c = [random.random() for _ in range(500)]
In [44]: timeit C_Horner(c, -1.34)
10000 loops, best of 3: 18.9 µs per loop
In [45]: timeit Horner(c, -1.34)
10000 loops, best of 3: 44.6 µs per loop
In [46]: timeit naive(c, -1.34)
10000 loops, best of 3: 167 µs per loop
In [47]: timeit itera(c,-1.34)
10000 loops, best of 3: 75.8 µs per loop
您的分析可以得到很大改进。另外，我们可以让您的代码 运行 快 200-500 倍。
(1) 冲洗并重复
您不能 运行 只进行一次性能测试迭代，原因有二。
- 您的时间分辨率可能不够好。这就是为什么您有时会为两个实现获得相同的时间：一个 运行 的时间接近您的计时机制的分辨率，因此您只记录了一个 "tick".
- 有各种 影响性能的因素。进行有意义的比较的最佳选择是多次迭代。
您不需要数以亿计的 运行s（当然，这并没有什么坏处），但是您可以估计并调整迭代次数，直到方差在您可以接受的水平内目的。
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
Whoa! All 时间变得更快了（10-60 倍）。按比例，Horner 的实现比其他两个更快。我们删除了所有三个的开销，现在可以看到 "bare bones" 差异。
Horner 比 naive 快 4 倍，比 itera 快 2 倍。
(3) 交替运行次
您正在使用 Python 2。我假设是 2.7。
让我们看看Python3.4票价如何。 （语法调整：您需要在参数列表周围加上括号 print。）
Horner 0.03298933599944576
naive 0.13706714100044337
itera 0.06771054599812487
差不多。
让我们试试 PyPy，Python 的 JIT 实现。 （"normal" Python 实现称为 CPython。）
Horner 0.006507158279418945
naive 0.07541298866271973
itera 0.005059003829956055
不错！每个实施现在 运行ning 快 2-5 倍。 Horner 现在的速度是 naive 的 10 倍，但比 itera 稍慢。
JIT 运行时间比解释器更难描述。让我们把迭代次数增加到50000次，试试看。
Horner 0.12749004364013672
naive 3.2823100090026855
itera 0.06546688079833984
（请注意，我们有 50 倍的迭代，但只有 20 倍的时间...JIT 在前 1000 运行 秒中的许多时间都没有完全发挥作用。）相同的结论，但差异更明显。
当然，JIT 的思想是在 运行 时间分析、分析和重写程序，所以如果您的目标是比较算法，这将添加很多不明显的实现细节。
None尽管如此，比较 运行 次可能有助于提供更广阔的视角。
还有一些事情。例如，您的天真实现计算了一个它从未使用过的变量。您使用 range 而不是 xrange。您可以尝试使用索引而不是反向切片向后迭代。等等
None 这些对我来说改变了很多结果，但它们值得考虑。
所以我写下了使用三种不同方法评估多项式的代码。 Horner的方法应该是最快的，而naive的方法应该是最慢的吧？但是计算时间怎么不是我期望的呢？有时计算时间对于 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
你无法通过这样的测量获得准确的结果:
start_time=time.time()
print Horner(c,x)
print time.time()-start_time
估计大部分时间花在了print函数涉及的IO函数上。此外，要有显着性，你应该在大量迭代上进行测量，以平滑误差。在一般情况下，您可能还想对各种输入数据执行测试——根据您的算法，某些情况可能巧合地比其他情况更有效地解决。
您一定要看看 timeit 模块。类似的东西，也许：
import timeit
print 'Horner',timeit.timeit(stmt='Horner(c,x)',
setup='from __main__ import Horner, c, x',
number = 10000)
# ^^^^^
# probably not enough. Increase that once you will
# be confident
print 'naive',timeit.timeit(stmt='naive(c,x)',
setup='from __main__ import naive, c, x',
number = 10000)
print 'itera',timeit.timeit(stmt='itera(c,x)',
setup='from __main__ import itera, c, x',
number = 10000)
在我的系统上生成这个：
Horner 23.3317809105
naive 28.305519104
itera 24.385917902
但仍然有来自 运行 另一个的可变结果：
Horner 21.1151690483
naive 23.4374330044
itera 21.305426836
正如我之前所说，为了获得更有意义的结果，您应该明确地增加测试数量，并且 运行 在多个测试用例上增加测试数量以使结果更平滑。
如果您正在进行大量基准测试、科学计算、numpy 相关工作以及更多使用 ipython 的工作，将是一个非常有用的工具。
为了进行基准测试，您可以使用 ipython magic 使用 timeit 对代码进行计时，每个 运行 您将获得更一致的结果，这只是使用 timeit 然后使用函数或时间代码：
In [28]: timeit Horner(c,x)
1000 loops, best of 3: 670 µs per loop
In [29]: timeit naive(c,x)
1000 loops, best of 3: 983 µs per loop
In [30]: timeit itera(c,x)
1000 loops, best of 3: 804 µs per loop
要跨越一行以上的时间代码，您只需使用 %%timeit:
In [35]: %%timeit
....: for i in range(100):
....: i ** i
....:
10000 loops, best of 3: 110 µs per loop
ipython 可以 compile cython code, f2py 编码并使用不同的插件和 ipython 魔术命令完成许多其他非常有用的任务。
使用 cython 和一些非常基本的改进，我们可以将 Horner 的效率提高大约 25%：
In [166]: %%cython
import numpy as np
cimport numpy as np
cimport cython
ctypedef np.float_t DTYPE_t
def C_Horner(c, DTYPE_t x):
cdef DTYPE_t p
for i in reversed(c):
p = p * x + i
return p
In [28]: c=npr.uniform(size=(2000,1))
In [29]: timeit Horner(c,-1.34)
100 loops, best of 3: 3.93 ms per loop
In [30]: timeit C_Horner(c,-1.34)
100 loops, best of 3: 2.21 ms per loop
In [31]: timeit itera(c,x)
100 loops, best of 3: 4.10 ms per loop
In [32]: timeit naive(c,x)
100 loops, best of 3: 4.95 ms per loop
使用@Paul drapers 中的列表回答我们的 cythonised 版本 运行s 是原始函数的两倍，比 ietra 和 naive 快得多：
In [214]: import random
In [215]: c = [random.random() for _ in range(500)]
In [44]: timeit C_Horner(c, -1.34)
10000 loops, best of 3: 18.9 µs per loop
In [45]: timeit Horner(c, -1.34)
10000 loops, best of 3: 44.6 µs per loop
In [46]: timeit naive(c, -1.34)
10000 loops, best of 3: 167 µs per loop
In [47]: timeit itera(c,-1.34)
10000 loops, best of 3: 75.8 µs per loop
您的分析可以得到很大改进。另外，我们可以让您的代码 运行 快 200-500 倍。
(1) 冲洗并重复
您不能 运行 只进行一次性能测试迭代，原因有二。
- 您的时间分辨率可能不够好。这就是为什么您有时会为两个实现获得相同的时间：一个 运行 的时间接近您的计时机制的分辨率，因此您只记录了一个 "tick".
- 有各种 影响性能的因素。进行有意义的比较的最佳选择是多次迭代。
您不需要数以亿计的 运行s（当然，这并没有什么坏处），但是您可以估计并调整迭代次数，直到方差在您可以接受的水平内目的。
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
Whoa! All 时间变得更快了（10-60 倍）。按比例，Horner 的实现比其他两个更快。我们删除了所有三个的开销，现在可以看到 "bare bones" 差异。
Horner 比 naive 快 4 倍，比 itera 快 2 倍。
(3) 交替运行次
您正在使用 Python 2。我假设是 2.7。
让我们看看Python3.4票价如何。 （语法调整：您需要在参数列表周围加上括号 print。）
Horner 0.03298933599944576
naive 0.13706714100044337
itera 0.06771054599812487
差不多。
让我们试试 PyPy，Python 的 JIT 实现。 （"normal" Python 实现称为 CPython。）
Horner 0.006507158279418945
naive 0.07541298866271973
itera 0.005059003829956055
不错！每个实施现在 运行ning 快 2-5 倍。 Horner 现在的速度是 naive 的 10 倍，但比 itera 稍慢。
JIT 运行时间比解释器更难描述。让我们把迭代次数增加到50000次，试试看。
Horner 0.12749004364013672
naive 3.2823100090026855
itera 0.06546688079833984
（请注意，我们有 50 倍的迭代，但只有 20 倍的时间...JIT 在前 1000 运行 秒中的许多时间都没有完全发挥作用。）相同的结论，但差异更明显。
当然，JIT 的思想是在 运行 时间分析、分析和重写程序，所以如果您的目标是比较算法，这将添加很多不明显的实现细节。
None尽管如此，比较 运行 次可能有助于提供更广阔的视角。
还有一些事情。例如，您的天真实现计算了一个它从未使用过的变量。您使用 range 而不是 xrange。您可以尝试使用索引而不是反向切片向后迭代。等等
None 这些对我来说改变了很多结果，但它们值得考虑。