对于小iterables

Question

我是用Python的collection.deque玩耍，并写了下面的基准Python的双端队列性能：

#!/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元）的表现几乎一样吗？

Answer 1

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大小，一旦因为它是空的。这项检查将花费大约相同的时间为列表和deques。

对于小型列表/ deques，第一次迭代相对于其他999999次迭代的总和较短，因此您并不真正测量任何相关的内容，并获得相似的时间。如果你使用number==1，你不会有这个问题。另一种选择是让定时代码推送并弹出一个项目，以便列表/代名词保持相同的大小。

Answer 2

对于数量较少的元素，构建双端队列和列表花费的时间很长。

一旦f个元素的数量增加，结果就不再显着。

重写测试，以便构建列表不在t​​imeit调用中。

编辑：正如@Interjar指出的那样，类的初始化是在方法时间之外完成的，所以这不是低数目条目类似时间的原因。

Answer 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 

所需要的注意事项（做外循环的进口，使回路中的数据的新副本）是这么容易看到和执行，这样...