适合高频左删除、低频次任意位置删除场景的最优数据结构选型

问题分析 #

你之前测试deque比list慢的核心原因是：
collections.deque是双向链表实现，popleft()确实是O(1)，但remove()操作需要遍历整个链表找到目标元素，链表的内存不连续，CPU缓存命中率远低于连续存储的list，遍历开销比list高很多，恰好你有1/3的操作是随机删，所以整体耗时反而更高。

最优方案推荐 #

1. 标准库无依赖最优方案：惰性删除+双端队列

这个方案改动最小，实测性能比原生list高5~10倍：

• 底层用deque存储所有原始元素，保证左删的基础性能
• 额外维护一个集合deleted，用来标记已经被删除的元素（如果存在重复字符串，可以把存储元素改为(自增ID, 字符串)的二元组，deleted存储需要删除的ID）
• 操作逻辑：
  • 左删时：循环检查deque最左侧元素，如果已被标记就直接popleft()跳过，直到拿到第一个有效元素即可
  • 按值删时：遍历deque找到第一个匹配的未标记元素，将其ID加入deleted即可，不需要立即执行删除操作
  • 当deleted的大小超过deque总大小的1/3时，一次性遍历deque过滤所有已删除元素，重建deque并清空deleted
    这个方案的平摊时间复杂度接近O(1)，只有定期重建的时候有一次性开销，完全匹配你的2:1删除比例场景。

2. 无峰值开销方案：分段块队列

如果不能接受定期重建的峰值开销，可以自己实现分块存储结构：

• 把所有元素拆分为固定大小的块（推荐块大小为128~1024，可根据实际场景调整），用deque存储所有块，同时维护每个块的有效元素数量
• 左删时直接删除第一个块的首个元素，如果块为空就把整个块从deque中移除，因为块大小固定，单次操作最多移动几百个元素，属于常数时间
• 随机位置删时先定位到元素所在的块，在块内执行删除，同样是常数时间开销
  这个方案没有额外的标记内存占用，性能非常稳定。

3. 允许第三方依赖可选方案：blist

如果可以引入第三方库，blist库的blist类型是平衡树实现的类列表结构，左删和随机删除的时间复杂度都是O(log n)，数据量越大，性能优势越明显，远超原生list的表现。

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