Python 标准库高性能容器与算法：collections / bisect / heapq

更新时间：2026-09-02。本篇回答：为什么用 list 当队列会慢成 O(n²)？统计词频、取 Top-K、在有序表里查找，标准库分别给了什么更快的工具？ 上一篇 内置数据结构 讲了 list/dict/set 的复杂度，这篇补齐它们「专业分工」的亲戚——全部是纯标准库、无需安装、Python 3.6 行为一致。

一、一张表先看选型

你的主操作	别用	用它	关键复杂度
两端增删（队列/栈/滑动窗口/最近 N 条）	list.pop(0) / insert(0,x)	collections.deque	两端 O(1)，中间访问 O(n)
按下标随机读写为主	—	list	随机访问 O(1)
「键不存在就给默认值」的计数/分组	if k in d / setdefault	collections.defaultdict	缺键自动构造 O(1)
统计频次 / 取 Top-K 高频	手写字典 + sorted	collections.Counter	统计 C 级；most_common(k) O(n log k)
在已排序序列里查找/插值	list.index 线性扫	bisect	查找 O(log n)，插入仍 O(n)
动态取最大/最小、优先队列、Top-K	每次 sorted	heapq	堆顶 O(1)，增删 O(log n)
多路有序流归并（日志/外部排序）	拼接后全排序	heapq.merge	O(n log k)，且惰性
大量只读的「具名字段」记录	普通 class（每实例 __dict__）	collections.namedtuple	无 __dict__，省内存

一句话：list/dict 是通用件，collections/bisect/heapq 是为特定访问模式定制的专用件——主操作对了，复杂度能差一个数量级。

二、deque：两端 O(1) 的队列，list 头部操作是 O(n)

list 是连续内存的动态数组：尾部追加 O(1)，但头部 pop(0) / insert(0, x) 要把后面所有元素整体搬移，是 O(n)。在循环里反复头部操作就是 O(n²)。

collections.deque（double-ended queue）底层是分块双向链表（CPython 每块存 64 个指针），两端增删都是 O(1)：

from collections import deque

q = deque()
q.append(1)        # 右端进  O(1)
q.appendleft(2)    # 左端进  O(1)
q.pop()            # 右端出  O(1)
q.popleft()        # 左端出  O(1)

# 定长滑动窗口：满了自动从对端挤掉，不用手写溢出
recent = deque(maxlen=100)
for x in stream:
    recent.append(x)        # 永远只留最近 100 个

实测（demo d1，N 次进 + N 次出的 FIFO）：

N	list append+pop(0)	deque append+popleft	加速比
2 万	0.047 s	0.004 s	12x
10 万	2.410 s	0.020 s	118x

N 从 2 万涨到 10 万（5 倍），list 耗时涨 51 倍（O(n²) 的特征），deque 只涨 5 倍（O(n)）。滑动窗口场景 deque 也快约 3x 且省掉手动溢出逻辑。

但 deque 不是万能：随机按下标访问 dq[i] 要沿块链跳，中间位置是 O(n)。实测 2 万次随机访问，list[i] 0.003 s、deque[i] 0.010 s（list 快 3.4x）。队列/栈/滑动窗口/最近记录用 deque；按下标随机读写为主还是 list。

deque 也是线程安全的（append/pop 用 GIL 保证原子），常被用作多线程任务队列；但「检查再操作」的复合逻辑仍要自己加锁。

2.1 为什么 deque 两端快、中间慢

CPython 的 deque 不是「带指针的链表节点」，而是分块双链表：一个块（block）存 64 个 PyObject*，块之间用双向链表串起来。

• 两端增删：只动当前端块的槽位，满了就新挂一个块，O(1)；
• 随机访问 dq[i]：要先算 i 落在第几块（沿块链表数过去），再进块偏移，中间位置要串过多块，退化为 O(n)；
• 内存局部性比「每节点一对象」的链表好（一块 64 项连续），但仍不如 list 的一整段连续数组——这也是 dq[i] 比 lst[i] 慢的硬件层原因（缓存不友好，对应本站 缓存友好代码 主线）。

list 则是一整段连续的指针数组：随机访问 O(1) 且缓存友好，但头部增删要把整段 memmove 搬移。记住这张物理图，选型就不会反。

三、defaultdict 与 Counter：映射的两个专用件

3.1 defaultdict：消掉「缺键初始化」样板

统计、分组时常写「键不存在就先建空容器」：

# 老写法：每次都要判断/setdefault
groups = {}
for k, v in pairs:
    if k not in groups:
        groups[k] = []
    groups[k].append(v)
# 或 groups.setdefault(k, []).append(v)

# defaultdict：缺键时自动调用工厂函数造一个
from collections import defaultdict
groups = defaultdict(list)        # 缺键 -> 自动建 []
for k, v in pairs:
    groups[k].append(v)

counts = defaultdict(int)         # 缺键 -> 自动 0，计数直接 +=
counts["x"] += 1

defaultdict(factory) 遇到不存在的键时，会调一次 factory() 把结果存进去再返回——list 造空列表、set 造空集合、int 造 0。实测 20 万次分组，defaultdict(list) 0.024 s vs setdefault 0.042 s（约 1.75x），且意图更清晰。

工厂可以是任意可调用对象，做「懒初始化」很顺手：

from collections import defaultdict

# 每个键第一次访问时连上一个资源（连接池/计数器/子表）
pools = defaultdict(lambda: create_connection())
pools["db-a"].query(...)        # 首次自动建连，之后复用

# 嵌套结构：一键多值多集合
index = defaultdict(lambda: defaultdict(list))
index["user"]["events"].append(...)   # 两层都自动建

坑：defaultdict(list) 会「无中生有」——你只是查询 d["不存在"] 也会真的插入一个空列表。不想插入用 d.get(k)；依赖「访问即建」做初始化时要心里有数。

3.2 Counter：为「计数」而生的 dict 子类

Counter 是 dict 的子类，统计频次一行搞定，统计循环跑在 C 层：

from collections import Counter

freq = Counter(words)            # 直接喂可迭代对象，完成计数
freq.most_common(10)             # 频次最高的 10 个 [(word, count), ...]
freq["anything"]                 # 查不存在的键返回 0，不抛 KeyError
freq.update(more_words)          # 继续累加
c1 + c2; c1 - c2                 # 计数器可加减（multiset 语义）

实测（demo d2，100 万个词）：

写法	耗时
裸 dict + if k in d	0.249 s
dict.get(k, 0) + 1	0.262 s
Counter(words)	0.121 s（约 2x）

取 Top-10 高频词：Counter.most_common(10) 0.123 s vs 全表 sorted(...)[:10] 0.275 s（2.2x）。原理：most_common(k) 内部用堆，只维护最大的 k 个，复杂度 O(n log k)；而 sorted 是全排序 O(n log n)——n 越大、k 越小，差距越大（这正是第五节 heapq 的主题）。

四、bisect：有序序列上的二分查找 O(log n)

list.index(x) 和 x in list 都是线性扫描 O(n)。如果列表本身是有序的，用 bisect 二分查找只要 O(log n)——20 万元素只需约 18 次比较，而线性平均要 10 万次。

from bisect import bisect_left, bisect_right, insort

a = sorted([3, 1, 4, 1, 5, 9, 2, 6])     # 必须先有序

# 查找：bisect_left 返回 x 应插入的位置（左边界）
i = bisect_left(a, 4)
found = i < len(a) and a[i] == 4         # 该位置真的是 4 才算命中

# 重复元素：left 返回第一个、right 返回最后一个之后
lo = bisect_left(a, 1)                   # 区间 [lo, hi) 内全是 1
hi = bisect_right(a, 1)

# 插入并保持有序（二分定位 O(log n) + 搬元素 O(n)）
insort(a, 7)

实测（demo d3，有序表 3 万元素、1000 次查询）：命中查找时线性 list.index 0.158 s、bisect_left 0.001 s（188x）；查找不存在的键时线性要扫到尾还抛异常 0.323 s（527x——log₂(3e4)≈15 次比较 vs 平均 1.5 万次）；流式保序插入（边到边插、每次插完都有序）1000 次时，insort（二分定位）0.004 s，「每来一个就整体 sort」0.222 s（51x）。

bisect 有个常被忽略的妙用：区间映射（查表代替 if-elif 链）：

# 按分数定等级：不用写一长串 if，用分界点二分
breakpoints = [60, 75, 90]
grades = ["不及格", "及格", "良好", "优秀"]
grade = grades[bisect_right(breakpoints, score)]   # score=85 -> 位置 2 -> "良好"

关键边界：bisect 只在已排序序列上成立，插入无序元素后必须重新排序。而且 insort 后半段仍是 O(n) 搬移——bisect 适合「一次排序、海量查找」；边插边频繁取最值用 heapq；数据持续大规模增删则应考虑外部结构或数据库索引。

五、heapq：堆——Top-K、优先队列、有序流归并

heapq 实现的是最小堆：heap[0] 永远是最小元素，入堆/出堆都是 O(log n)。它直接拿普通 list 当堆（heapify 原地建堆 O(n)）。

import heapq

h = []
heapq.heappush(h, 3)          # 入堆 O(log n)
heapq.heappush(h, 1)
heapq.heappush(h, 2)
heapq.heappop(h)              # 弹出最小 1，O(log n)

nums = [5, 2, 8, 1, 9, 3]
heapq.heapify(nums)           # 原地建堆 O(n)
heapq.nlargest(3, nums)       # [9, 8, 5]  Top-K，O(n log k)
heapq.nsmallest(2, nums)      # [1, 2]

# 优先队列：元素是 (优先级, 序号, 数据)，元组按优先级比较
heapq.heappush(tasks, (5, seq, "低优先级任务"))
heapq.heappush(tasks, (1, seq, "高优先级任务"))
_, _, task = heapq.heappop(tasks)   # 永远先出优先级最高的

# 多路有序流归并（日志合并、外部排序核心），惰性生成器
for item in heapq.merge(sorted_log_a, sorted_log_b, sorted_log_c):
    ...

实测（demo d4，200 万个浮点数取 Top-20）：

写法	耗时	说明
sorted(data, reverse=True)[:20]	1.188 s	全排序 O(n log n)，为 20 个结果排了 200 万
heapq.nlargest(20, data)	0.045 s	O(n log k)，快 26 倍
手写长度 20 小顶堆	0.302 s	O(n log k)，比全排序快 3.9x

手写堆比库函数慢，是因为 nlargest 的堆维护在 C 层。理解原理用手写，生产用 nlargest。 另实测：3 路各 10 万的有序流归并，heapq.merge 比「拼接后全排序」快且是惰性的——边读边归并、不必全读进内存，正是处理超大日志/外部排序的思路。

什么时候堆不划算：要全部有序就直接 sorted（Timsort 实测比手写堆排序快约 2.4x）。堆的价值在「只要部分极值」「动态维护最值」「流式到来」——n 越大、k 越小，O(n log k) 相对 O(n log n) 优势越大。

5.1 一个能直接用的优先级调度器

任务随时到来、每次取优先级最高的，且要自动去重（同 key 任务只留最新优先级）：

import heapq, itertools

class PriorityQueue:
    def __init__(self):
        self._heap = []
        self._counter = itertools.count()   # 自增序号，做稳定排序 + 防元素不可比
        self._active = {}                    # key -> (prio, seq)，用于去重/更新

    def push(self, key, prio):
        seq = next(self._counter)
        self._active[key] = (prio, seq)
        heapq.heappush(self._heap, (prio, seq, key))

    def pop(self):
        while self._heap:
            prio, seq, key = heapq.heappop(self._heap)
            active = self._active.get(key)
            if active == (prio, seq):        # 是最新的一条；不是则为陈旧条目，跳过
                del self._active[key]
                return prio, key
            # 否则是被更新过的陈旧条目，丢弃继续 pop（惰性删除）
        raise IndexError("empty queue")

这正是 asyncio 事件循环定时器堆（handles + 序号）和 Dijkstra 最短路径「松弛」的标准写法：不修改堆里的旧条目，而是压入新条目、弹出时校验是否过期，绕开「堆中改值要重新 sift」的麻烦。

六、namedtuple 与 OrderedDict：省内存的记录与 LRU

6.1 namedtuple：介于 tuple 和 class 之间

tuple 省内存、不可变，但只能下标 p[0] 访问、可读性差；普通 class 可读，但每个实例都带一个 __dict__，字段少时内存浪费严重。namedtuple 两头占：

from collections import namedtuple

Point = namedtuple("Point", ["x", "y", "z"])
p = Point(1, 2, 3)
p.x          # 1   —— 字段名访问，可读
p[1]         # 2   —— 也能下标访问
x, y, z = p  # 还能解包
# p.x = 10   # 报错：只读，不可变

实测（demo d5，20 万个三元组内存占用）：class + __slots__ 13.8 MB（最省，不建 __dict__）、namedtuple 15.3 MB（本质 tuple）、普通 class 33.6 MB（每实例一个 __dict__）。读大量结构化记录（CSV 行、日志条目、坐标点）时，namedtuple 比普通 class 省一半多内存又可读；需要可变或加方法时，普通 class 加 __slots__ 最省（底层机制见专家篇对象模型）。

6.2 OrderedDict：LRU 缓存的标准积木

OrderedDict 是「记住顺序」的 dict（3.7 起普通 dict 也保序，但 OrderedDict 多两个 O(1) 关键方法）：move_to_end(key) 把键挪到「最新」端，popitem(last=False) 从「最旧」端弹出。两者正好拼出 LRU（最近最少使用）缓存——容量满时淘汰最久没访问的键：

from collections import OrderedDict

class LRU:
    def __init__(self, cap):
        self.cap, self.od = cap, OrderedDict()
    def get(self, key):
        if key not in self.od:
            return None
        self.od.move_to_end(key)        # 访问过 -> 标为最新
        return self.od[key]
    def put(self, key, val):
        if key in self.od:
            self.od.move_to_end(key)
        self.od[key] = val
        if len(self.od) > self.cap:
            self.od.popitem(last=False)  # 淘汰最旧

demo 实测容量 3：put a,b,c → 访问 a（a 变最新）→ put d，最旧的 b 被淘汰，顺序变为 [c, a, d]，全程 O(1)。生产直接用 functools.lru_cache（装饰器版 LRU），底层即类似机制。

七、常见场景速查表

场景	推荐	一句话理由
生产者-消费者任务队列	deque（多线程用 queue.Queue）	两端 O(1)，线程安全
保留最近 N 条日志/滑动窗口	deque(maxlen=N)	自动溢出，免手写
词频/事件计数	Counter	C 级统计，查缺失返回 0
取 Top-K 热门	Counter.most_common(k) / heapq.nlargest	堆 O(n log k)
按键分组聚合（键→列表）	defaultdict(list)	缺键自动建空列表
有序表海量点查	bisect_left/right	O(log n)
分数段/阈值映射	bisect + 分界点数组	替代长 if-elif
任务按优先级调度	heapq 存 (priority, seq, item)	堆顶永远最高优先
合并多个有序日志/文件	heapq.merge	惰性 O(n log k)，省内存
大量只读结构化记录	namedtuple	比普通 class 省一半内存
限容量缓存	functools.lru_cache / OrderedDict	O(1) 淘汰最旧

八、常见坑

1. 拿 list 当队列：pop(0) / insert(0, x) 是 O(n)，循环里就是 O(n²)。队列一律 deque。
2. deque 当数组用：dq[i] 中间访问 O(n)。频繁随机访问用 list。
3. defaultdict 查询会「无中生有」：d["不存在"] 会真插入一个空值。只想查不插入用 d.get(k)。
4. Counter 查缺失返回 0 而非报错——方便计数，但 if counter[k] 对「键存在但计数为 0」会误判；判断键是否存在用 k in counter。
5. bisect 忘了先排序：二分的前提是序列有序，乱序表上 bisect 结果毫无意义。
6. insort 当万能插入：它仍含 O(n) 搬移；高频动态插删该用堆或别的结构。
7. Top-K 用全排序：sorted(...)[:k] 为 k 个结果排了全部数据，n 大时浪费一个数量级。
8. heapq 是最小堆：要 Top-大 要么用 nlargest，要么存负数/反转 key；heap[0] 是最小不是最大。
9. 堆元素不可比较会炸：(priority, item) 若优先级相同、item 不可比较会 TypeError；加递增序号 (priority, seq, item) 兜底（asyncio 事件循环就这么做）。
10. namedtuple 不可变：想改字段要么 _replace 造新对象，要么用 dataclass（3.7+）/普通 class。
11. 普通 class 滥用：海量实例记得 __slots__，否则每个实例的 __dict__ 吃掉几倍内存（实测 33.6MB vs 13.8MB）。

九、代码位置与动手实验

本篇全部 demo 为纯标准库（collections / bisect / heapq），Python 3.6+ 跨平台，无第三方依赖：

# Linux / macOS / WSL
cd demos/python-inter/containers
bash run_all.sh

# Windows（任一 Python 3.6+）
python demos\python-inter\containers\d1_deque\deque_queue.py
python demos\python-inter\containers\d2_mappings\mappings.py
python demos\python-inter\containers\d3_bisect\bisect_search.py
python demos\python-inter\containers\d4_heapq\heap_topk.py
python demos\python-inter\containers\d5_misc\namedtuple_lru.py

demo	验证什么	关键实测数字（Python 3.6.8）
d1_deque	deque 两端 O(1) vs list 头部 O(n)；随机访问 list 胜	FIFO N=10w：deque 快 118x；随机访问 list 快 3.4x
d2_mappings	Counter/defaultdict 统计与分组	Counter 比手写字典快 ~2x；most_common 比全排序快 2.2x
d3_bisect	二分 O(log n) vs 线性 O(n)；insort 流式保序	3w 表 1000 次查询：命中 188x、缺失 527x；insort 快 51x
d4_heapq	Top-K / 归并的堆优化	200w 取 Top-20：nlargest 比全排序快 26x
d5_misc	namedtuple 省内存；OrderedDict 拼 LRU	普通 class 33.6MB / namedtuple 15.3MB / __slots__ 13.8MB

数字随机器波动，关注数量级和方向。建议改改 N、k 亲手跑一遍，观察 O(n) 与 O(n²)、O(n log n) 与 O(n log k) 随规模拉开的差距。

总结

• 主操作决定选型：两端增删 → deque；缺键默认值 → defaultdict；计数/Top-K → Counter；有序表查找 → bisect；动态最值/优先队列/归并 → heapq；大量只读记录 → namedtuple。
• 复杂度差距是数量级的：list 当队列 O(n²)（实测慢 118x）、有序表线性查找 vs 二分（缺失键实测 527x）、全排序 vs 堆 Top-K（26x）。
• 堆的价值在「部分极值 / 动态最值 / 流式」，要全量有序仍用 sorted（Timsort 极快）；bisect 的前提是有序，适合一次排序、多次查找。
• 这些工具全是纯标准库、跨版本一致，是 内置数据结构 的专业延伸；再往底层走，专家篇会讲 dict/list 的内存布局、__slots__、哈希表扩容等内部机制。

下一篇进入函数式与迭代工具箱：itertools / operator 与生成器表达式链——如何用惰性管道写出又快又省内存的数据处理。