为何带额外计算时deque.append比list.append性能更慢？

我尝试实现一个固定最大长度的内存结构：其中a是列表，达到最大长度时弹出首个元素；b是collections.deque，依赖其内置的maxlen管理。按时间复杂度预期，deque的popleft和append均为O(1)，列表pop(0)为O(n)、append为O(1)，deque耗时应该更短。但实际测试中deque耗时更长；移除temp = element * i - i这行计算后，结果反转。请问代码中存在什么问题？为何无关计算会造成此差异？

测试代码 #

import time
import numpy as np
import collections

a = [np.ones((64, 64), dtype=np.int64) + i for i in range(100000)]
b = collections.deque(a, maxlen=100000)
element = np.ones((64, 64), dtype=np.int64)

time.sleep(0.5)  # 模拟额外初始化与预处理

t = time.time()
for i in range(10000):
    temp = element * i - i  # 模拟即时计算
    b.append(temp)
print(time.time() - t)

t = time.time()
for i in range(10000):
    temp = element * i - i  # 模拟即时计算
    if len(a) == 100000:
        a.pop(0)
    a.append(temp)
print(time.time() - t)
print(len(a))
print(len(b))

原因分析 #

1. "无关计算"实则影响CPU资源分配 #

temp = element * i - i是numpy的数组运算，属于CPU密集型操作，会占用绝大多数CPU周期：

• 列表的pop(0)虽然是O(n)复杂度，但此时CPU主要在处理numpy运算，列表的内存移动操作只能在CPU空闲间隙执行，其O(n)的开销被numpy运算的耗时掩盖，整体耗时由numpy主导。
• deque的append是O(1)，但底层双向链表的指针操作、内部状态维护，在CPU资源被占满时，会因为上下文切换、缓存命中率下降等问题，额外开销被放大，导致整体耗时反超列表。

2. deque的maxlen内置逻辑有额外开销 #

当deque达到maxlen后，每次append会自动触发popleft，这个过程虽然都是O(1)，但相比手动判断列表长度再执行pop(0)，deque内置的边界检查、状态同步等逻辑有更多的底层操作，这些操作在CPU紧张时会累积出可观的耗时。

3. 无CPU密集运算时的性能反转 #

移除numpy运算后，CPU资源充足：

• 列表的pop(0)需要移动100000个numpy数组的引用，O(n)的开销直接暴露，耗时急剧上升。
• deque的O(1)操作优势完全体现，耗时显著低于列表，符合时间复杂度的预期结论。

优化建议 #

• 若场景中存在大量CPU密集型运算，且固定长度容器的操作频率不高，列表实现可能更高效；但容器长度进一步增大时，列表的O(n)开销会爆发，需谨慎选择。
• 若追求稳定的O(1)性能，优先使用deque；同时避免在CPU满载场景下高频调用其操作，或考虑将容器操作与CPU密集型运算异步分离。

内容的提问来源于stack exchange，提问作者seermer