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 回答