小型迭代的 Python 双端队列性能

我在玩弄 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 个元素)的性能几乎相同？

请您参考如下方法:

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 你就不会遇到这个问题。另一种选择是让定时代码推送和弹出一个项目，以便列表/双端队列保持相同的大小。