内置函数与递归函数
我既不是数学家，也不是计算机科学家--只是一个业余程序员，我正试图通过做Euler Project的问题来自学Python。其中之一需要使用阶乘。我使用递归函数编写了自己的计算，然后意识到可能有一个我可以使用的内置函数。找到它后，我想我会发现它比我的递归函数要快得多。令我惊讶的是，我发现它实际上更慢。
有没有人对此感到惊讶？我只是好奇。
我附上了我的代码(为了更好地衡量，我还包含了一个用于额外比较的循环方法)。
import math
import time
x = 50
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
secs = time.clock()
print(math.factorial(x))
print ("The built-in function took {a:0.5f} seconds.".format(a = time.clock() - secs))
secs = time.clock()
print (factorial(x))
print ("The recursive function took {a:0.5f} seconds.".format(a = time.clock() - secs))
secs = time.clock()
factl = 1
for i in range (1,x+1):
factl *= i
print (factl)
print ("The loop method took {a:0.5f} seconds.".format(a = time.clock() - secs))输出：
30414093201713378043612608166064768844377641568960512000000000000
内置函数耗时0.00549秒。
30414093201713378043612608166064768844377641568960512000000000000
递归函数耗时0.00299秒。
30414093201713378043612608166064768844377641568960512000000000000
循环方法耗时0.00259秒。
回答 3
Stack Overflow用户
发布于 2016-06-28 19:48:39
我采用了您的代码，并多次更改了测试这三个方法的顺序。我注意到测试的第一种方法通常比第二种方法花费两倍的时间。
我真的不能解释为什么，但我知道你不能用一次迭代来衡量一个函数的性能。你必须多次重复这个函数，并计算平均时间。
IPython提供了一个方便的“神奇方法”timeit，它可以做到这一点：
print('math')
%timeit math.factorial(x)
print('factorial')
%timeit factorial(x)
print('loop')
%timeit loopmethod(x)输出：
数学
最慢的跑比最快的多花了33.62倍。这可能意味着中间结果正在被缓存。
1000000个环路，最好3: 1.25µs/环路阶乘
100000个循环，最好3个:每个循环19.4µs
100000个环路，最好3: 7.87µs/环路
内置函数的速度平均是递归函数的10倍。
Stack Overflow用户
发布于 2016-06-28 20:11:26
即使不使用性能分析库，通过调整代码使其不会计时打印，您也可以看到内置方法比递归方法更好：
import math
import time
x = 50
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
secs = time.clock()
f = math.factorial(x)
elapsed = time.clock() - secs
print(f)
print ("The built-in function took {a:0.5f} seconds.".format(a = elapsed))
secs = time.clock()
f = factorial(x)
elapsed = time.clock() - secs
print (f)
print ("The recursive function took {a:0.5f} seconds.".format(a = elapsed))
secs = time.clock()
factl = 1
for i in range (1,x+1):
factl *= i
elapsed = time.clock() - secs
print (factl)
print ("The loop method took {a:0.5f} seconds.".format(a = elapsed))典型运行：
30414093201713378043612608166064768844377641568960512000000000000
The built-in function took 0.00001 seconds.
30414093201713378043612608166064768844377641568960512000000000000
The recursive function took 0.00011 seconds.
30414093201713378043612608166064768844377641568960512000000000000
The loop method took 0.00004 seconds.Stack Overflow用户
发布于 2016-06-28 20:01:56
为了更好地比较不同函数的效率，您需要在较长的时间内多次运行测试，同时在它们之间交替运行，并为每个被测试的函数花费最快的时间。
由于后台运行的进程的活动，执行时间可能会因当前的机器负载而变化很大。对于每个被测试的函数，采取最快的时间应该会最小化由于其他进程同时运行而造成的任何中断的影响。诸如打印到终端之类的输入/输出操作更加耗时，因此我建议您只运行factorial(x)而不是print (factorial(x))。
您可能还想看看Python3 profilers library，它是专门用来报告程序各个部分的执行时间的。对于单个函数的基准标记，timeit模块会更合适。
https://stackoverflow.com/questions/38074742
复制相似问题
腾讯云开发者
