Python计时 - 一定有更好的方法！

Question

我希望有人能帮我解决这个问题。

我想测量排序算法的性能。现在我用的方式是这样的：

M = 1000 # number of executions
N = [1000, 2000, 4000, 16000] # size of the list
L = [100, 1000, 2000,16000] # max element of the list

# timing:
print 'Number of executions: %i' % (M)
print '-'*80
print '\tL\N\t|\t%i\t|\t%i\t|\t%i\t|\t%i' % (N[0], N[1], N[2], N[3])
print '-'*80
for l in L:
    print '\t%i\t' % l,
    for n in N: 
        t = 0
        for m in xrange(M):
            A = [random.randint(0,l-1) for r in xrange(n)] # generates an n long random list
            t0 = time.clock()
            pass # sort function call goes here
            t1 = time.clock()
            t += (t1-t0)
        print '|\t%0.3f\t' % ((t*1000.0)/M ), # avg time
    print
print '-'*80

这个空测试大约需要4分钟。我希望能得到一些建议，让它更快。

谢谢！

编辑：在Rafe Kettler的提示之后，我想出了这个：

def sorting(LST):
    pass

if __name__ == "__main__" :
    M = 1000
    N = [1000, 2000, 4000, 16000]
    L = [100, 1000, 2000,16000]

    print 'Number of executions: %i' % (M)
    print '-'*80
    print '\tL\N\t|\t%i\t|\t%i\t|\t%i\t|\t%i' % (N[0], N[1], N[2], N[3])
    print '-'*80
    for l in L:
        print '\t%i\t' % l,
        for n in N:
            #------------------------
            t = timeit.Timer('sorting([random.randint(0,l-1) for r in xrange(n)])', 'from __main__ import sorting, n, l, random')
            #------------------------
            print '|\t%0.3f\t' % (t.timeit(M)/M ), # avg time
        print
    print '-'*80

不幸的是，这样反而变慢了。我哪里做错了呢？

Answer 1

生成随机数是一项耗时的工作。你需要生成4*1000*(1000+2000+4000+16000)个随机数。就连最简单的测试案例在我的系统上都要花超过7分钟：

>>> t=timeit.Timer('random.randint(0,15999)','import random')
>>> t.timeit(4*1000*(1000+2000+4000+16000))
447.08869618904077

正如我在评论中提到的，非常重要的一点是，要把生成测试数据的时间从你要测试的算法的时间中排除出去。

Answer 2

你可以用下面的代码替换这段代码：

A = [random.randint(0,l-1) for r in xrange(n)]

用生成器来实现，比如：

def A(n):
    for r in xrange(n):
        yield random.randint(0,l-1)

我觉得，在你的空测试中，大部分时间都是在生成随机列表。

Answer 3

timeit 是在Python中测量代码运行时间的最佳工具。你可以把你的算法整理成函数，然后用 timeit 来测试这些函数的执行时间。