前言
理论上,Python列表结构可以实现队列的所有功能,甚至可以实现首尾元素的扩展和删减,这些操作利用其内置的函数就能实现,例如:
List.pop(0) , List.insert(0, element) , List.append(element), List.pop(-1)
然而列表的弹出操作速度效率缓慢,相比于collections库中集成的队列,执行效率差距几百上千倍,下面给出一段程序,来支撑我们的说法:
Code
from collections import deque
import timeit
res1 = [i for i in range(200000)] # 列表,初始化元素
res2 = deque(res1) # 队列,元素内容一致
def func1():
for _ in range(10000):
res1.pop(0)
def func2():
for _ in range(10000):
res2.popleft()
t1 = timeit.Timer(stmt="func1()", setup="from __main__ import func1")
t2 = timeit.Timer(stmt="func2()", setup="from __main__ import func2")
print(t1.timeit(number=20))
print(t2.timeit(number=20))
这段代码的意思是,初始化包含20万个相同元素的列表或队列,每次执行函数弹出每个数据结构首面的1万个元素,总共执行20次,分别返回总执行时间
执行效果
从图中可见,list结构的pop速度远慢于deque结构。我们进一步将上述代码中列表、队列初始化长度修改成30万,并让timtit函数执行30次,继续运行程序:
元素从20w扩展为30w,初始列表和队列长度大约要花费原本的1.5倍空间。从数值上发现,队列popleft()
30万次的总执行时间大约线性增加:从0.0105 s 到0.0165 s。然而这个规律不适用于列表:从3.3825 s到7.4936 s,花费时间甚至比直接翻倍还多一点。
pop()
或pop(-1)
的速度
上面的操作全是弹出数据结构的首元素,如果尝试弹出数据结构末尾元素会有什么区别呢?
我们仍然修改初始化长度为20W,重复执行20次。代码如下:
def func3():
for i in range(10000):
res1.pop() # 弹出末尾元素
def func4():
for j in range(10000):
res2.pop() # 同样弹出末尾元素
res1 = [i for i in range(200000)]
res2 = deque(res1)
t3 = timeit.Timer(stmt="func3()", setup="from __main__ import func3")
t4 = timeit.Timer(stmt="func4()", setup="from __main__ import func4")
print(t3.timeit(number=20))
执行效果:
对比之前多次弹出首元素的执行效果,首先发现List的操作要快上百倍,这说明列表pop()
行为要远比pop(0)
快。其次,deque的执行.pop()
与.popleft()
时间几乎没有发生变化,可忽略不计。最后,list关于.pop()
的速度仍然略慢于deque结构,但至少已经在相同数量级上了。
.append()
的速度
我们进一步进行了更有趣的尝试,测试两种数据结构在末尾添加元素的速度,总共给结构各添加20W次元素,代码:
def func3():
for i in range(10000):
res1.append(i)
def func4():
for j in range(10000):
res2.append(j)
res1 = []
res2 = deque()
t3 = timeit.Timer(stmt="func3()", setup="from __main__ import func3")
t4 = timeit.Timer(stmt="func4()", setup="from __main__ import func4")
print(t3.timeit(number=20))
print(t4.timeit(number=20))
执行了三次,结果如下:
得到如下结论:List和Deque在容器末尾的append()
扩展元素操作都要快于pop()
删除元素操作。并且,List结构在容器末尾的append()
操作慢于Deque结构,勉强仍在同一个数量级。
.appendleft()
的速度
继续搞事情,在2种数据结构的最左侧插入元素,重复20W次插入操作,查看执行时间,代码:
def func5():
for i in range(10000):
res1.insert(0, i)
def func6():
for j in range(10000):
res2.appendleft(j)
res1 = []
res2 = deque()
t3 = timeit.Timer(stmt="func5()", setup="from __main__ import func5")
t4 = timeit.Timer(stmt="func6()", setup="from __main__ import func6")
print(t3.timeit(number=20))
print(t4.timeit(number=20))
执行结果:
对比之前的pop(0)
或popleft()
操作,可以得出如下结论。List在容器头部pop
元素快于insert
元素(3.3825 s < 6.4277 s);Deque在容器头部popleft
元素基本和appendleft
元素一样快(0.01052 ≈ 0.0107)。
综上所述
- 列表关于
pop\append\insert
之类的各项操作的性能都比队列要慢,估计index、reserve、count、remove
等操作也要慢,但还并没有得到我的验证。 - 队列的
pop\popleft\append\appendleft
各种操作的时间几乎完全一样,并且各种操作的执行时间随着元素数目变化而线性增加、缩减,然而列表某些操作的时间几乎做不到线性变化。 - 无论队列还是列表,在容器末尾的操作执行时间都要快于容器开头,这在列表结构上表现出的差异尤其显著,相差上百倍。
- 无论队列还是列表,无论是容器末尾或容器开头,插入元素似乎都比删除元素更费时一点,这也许是因为要分配内存,花费更多时间。