1

我在玩 Python 的 collection.deque 并编写了以下基准:

#!/usr/bin/python

import timeit

if __name__=='__main__':
    number = 1000000
    for r in (1,10,100,1000,5000,10000,100000):
        print r
        print timeit.timeit("while x: x.pop(0);",
                            "x = list(range("+str(r)+"))",
                            number=number)
        print timeit.timeit("while x: x.popleft();",
                            "from collections import deque; x = deque(range("+str(r)+"))",
                             number=number)

这将从具有各种大小的列表/双端队列中弹出(0)/popleft()。结果是:

1
0.0801048278809
0.0822219848633
10
0.081041097641
0.080836057663
100
0.0806250572205
0.0807700157166
1000
0.081248998642
0.082062959671
5000
0.0976719856262
0.0825741291046
10000
0.157499074936
0.0825819969177
100000
16.0247170925
0.097559928894

我的问题是:为什么小型双端队列和列表(约 1000 个元素)的性能几乎相同?

4

3 回答 3

4

timeit 模块运行一次设置代码,然后运行定时代码number时间(在这种情况下,number==1000000)。在您的情况下,这看起来像(对于列表情况):

x = list(range(r))
#timer is started here
for iteration in xrange(1000000):
    while x: x.pop(0)
#timer is stopped here

如您所见,只有第一次迭代会做任何事情,而其他 999999 次迭代只会检查x一次的大小,因为它将为空。对于列表和双端队列,此检查将花费大约相同的时间。

对于小型列表/双端队列,第一次迭代相对于其他 999999 次迭代组合来说很短,所以你并没有真正测量任何相关的东西,并且得到相似的时间。

如果你使用number==1你不会有这个问题。另一种选择是让定时代码推送和弹出一个项目,以便列表/双端队列保持相同的大小。

于 2010-01-16T13:49:21.500 回答
3

我总是发现timeit更适合从 shell 命令行使用。在这里,例如:

$ python -mtimeit -s'from collections import deque; base=range(100); ctr=list' 'x=ctr(base)' 'while x: x.pop(0)'
10000 loops, best of 3: 77.3 usec per loop
$ python -mtimeit -s'from collections import deque; base=range(100); ctr=deque' 'x=ctr(base)' 'while x: x.popleft()'
10000 loops, best of 3: 36 usec per loop

所需的预防措施(在循环外进行导入,在循环内制作数据的新副本)更容易查看和实施,这样......

于 2010-01-16T16:08:06.673 回答
2

对于少量元素,构建双端队列和列表所花费的时间很重要。

一旦 f 元素的数量增加,这在结果中就不再重要了。

重写测试,使列表的构造在 timeit 调用之外。

编辑:正如@Interjar 指出的那样,类的初始化是在方法计时之外完成的,因此这不是在条目数量较少时出现类似计时的原因。

于 2010-01-16T12:58:59.647 回答