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

很遗憾它变得更慢了。我做错了什么？

- Stiggo

Answer 1

timeit。Python 中最好的计时方法，无可争议。将算法重构为函数，并使用 timeit 测试执行时间。

- Rafe Kettler

---

一定要在计时函数之外设置测试数据！ - Mark Ransom

感谢及时通知 timeit！ - Stiggo

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)

我认为，你的空测试大部分时间都是随机列表生成。

- seriyPS

---

生成器表达式：A = (random.randint(0,l-1) for r in xrange(n)) - codewarrior

我已经尝试过使用[]和()，它们之间只有几秒钟的差距。我知道生成随机数是一个耗时的任务。但一定有更快的方法。我还没有找到它。希望我能找到。 - Stiggo

Answer 3

生成随机数是一项耗时的任务。您需要创建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

正如我在评论中所说的，从测试数据创建的时间中排除算法测试的时间非常重要。

- Mark Ransom

---

我知道这是92000000个随机数，需要很长时间。但是目前我不知道如何为每次重复生成一个新的随机列表。我想为每1000 * 4次"准确性"（或"更详细的图片"，抱歉我不知道正确的英语表达）使用一个新的输入列表。 - Stiggo

@Stiggo，我并不建议你改变生成测试数据的方式，只是想解释无论你如何做，它都需要很长时间。只需更改测试的参数，使数据生成不被计算，并接受运行需要很长时间的事实。 - Mark Ransom

Answer 4

虽然没有完全回答时间问题，但是您可以使用numpy包中的随机模块来非常高效地生成大量随机数数组：

>>> from numpy import random
>>> l = 100; n = 16000
>>> random.randint(0,l-1,n)

改编OP的脚本，下面是使用numpy.random与标准random模块比较的总时间。

numpy.random
number of executions: 1000
--------------------------------------------------------------------------------
        L\N     |       1000    |       2000    |       4000    |       16000
--------------------------------------------------------------------------------
        100     |       0.022   |       0.043   |       0.084   |       0.332
        1000    |       0.016   |       0.031   |       0.059   |       0.231
        2000    |       0.016   |       0.030   |       0.059   |       0.231
        16000   |       0.016   |       0.030   |       0.059   |       0.231
--------------------------------------------------------------------------------

random 
Number of executions: 1000
--------------------------------------------------------------------------------
        L\N     |       1000    |       2000    |       4000    |       16000
--------------------------------------------------------------------------------
        100     |       2.152   |       4.271   |       8.649   |       34.007
        1000    |       2.264   |       4.501   |       8.762   |       34.956
        2000    |       2.202   |       4.412   |       8.743   |       34.818
        16000   |       2.205   |       4.398   |       8.735   |       34.823
--------------------------------------------------------------------------------

- LmW.

Answer 5

只需生成随机数一次。将它们放入一个shelve或pickle文件中，需要运行测试时再读取出来。

- Martlark