前言

刷题和写算法代码时，最有价值的往往不是「又发明了一个轮子」，而是知道标准库已经替你准备好了什么。Python 的标准库里藏着一批专为算法场景设计的模块：itertools负责组合、累积、分组；functools提供缓存和规约；bisect维护有序序列；heapq实现优先队列；collections.deque做双端队列。

这篇是一份算法技巧的工具箱：不算复述每个函数的完整签名，而是讲「这个模块解决哪类算法问题、典型场景长什么样」。每条给一个能直接看懂的小例子。需要某个函数的完整参数时，请以对应模块的官方文档为准。

一个前提要说明：本文只讲原理和适用场景，不声称任何「提速多少倍」；复杂度结论（比如「查找是 O(log n)」）是算法层面的结论，可以用，但具体跑多快取决于数据和环境，需要就用timeit自己测。示例以 Python 3.8 为基准，个别函数标注了更高版本要求。

一、itertools：组合与迭代的瑞士军刀

itertools里全是惰性迭代器，不一次性把结果算进内存，非常适合边算边用。

accumulate：前缀和（累积）。默认做加法，也可以传入其它二元函数。

# 适用于 Python 3.8+
from itertools import accumulate
import operator

nums = [1, 2, 3, 4]
print(list(accumulate(nums))) # [1, 3, 6, 10]，前缀和
print(list(accumulate(nums, operator.mul))) # [1, 2, 6, 24]，前缀积
print(list(accumulate(nums, initial=100))) # [100, 101, 103, 106, 110]

initial关键字参数需要Python 3.8+，给了它输出会比输入多一个元素。

chain：把多个可迭代对象串成一个。

# 适用于 Python 3.8+
from itertools import chain
print(list(chain([1, 2], [3], [4, 5]))) # [1, 2, 3, 4, 5]

groupby：把相邻的相同键元素分组。注意它只合并「挨在一起」的，用之前通常要先排序。

# 适用于 Python 3.8+
from itertools import groupby

data = [("a", 1), ("a", 2), ("b", 3)]
for key, group in groupby(data, key=lambda x: x[0]):
print(key, list(group))
# a [('a', 1), ('a', 2)]
# b [('b', 3)]

combinations/permutations/product：组合、排列、笛卡尔积。

# 适用于 Python 3.8+
from itertools import combinations, permutations, product

print(list(combinations([1, 2, 3], 2))) # [(1,2), (1,3), (2,3)]
print(list(permutations([1, 2, 3], 2))) # [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]
print(list(product([0, 1], repeat=2))) # [(0,0), (0,1), (1,0), (1,1)]

二、functools：缓存与规约

lru_cache/cache：把函数结果按参数缓存，递归、动态规划里几乎是标配。

# 适用于 Python 3.8+
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(20)) # 6765

lru_cache(maxsize=128, typed=False)是带容量上限的版本，超出就淘汰最久未用的；functools.cache（3.9+）是不设上限的简化版，等价于lru_cache(maxsize=None)。被缓存的参数必须可哈希，所以参数是列表时不能直接用。

reduce：把一个序列「折叠」成单个值。

# 适用于 Python 3.8+
from functools import reduce

print(reduce(lambda a, b: a + b, [1, 2, 3, 4])) # 10
print(reduce(lambda a, b: a * b, [1, 2, 3, 4], 1)) # 24，带初始值

注意reduce的签名是reduce(function, iterable, /[, initial])，第三个参数是初始值。

三、bisect：在有序序列上二分

bisect用于维护已排序的列表：bisect_left/bisect_right返回插入点，insort直接插入。核心要点是——返回的是插入位置，不是「找没找到」。

# 适用于 Python 3.8+
import bisect

a = [10, 20, 20, 30]
print(bisect.bisect_left(a, 20)) # 1，插在已有 20 的左边
print(bisect.bisect_right(a, 20)) # 3，插在已有 20 的右边
bisect.insort(a, 25) # 保持有序地插入
print(a) # [10, 20, 20, 25, 30]

要在有序序列里做等值查找，得用bisect_left拿到位置后再自己比一次（详见专门的 bisect 篇）。查找是 O(log n)，但insort因插入本身要挪动元素，整体是 O(n)。

四、heapq：优先队列

heapq把普通列表当成最小堆用，堆顶永远是heap[0]（最小值）。

# 适用于 Python 3.8+
import heapq

h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
print(h[0]) # 1，堆顶
print(heapq.heappop(h)) # 1，弹出最小值
print(heapq.nlargest(2, [3, 1, 4, 1, 5, 9, 2])) # [9, 5]

取最大的几个用nlargest，最小的几个用nsmallest，直接heapify能把现成列表原地变成堆。需要在优先队列里带任务时，常用(优先级, 序号, 任务)三元组避免比较任务本身（详见专门的 heapq 篇）。

五、collections.deque：双端队列

deque（读作 deck，double-ended queue）支持 O(1) 地从左右两端进出，还能设最大长度自动挤掉旧元素。

# 适用于 Python 3.8+
from collections import deque

dq = deque([1, 2, 3])
dq.appendleft(0) # 左端加
dq.append(4) # 右端加
print(dq) # deque([0, 1, 2, 3, 4])
print(dq.popleft()) # 0
print(dq.pop()) # 4

它比用list.pop(0)强的地方在于：list从头部弹出要整体挪动，是 O(n)；deque两端都是 O(1)。带maxlen的deque很适合做「只保留最近 N 条」的滑动窗口。

# 适用于 Python 3.8+
from collections import deque
recent = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
recent.append(x) # 满了自动从左边挤掉
print(list(recent)) # [3, 4, 5]

六、按问题选工具

常见坑点

坑一：groupby忘了先排序。

# 适用于 Python 3.8+
# ❌ 只合并相邻的相同键，乱序数据分不对
from itertools import groupby
data = ["a", "b", "a"]
print([(k, list(g)) for k, g in groupby(data)]) # [('a',['a']), ('b',['b']), ('a',['a'])]
# ✅ 先按同一个 key 排好序
data.sort()
print([(k, list(g)) for k, g in groupby(data)]) # [('a',['a','a']), ('b',['b'])]

坑二：给lru_cache的函数传了不可哈希的参数。

# 适用于 Python 3.8+
# ❌ 列表不能做缓存键
from functools import lru_cache
@lru_cache(maxsize=None)
def f(xs):
return sum(xs)
f([1, 2]) # TypeError: unhashable type: 'list'
# ✅ 传元组
f((1, 2)) # 3

坑三：把bisect的返回值当成「是否找到」。

# 适用于 Python 3.8+
# ❌ 返回的是插入点，不是下标命中
import bisect
a = [10, 20, 30]
print(bisect.bisect_left(a, 25)) # 2，位置在 20 和 30 之间
# ✅ 要判等值，拿到位置后再比
i = bisect.bisect_left(a, 25)
found = i < len(a) and a[i] == 25 # False

坑四：用list当队列从头部弹。

# 适用于 Python 3.8+
# ❌ list.pop(0) 是 O(n)
q = [1, 2, 3]
q.pop(0)
# ✅ 用 deque
from collections import deque
q = deque([1, 2, 3])
q.popleft()

坑五：以为heapq能直接取最大值。

# 适用于 Python 3.8+
# ❌ heapq 是最小堆，h[0] 是最小值
import heapq
h = [3, 1, 2]
heapq.heapify(h)
print(h[0]) # 1，不是 3
# ✅ 要最大堆就把值取负存
h = []
for x in [3, 1, 2]:
heapq.heappush(h, -x)
print(-h[0]) # 3

坑六：在循环里反复append到一个不断增长的列表当缓存，却忘了去重。

# 适用于 Python 3.8+
# ❌ 缓存只增不减，重复调用也重算
cache = []
def f(x):
if x not in cache: # 线性扫描，且没存结果
cache.append(x)
# ✅ 用字典或 lru_cache 做真正的记忆化
from functools import lru_cache
@lru_cache(maxsize=None)
def f(x):
return x * x

坑七：把itertools的迭代器当列表用两次。

# 适用于 Python 3.8+
# ❌ 迭代器只能遍历一次
from itertools import combinations
c = combinations([1, 2, 3], 2)
print(len(list(c))) # 3
print(len(list(c))) # 0，第二次已经空了
# ✅ 需要多次使用就先转成列表
c = list(combinations([1, 2, 3], 2))

总结

算法代码写得多的人，脑子里会有一张「什么需求找哪个模块」的对照表：累积想accumulate，去重递归想lru_cache，有序查找想bisect，优先队列想heapq，两端进出想deque。先熟悉这张表，再深入具体函数的细节，是提升效率最实在的一条路。