Python deque在小可迭代对象中的性能

Question

我在玩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)

这个测试会从不同大小的列表和deque中删除第一个元素。结果是：

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

我想问的是：为什么小的deque和列表（大约1000个元素）在性能上几乎是一样的呢？

Answer 1

对于元素数量少的情况，构建双端队列和列表所花费的时间是比较明显的。

但是一旦元素数量增多，这个时间在结果中就不再显著了。

可以把测试重写一下，把列表的构建放到时间测试的外面。

补充：正如@Interjar所指出的，类的初始化是在方法计时之外进行的，所以这并不是导致少量数据时计时相似的原因。

Answer 2

我发现用timeit在命令行中更方便。比如说：

$ 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

在这种情况下，必要的注意事项（比如在循环外部进行导入，在循环内部创建数据的新副本）就更容易看出来并且实现了...

Answer 3

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的大小，因为它是空的。这个检查对于列表和双端队列（deque）来说，所花的时间大致是一样的。

对于小的列表或双端队列，第一次运行的时间相对于后面999999次的总时间来说是很短的，所以你实际上并没有测量到什么有用的东西，得到的时间也差不多。

如果你把number==1设置成1，就不会有这个问题了。另一个选择是让计时的代码进行添加和删除操作，这样列表或双端队列的大小就能保持一致。