如何在Python中测量算法运行时间

Question

可能的重复问题：
在Python中准确计时函数
准确测量Python函数运行时间

我该如何测量和比较我用Python写的算法的运行时间？如果可以的话，给我推荐一个像StackOverflow这样好的算法网站或论坛。

Answer 1

这个模块 timeit 很有用，并且它是Python标准版自带的。

举个例子：

import timeit
timeit.Timer('for i in xrange(10): oct(i)').timeit()

Answer 2

对于一些小的算法，你可以使用Python文档中的timeit模块。

def test():
    "Stupid test function"
    L = []
    for i in range(100):
        L.append(i)

if __name__=='__main__':
    from timeit import Timer
    t = Timer("test()", "from __main__ import test")
    print t.timeit()

虽然不够精确，但你也可以像这样使用time模块：

from time import time
t0 = time()
call_mifuntion_vers_1()
t1 = time()
call_mifunction_vers_2()
t2 = time()

print 'function vers1 takes %f' %(t1-t0)
print 'function vers2 takes %f' %(t2-t1)

Answer 3

我不太确定“我用Python写的算法的运行时间”具体指的是什么，所以我想从更广泛的角度来看看一些可能的答案。

• 算法本身没有运行时间；我们可以给具体的实现计时，但算法是一种抽象的方法。优化程序时，最常见且最重要的部分是分析算法，通常使用渐进分析来计算大O复杂度，包括时间、空间、磁盘使用等。

  计算机实际上无法为你完成这一步。这需要你做一些数学计算来弄清楚某个东西是如何工作的。优化这一部分是实现可扩展性能的关键。

• 你可以给具体的实现计时。在Python中，最简单的方法是使用timeit。它的使用方式通常是创建一个模块，里面有一个函数封装你想要调用的内容，然后通过命令行用python -m timeit ...来调用。

  使用timeit来比较多个代码片段时，适合做微优化，但通常不适合用来比较两种不同的算法。你可能更需要的是渐进分析，但也有可能你需要更复杂的分析方式。

• 你需要知道该计时什么。 大多数代码片段并不值得优化。你需要在真正重要的地方进行改动，尤其是当你在做微优化，而不是改善算法的渐进复杂度时。

  如果你把一个函数的速度提高四倍，但你的代码在这个函数上只花了1%的时间，那这并不算真正的加速。如果你在一个函数上提高了20%的速度，而这个函数占了你程序50%的时间，那你就真的有收获了。

  要确定一个真实的Python程序花费的时间，可以使用标准库的性能分析工具。这会告诉你在一个示例程序中，代码花费时间的地方。