我统计过自己这几年写下的 Python 代码,真正跟"刷题算法"重合的部分不到三成,但恰恰是这三成——排序、二分、堆、并查集、BFS、滑动窗口——在关键时刻救过场:一次是把一个跑了四十多分钟的对账任务压到两分半,一次是把一个内存爆掉的图遍历改成了可控的迭代版本。所以当有人问我"Python 经典算法有哪些、Python 算法大全该怎么学"的时候,我一般不会甩一份清单过去,而是先反问一句:你是要应付面试,还是要让线上那段代码别再把 CPU 吃满。这两个答案指向的算法集合重叠度很高,但优先级排序完全不一样。
这篇东西就是把我自己踩过的路径整理出来:Python 里那些真正称得上"经典"的算法分别解决什么问题、官方标准库已经替你实现了哪些、哪些必须自己手写、手写时最容易在哪一行翻车。不管你是刚接触算法的新手,还是写过几年代码但一直靠sorted和in混日子的老手,下面这些内容应该都能抠出点能直接用的东西。
1. 先把"Python 算法大全"这个词拆开看
1.1 面试算法和工程算法的分层差异
网上流传的"Python 经典算法大全"清单,绝大多数是按刷题平台的知识树排的:数组、链表、哈希、双指针、二分、递归、回溯、贪心、动态规划、图论、位运算。这套体系没问题,它覆盖了计算机科学里最核心的思维训练。但如果你直接照着它去写业务代码,会发现一个尴尬的事实:里面一大半算法,标准库或者第三方库已经做到你手写永远追不上的程度。
我习惯把算法分成三层来看,这个分层决定了你该花多少时间在"手写"上:
| 层级 | 典型内容 | 处理策略 |
|---|---|---|
| 标准库已实现层 | 排序、二分查找、堆、双端队列、有序字典、字符串查找 | 优先用库,但要懂边界和复杂度 |
| 必须手写层 | 并查集、拓扑排序、滑动窗口、回溯剪枝、状态压缩 DP | 必须能手写,且要写得能过性能关 |
| 框架/库替代层 | 最短路、最小生成树、最大流、矩阵运算 | 小规模手写练思维,生产环境上专用库 |
这张表的意义在于省时间。新手最容易犯的错是把"排序算法全家桶"背得滚瓜烂熟,却在需要 Top-K 的时候写了个全量排序;反过来,老手容易过度依赖库,遇到需要自定义合并规则的场景就抓瞎。
1.2 Python 这门语言给算法带来的特殊约束
Python 写算法和其他语言有个根本差异:解释执行带来的常数开销极大。同一份快速排序,C 写出来可能比 Python 快几十倍。这意味着在 Python 里,算法复杂度的"常数项"往往比复杂度本身更能决定成败。
举个具体的:一个 O(n log n) 的归并排序,如果每一层都做大量的列表切片和拼接,实际耗时可能比一个常数优化良好的 O(n²) 插入排序还慢——在 n 小于几百的时候这几乎是必然的。我实测过,对 200 个随机整数排序,纯 Python 手写插入排序和sorted()的差距在 10 倍以内,但手写归并的差距能到 30 倍以上,因为递归调用加临时列表分配的成本太高了。
所以学 Python 算法有个隐含前提:你要知道哪些操作在 Python 里是"贵"的。列表中间插入删除贵、递归调用贵、属性访问贵、全局变量访问贵;而内置函数、列表推导式、切片、sum、min、max、any、all这些由 C 层实现的操作用起来便宜得多。后面每一节我都会点出对应的性能雷区。
2. 排序与查找:从 sorted 的边界往外扩一圈
2.1 Timsort 到底帮你做了什么,什么时候必须绕开它
Python 的sorted()和list.sort()用的是 Timsort,这是个归并排序和插入排序的混合体。它的核心设计是识别输入中已经有序的片段(术语叫 run),对短 run 用二分插入排序扩展,再两两归并。默认最小 run 长度是 32 或 64(跟实现版本有关)。带来的直接结果是:最好情况 O(n),最坏和平均都是 O(n log n),并且稳定。
稳定这个性质很多人不当回事,实际很关键。比如你要按分数降序排学生名单,同分的保持原顺序,直接sorted(students, key=lambda s: -s.score)就完事,不用额外加索引。如果你手写快排,这个稳定性就没了,得用"排序键 + 原索引"的元组来补救,白白多一层开销。
那什么时候必须绕开sorted?
第一种是需要"部分排序"。你要从一百万个元素里取最大的十个,全量排序是 O(n log n),而维护一个大小为 10 的最小堆只要 O(n log k),差距在两个数量级以上。第二种是数据流式到达,你没法一次性拿到全部数据。第三种是排序键的计算成本极高,而你想复用中间结果——这时候可以自己控制"装饰-排序-去装饰"的节奏。
提示:
sorted对 key 函数的调用次数是严格的 n 次,不是 n log n 次。它内部会先把每个元素映射成 (key, index, value) 的元组再排。所以哪怕 key 里做了复杂计算,也不会因为比较次数多而被反复调用。这一点让很多人误以为 key 会被调用很多次,从而去手动缓存,其实是多余的。
2.2 手写快排时那两个必踩的坑
就算平时用sorted,快排还是得会写,面试绕不开。但 Python 版快排有两个坑,几乎所有第一次写的人都会撞上。
第一个坑是递归深度和切片开销。教科书式写法left = [x for x in arr if x < pivot]看着优雅,实际每次递归都新建两个列表,内存分配和垃圾回收的成本会吃掉算法优势。对 10 万个随机数,这种写法比sorted慢 5 倍以上。改良方式是原地分区(Lomuto 或 Hoare 分区),只交换不新建。
第二个坑是重复元素导致的退化。如果数组里大量元素相等,标准的两路分区会把它们全部分到一边,递归树退化成链,复杂度掉到 O(n²)。解决办法是三路快排,把数组分成"小于、等于、大于"三段,等于段不再参与递归。代码骨架如下:
def quick_sort_3way(arr, lo, hi): if lo >= hi: return pivot = arr[lo] lt, gt, i = lo, hi, lo + 1 while i <= gt: if arr[i] < pivot: arr[lt], arr[i] = arr[i], arr[lt] lt += 1 i += 1 elif arr[i] > pivot: arr[gt], arr[i] = arr[i], arr[gt] gt -= 1 else: i += 1 quick_sort_3way(arr, lo, lt - 1) quick_sort_3way(arr, gt + 1, hi)注意gt那一支在交换后i不前进,因为换过来的元素还没被检查过。这个细节漏掉就是死循环或者结果错乱,我第一次写的时候在这一行上卡了半小时。
2.3 二分的四种边界变体和 bisect 的正确用法
二分查找看着简单,实际是算法题里翻车率最高的。核心原因是"找目标值"只是最基础的一种,真正有用的是四种边界变体:找第一个等于目标的位置、找最后一个等于目标的位置、找第一个大于等于目标的位置、找第一个大于目标的位置。
Python 的bisect模块直接给了后两种:bisect_left返回第一个>= x的插入点,bisect_right返回第一个> x的插入点。前两种可以由此推出:
- 第一个等于 x 的位置:
i = bisect_left(a, x),检查i < len(a) and a[i] == x - 最后一个等于 x 的位置:
j = bisect_right(a, x) - 1,检查j >= 0 and a[j] == x - 元素 x 的出现次数:
bisect_right(a, x) - bisect_left(a, x)
手写二分最容易出的错是循环条件和 mid 取法的配套。while left < right配mid = (left + right) // 2,更新时必须是right = mid和left = mid + 1;如果写成left = mid就会死循环。我的经验是:只要区间定义为左闭右开,就统一用left < right加mid = (left + right) // 2,右边界更新写right = mid,这套组合几乎不会错。
还有一种进阶用法叫"二分答案":当问题的解具有单调性(判定某个值可行,则更大或更小的值也可行)时,可以对答案域做二分。典型场景是最小化最大值、最大化最小值这类问题。这种题的关键不是二分本身,而是把"判定函数"写对——判定函数写错,二分再标准也是错的。
3. 线性结构:deque、heapq、并查集、LRU 的落地写法
3.1 list 当队列用是个高频事故
新手写 BFS,十有八九写成queue.pop(0)。这行代码是 O(n) 的,因为 Python 的 list 是连续内存的动态数组,删掉头部元素要把后面所有元素整体前移。在 10 万节点的图上,这个操作能把 BFS 从秒级拖到分钟级。
正确做法是collections.deque,两端插入删除都是 O(1)。它的代价是不支持切片、随机访问是 O(n)、中间插入也慢,但对于队列和栈的用途完全够。另一个常见误区是把 deque 当有序容器用,以为它有sort方法——没有,需要排序就先转成 list。
栈的话直接用 list 就行,append和pop()都是 O(1),没必要上 deque。我见过有人为了"统一风格"全用 deque,结果代码里到处是popleft和pop混用,可读性反而下降。
3.2 heapq 的三个隐藏细节
heapq是 Python 里最被低估的标准库之一。它实现的是最小堆,所有操作基于 list 原地进行,heappush和heappop都是 O(log n),heapify建堆是 O(n)。三个细节必须知道:
第一,最大值要用负数。Python 没有内置最大堆,标准做法是存-x。如果你的元素是元组,就在第一位放负的优先级:heapq.heappush(h, (-priority, item))。
第二,tuple 比较会继续比较后续元素。这既是特性也是陷阱。存(priority, item)时,如果两个元素优先级相同,Python 会去比较item。如果item是自定义对象且没实现__lt__,直接抛TypeError。解决办法是加一个自增计数器作为第二元素:(priority, count, item),保证比较永远在计数器处终止。
import heapq, itertools counter = itertools.count() heap = [] heapq.heappush(heap, (5, next(counter), {"name": "task_a"})) heapq.heappush(heap, (5, next(counter), {"name": "task_b"})) # 两个优先级相同也不会去比较 dict第三,建堆别用循环 push。从已有列表建堆用heapq.heapify(lst),O(n);循环heappush是 O(n log n)。差一个 log 因子,在大数据量下很明显。
3.3 并查集:迭代实现比递归实现靠谱
并查集(Union-Find)解决的是"元素分组 + 快速判断是否同组"的问题,典型应用是连通性判断、Kruskal 最小生成树、朋友圈合并。核心就两个操作:find找根,union合并。两个优化:路径压缩、按秩(或按大小)合并。两个都上,均摊复杂度接近 O(α(n)),α 是反阿克曼函数,实际可以当成常数。
Python 实现建议用迭代版 find,别用递归。递归版在链很长的时候会撞上默认 1000 层的递归限制,虽然路径压缩会把链压平,但第一次 find 之前链可能已经很长了。
class DSU: def __init__(self, n): self.parent = list(range(n)) self.size = [1] * n self.count = n # 连通分量数 def find(self, x): root = x while self.parent[root] != root: root = self.parent[root] while self.parent[x] != root: # 路径压缩,迭代版 self.parent[x], x = root, self.parent[x] return root def union(self, a, b): ra, rb = self.find(a), self.find(b) if ra == rb: return False if self.size[ra] < self.size[rb]: ra, rb = rb, ra self.parent[rb] = ra self.size[ra] += self.size[rb] self.count -= 1 return Trueunion返回布尔值表示是否真的合并了,这个返回值在 Kruskal 里非常方便:合并成功就说明这条边要加入生成树,失败说明成环要跳过。
3.4 手写 LRU:OrderedDict 和双向链表两条路
LRU(最近最少使用)缓存是面试高频题,Python 里有两条实现路径。
第一条是collections.OrderedDict,三行搞定:
from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cap = capacity self.data = OrderedDict() def get(self, key): if key not in self.data: return -1 self.data.move_to_end(key) return self.data[key] def put(self, key, value): if key in self.data: self.data.move_to_end(key) self.data[key] = value if len(self.data) > self.cap: self.data.popitem(last=False)第二条是哈希表 + 双向链表,面试时如果被要求"不许用 OrderedDict"就得靠这个。核心是虚拟头尾节点,避免边界判断。手写版本的价值在于理解"为什么是 O(1)"——哈希定位节点,链表调整顺序,两个操作都是常数时间。
工程上如果真要做缓存,直接用functools.lru_cache或者更完整的第三方缓存库,别自己造。自己写的版本通常缺并发保护、缺过期策略、缺内存回收。我见过有人手写 LRU 结果在多线程下把链表指针改乱了,排查了很久。
4. 递归、回溯与 DP:从"能跑通"到"不超时"的距离
4.1 递归深度这道坎比想象中低
Python 默认递归限制是 1000 层,sys.setrecursionlimit()可以调高,但调高不等于安全。因为每层递归在 C 栈上也有开销,调太高(比如 10 万)可能导致解释器直接崩溃而不是抛RecursionError,这个后果比报错严重得多。
我的经验是:递归深度超过 5000 就该考虑改迭代了。改法有三种:显式维护栈(最适合 DFS)、BFS 替代(如果只关心可达性)、状态转移改循环(DP 场景)。显式栈的写法是把递归函数里的参数打包成元组压栈,本质上是手动模拟调用栈。
尾递归在 Python 里没有任何优化,写return f(x-1)照样占一层栈。这一点和其他语言差别很大,别指望靠它省空间。
另外有个高频坑是可变默认参数:
def dfs(node, path=[]): # 错误 path.append(node) ... def dfs(node, path=None): # 正确 path = [] if path is None else path path.append(node)默认参数在函数定义时求值一次,所有调用共享同一个 list,第二个测试用例就直接全错了。这个坑排错时特别隐蔽,因为单次运行看起来完全正常。
4.2 回溯剪枝放在哪一行决定了快十倍还是慢十倍
回溯的通用模板是"选择 - 递归 - 撤销选择",难点不在模板,在剪枝。剪枝位置有三种,效果差异巨大:
第一种是排序后跳过重复,处理"组合中有重复元素但不能重复选"的问题:if i > start and nums[i] == nums[i-1]: continue。这里i > start不能少,否则第一个元素就被跳过了。
第二种是提前终止,当当前和已经超过目标、或者剩余元素全加都不够时直接 return。前提是数组已排序,所以排序往往不只是为了去重,也是为了剪枝。
第三种是可行性预判,在进入递归前检查剩余资源,比如背包问题里检查容量是否还够。这种剪枝写起来最麻烦,但收益最大。
我做过一个对比:解数独的朴素回溯和加了"候选数最少优先"的版本,在中等难度题上差距接近 20 倍。剪枝的收益不是线性的,它砍掉的是整棵子树。
状态恢复也要注意。用list.append和list.pop配对是最安全的,别用path = path + [x]这种写法,虽然也能得到正确结果,但每层都复制一次列表,空间和时间都翻倍。
4.3 DP 的状态设计比递推式难十倍
动态规划的关键从来不是写递推式,是定义状态。状态定义对了,递推式自然出来;定义错了,怎么推都漏情况。
我一般按三步走:先写出暴力递归版本(保证正确),再看递归函数有哪些参数在变化(这些就是状态维度),最后决定用自顶向下的lru_cache还是自底向上的循环。
functools.lru_cache是个好东西,几行代码就能把指数级递归变成多项式级。但它有三个限制:参数必须可哈希(list 不行,得转 tuple);缓存没有自动清理(长生命周期函数会吃掉内存);递归深度限制依然存在。所以在生产代码里,我倾向手写 DP 表,用数组存状态,可控性强得多。
二维 DP 转一维是个必备技能,尤其背包类问题。0-1 背包的一维写法必须逆序遍历容量,完全背包必须正序遍历,这个方向的差异来源于"同一物品能否重复使用"。我见过太多人把方向写反,结果要么答案偏小要么偏大,还得靠打印中间表才能发现。记忆口诀是:逆序保旧值,正序用新值。
5. 图与树:BFS、拓扑排序、最短路的三套写法
5.1 邻接表的三种存法和选择依据
建图方式直接影响后续代码的可读性和性能。三种常见存法:
| 存法 | 结构 | 适用场景 | 注意点 |
|---|---|---|---|
| 列表套列表 | g = [[] for _ in range(n)] | 节点编号连续、稠密度中等 | 节点数大但边少时浪费内存 |
| 字典套列表 | g = defaultdict(list) | 节点编号离散、字符串节点 | 遍历时要.items() |
| 边列表 | edges = [(u, v, w)] | Kruskal、Bellman-Ford | 需要邻接表时再转换 |
选哪种?我的判断标准是节点编号是否在 0 到 n-1 范围内。是就用列表套列表,访问速度最快;不是就用defaultdict(list),省去编号映射的麻烦。
邻接矩阵只在稠密图上用,比如 Floyd 求全源最短路。n 超过 2000 时矩阵内存就到 GB 级了,得换思路。
5.2 BFS 的 visited 标记时机是最大的坑
BFS 里 visited 的标记时机,直接决定代码是线性复杂度还是指数复杂度。正确做法是入队时就标记,不是出队时。
from collections import deque def bfs(graph, start, target): visited = {start} q = deque([(start, 0)]) while q: node, dist = q.popleft() if node == target: return dist for nxt in graph[node]: if nxt not in visited: # 入队前判断 visited.add(nxt) # 入队前标记 q.append((nxt, dist + 1)) return -1如果写成出队时才标记,同一个节点会被多个前驱重复入队,队列规模可能膨胀到边的数量级。在稠密图上这就是灾难。这个问题我调试过两次,每次都是通过打印队列长度才发现的——队列长度异常增长,八成就是标记时机错了。
5.3 Dijkstra 的堆优化和两个必备补丁
Dijkstra 的朴素版是 O(n²),堆优化版是 O((n+m) log n)。Python 实现堆优化版有两个补丁不能省:
第一个补丁是跳过过期条目。堆里可能存着同一个节点的多个距离值,弹出时检查if d > dist[u]: continue,否则会用旧距离去松弛邻居,算出来的结果虽然是"更长的路径",但不影响正确性(因为最终会被更小的覆盖),只是浪费计算。
第二个补丁是提前终止。如果只关心起点到某个终点的最短距离,在终点首次弹出时就可以返回,不需要跑完全图。这在图很大而终点很近的时候收益巨大。
Dijkstra 有个硬约束:不能处理负权边。有负权边必须换 Bellman-Ford 或 SPFA。判断依据很简单:如果有边的权重为负,先用 Bellman-Ford 检测负环,没负环再用 SPFA 求最短路。
5.4 拓扑排序:Kahn 算法和 DFS 后序的取舍
两种写法都能给出拓扑序,但用途不同。
Kahn 算法基于入度:把所有入度为 0 的节点入队,弹出时把它指向的节点入度减一,减到 0 就入队。它的额外好处是能直接判断有没有环——如果最终输出的节点数少于总数,说明剩下的节点互相依赖成环了。
DFS 后序法是遍历完一个节点的所有后继后把它加入结果,最后整体反转。代码更短,但环检测要做额外的三色标记(未访问/访问中/已完成),遇到"访问中"的节点就说明有环。
我一般优先用 Kahn,理由是它天然给出"同时可执行的批次"——把每轮队列里的元素当成一批,就能得到分层拓扑序。这个性质在任务调度场景里直接能用上,比如构建依赖图里哪些模块可以并行编译。
6. 字符串与窗口类算法:Python 语境下的特殊打法
6.1 KMP 的 next 数组到底在算什么
KMP 是字符串匹配的经典算法,核心是next数组(也叫前缀函数、失配函数)。它记录的是"模式串的每个前缀,最长的既是前缀又是后缀的子串长度"。听起来绕,作用是:匹配失败时,模式串不用从头开始,直接根据 next 数组跳到一个已知的前缀位置继续。
Python 里日常做子串查找,直接用in或者str.find就行,底层是优化过的算法,手写 KMP 在绝大多数场景都更慢。KMP 的价值在于算法思维,以及在"需要求字符串周期、判断由重复子串构成"这类问题上——比如判断s是否能由某个子串重复多次构成,解法就是看n - next[n-1]是否能整除n。
6.2 滑动窗口的模板要配"何时收缩"的判断
滑动窗口解决的是"连续子数组/子串满足某条件"的问题,模板固定:
def sliding_window(s): left = 0 counter = {} best = 0 for right in range(len(s)): counter[s[right]] = counter.get(s[right], 0) + 1 while 条件不满足: counter[s[left]] -= 1 if counter[s[left]] == 0: del counter[s[left]] left += 1 best = max(best, right - left + 1) return best关键在两个地方:while里的收缩条件怎么写,以及结果在收缩前更新还是收缩后更新。求"最长"是在收缩后更新,求"最小长度"是在收缩过程中更新。这个差别我一开始老是搞混,后来统一记成"最长看窗口外面,最短看窗口里面"。
还有一个非模板的东西:字符串里涉及字符计数时,Counter比手写 dict 方便,但每次比较Counter相等是 O(k),k 是字符种类数。字符集固定(比如只有小写字母)时,用一个长度为 26 的 list 计数会快不少。
6.3 字符串拼接的性能雷区
Python 的字符串不可变,s += c在循环里理论上每次都新建对象,是 O(n²)。虽然 CPython 对+=有引用计数优化,在s只被引用一次时能原地扩展,但这个优化属于实现细节,不可依赖。稳妥做法是''.join(parts)或者用io.StringIO。
另一个常被忽视的点:字符串的s[i]返回的是长度为 1 的新字符串,不是字符类型。所以需要原地修改字符的场景(比如双指针交换),必须先lst = list(s)转成列表,改完再''.join(lst)。直接对字符串做下标赋值会抛TypeError。
涉及正则的场景,如果同一模式要匹配多次,先re.compile缓存,别在循环里反复编译。这个差异在百万级匹配下能到 30% 以上。
7. 从能跑到跑得快:算法代码的性能验证与工程化
7.1 用数据说话:timeit 和 cProfile 的分工
写完算法不看性能,等于没写完。我习惯用两个工具:timeit测单段代码的重复执行耗时,cProfile定位整个程序的耗时分布。
timeit的正确用法是给stmt和setup,让它内部做多次重复取最小值。手动写time.time()前后相减是最粗糙的做法,受系统负载和缓存影响极大,测出来的数字基本不能比。
cProfile输出的是函数级调用统计,按cumtime(累计时间)排序找热点。我发现过好几次"以为慢在算法上,实际慢在日志打印和数据转换"的情况,没有 profile 根本看不出来。一个真实例子:一个图遍历程序,算法部分只占 15% 时间,剩下 85% 花在 JSON 序列化上,优化算法毫无意义。
7.2 那些让算法白写的语言级细节
有几个 Python 层面的细节,能让同一份算法代码差出几倍性能:
- 把常用的全局函数绑定到局部变量。循环里反复访问
len、append、heapq.heappush这类全局名字,每次都要做字典查找。在函数开头写成_append = lst.append、_heappush = heapq.heappush,在热循环里能省下可观的开销。 - 用列表推导代替 for 加 append。列表推导在 C 层执行,比显式循环快 30% 到 50%。
- 用
sum、any、all代替手写累加。内置函数走 C 循环,快得多。 - 避免在循环里做重复计算。
for i in range(len(arr))里的len(arr)每轮都要求值,改成n = len(arr)再for i in range(n)。
这些优化单个看起来都是小打小闹,叠加起来在百万级数据上能有两三倍的差距。当然前提是算法复杂度已经对了,用这些技巧去优化一个 O(n²) 的算法是本末倒置。
7.3 把算法封装成可测试的模块
面试写完就交,生产代码不行。我的习惯是每个算法实现配一组边界用例:空输入、单元素、全部相同、已排序、逆序、含负数或特殊值。这些用例不是为了凑覆盖率,是因为它们对应着真实会踩的坑。
举个我自己的教训:写过一版二分查找,逻辑完全正确,但没处理空列表,bisect_left([], x)返回 0,我的代码直接arr[0]抛了IndexError。这个 bug 在上线两周后才因为某个数据源为空而暴露。
封装时还有一个建议:把算法的输入校验和核心逻辑分开。校验层负责类型检查、边界处理、异常抛出,核心逻辑保持纯粹,只处理"已经合法"的输入。这样核心逻辑好测、好复用,也不会被各种防御性代码搞成一锅粥。
还有一点,如果算法涉及浮点数比较,一律用math.isclose,别写==。round(2.675, 2)返回2.67不是2.68,因为 2.675 在二进制里存不下精确值。这种问题在几何计算和数值算法里出现频率极高。
8. 几个让我改了代码习惯的具体现场
说几个真实的场景,都是我在项目里撞上的,比抽象讲道理有用。
第一个是 BFS 的内存爆炸。做一个层级依赖分析,图有几十万节点,跑着跑着内存涨到几个 G。排查下来是 visited 用 list 存然后in判断,查询是 O(n),总复杂度变成 O(n²),加上重复入队导致的队列膨胀,内存直接失控。改成 set 加正确的入队前标记,内存降到几百兆,时间从分钟级到秒级。
第二个是排序键不一致导致的崩溃。线上环境sorted抛TypeError: '<' not supported between instances of 'NoneType' and 'int',原因是某条数据里排序字段是 null。修复方案是在 key 函数里做默认值处理,并且明确业务上 null 应该排在最前还是最后。这类问题提醒我:算法代码里的"理想输入"假设,在真实数据面前经常不成立。
第三个是 DP 缓存没清理。一个用lru_cache写的路径计算方法,跑批处理任务时内存持续增长,跑了几个小时之后被系统杀掉。原因是缓存 key 里带了整个请求上下文,每个请求都产生新条目且永不过期。改成手动管理缓存表,按批次清理,问题解决。lru_cache适合函数式、参数空间小的场景,不适合参数空间巨大且持续变化的场景。
最后再分享一个我自己的判断标准:如果一个算法的实现超过 60 行还没写完,八成是状态设计或者数据结构选错了,回头重想比硬写下去快。我见过太多人(包括我自己)在错误的方向上硬啃,最后写出来的代码又长又慢,还不容易发现哪里错了。真正干净的实现,往往短得让你怀疑是不是漏了什么。