为什么Python中List的入队出队速度比基于deque实现的Queue更快？

测试方案 #

本次对比两类队列实现的enqueue、dequeue性能：

• 内置列表实现：入队调用list.insert(0, value)方法，出队调用list.pop()方法
• 自定义Queue实现：基于collections.deque封装的队列类，入队调用enqueue(value)方法，出队调用dequeue()方法

测试代码 #

性能测试主代码 #

import timeit

# 列表实现测试代码
List_Code = '''
def M_N_List(M, N):
    from random import randint
    no_of_integers = N
    list = []
    for i in range(M):
        for i in range(no_of_integers):
            list.insert(0 , randint(1, 100))
        for i in range(no_of_integers):
            list.pop()            

M_N_List(15,20)
'''
print("List : ")
print ("Code Run Time = " , round(timeit.timeit(stmt = List_Code,
                     number = 10000) , 4) , "seconds")

# 自定义队列实现测试代码
Queue_Code = '''
def M_N_Queue(M,N):
    from Queue import Queue
    from random import randint
    no_of_integers = N
    queue = Queue()
    for i in range(M):
        for i in range(no_of_integers):
            queue.enqueue(randint(1,100))
        for i in range(no_of_integers):
            queue.dequeue()

M_N_Queue(15,20)
'''
print("")
print("Queue : ")
print ("Code Run Time = " , round(timeit.timeit(stmt = Queue_Code,
                     number = 10000) , 4) , "seconds")

自定义Queue类实现 #

import ctypes
from collections import deque

class Queue:
    def __init__(self):
        self.buffer = deque()
    def size(self):
        return len(self.buffer)
    def make_array(self,new_cap):
        return (new_cap * ctypes.py_object)()
    def __getitem__(self, k):
        if not 0 <= k < len(self.buffer):
            return IndexError("k is out of bounds")
        return self.buffer[k]
    def enqueue(self, val):
        self.buffer.appendleft(val)
    def dequeue(self):
        return self.buffer.pop()
    def is_empty(self):
        return len(self.buffer) == 0

问题描述 #

理论上Python列表的头部插入操作时间复杂度为O(n)，deque的两端插入操作时间复杂度为O(1)，自定义Queue的性能理应优于列表实现，但实测Queue耗时更长，和大O时间复杂度结论不符。

异常原因分析 #

• 测试数据量过小，大O复杂度优势未体现：本次测试每轮仅执行20次入队操作，列表最大长度仅为20，O(n)的n极小时，移动元素的开销极低，时间复杂度的差异完全被常数项开销覆盖。如果将测试参数调整为M=10、N=10000，就能看到列表耗时暴涨，远高于自定义Queue。
• 自定义类的方法调用额外开销：自定义Queue的enqueue、dequeue都是Python层面的方法，每次调用都需要创建栈帧、参数校验等额外开销，而列表的insert、pop都是底层C实现的内置方法，调用开销远低于自定义Python方法。小数据量场景下，这部分额外开销完全盖过了deque本身的性能优势。
• 测试代码的冗余导入开销：Queue测试代码中将from Queue import Queue放在了函数内部，timeit每执行一次测试用例都会触发一次模块导入操作，额外增加了Queue的测试耗时，而列表实现没有这部分导入开销。
• 小容量场景下列表的缓存优势：列表是连续内存存储，小容量下CPU缓存命中率更高，deque采用近似双端链表的实现，节点内存分散，小数据量下缓存命中率反而低于列表，进一步抵消了时间复杂度的优势。

内容的提问来源于stack exchange，提问作者Mubashir Ahmed Siddiqui