526互联

Python 列表与队列弹出元素的速度对比

发布时间 2023-09-08 13:16:50作者: 爱吃砂糖橘的白龙

前言

理论上，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各种操作的时间几乎完全一样，并且各种操作的执行时间随着元素数目变化而线性增加、缩减，然而列表某些操作的时间几乎做不到线性变化。
  • 无论队列还是列表，在容器末尾的操作执行时间都要快于容器开头，这在列表结构上表现出的差异尤其显著，相差上百倍。
  • 无论队列还是列表，无论是容器末尾或容器开头，插入元素似乎都比删除元素更费时一点，这也许是因为要分配内存，花费更多时间。