按增长率读代码
正确性代码审查 vs 复杂度代码审查
正确性审查找出逻辑错误:条件错误、数组越界、空指针检查遗漏。复杂度感知审查找出不同类型的缺陷:在N = 100时工作正确,但在N = 100,000时灾难性增长的代码。
本课程连接到《unhamming课程》中的深入调查: 缺失的章节: 算法复杂度 从生产缺陷的背景讨论大O记法, & MOAD-0001: 沉积式缺陷 绘制该模式在60多个软件生态系统中的分布。
两个审查启发式方法
嵌套循环使复杂度相乘。 两个嵌套循环都迭代N项产生O(N²)。三个产生O(N³)。审查时:首先数循环嵌套深度。
热循环内的顺序容器。 任何.contains()、.includes()、.find()或in list检查在循环内都花费O(N)。在N次迭代中:总共O(N²)。这个模式出现在GHC Haskell编译器、Python pip、Apache Maven、Rust Cargo、TypeScript、Godot中——同样的错误,不同的代码库。
审查: find_duplicates
对以下Python函数进行复杂度感知审查:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: 沉积式缺陷
同样的缺陷,六十个生态系统
模式if x not in list: list.append(x)在循环内出现——曾出现——在几十个软件生态系统的生产代码中:
- GHC (Haskell编译器): 依赖解析器, O(N²)在N = 50,000个包, 17分钟构建
- Python pip: 依赖冲突解决
- Apache Maven: 类路径去重
- Rust Cargo: 特性统一
- TypeScript编译器: 模块解决
- Godot / Redot游戏引擎: 节点图遍历
这些团队都没有出错。他们在小N时写了正确的代码。N增长了。代码石化了。这个模式有个名字: MOAD-0001, 沉积式缺陷。 沉积物:在薄层时正确、无害。随着时间,层堆积并硬化。
修复
在每种情况下:用哈希容器替换顺序容器。一行。在正确输入处零行为改变。在实际N处100–1,000×加速。
修复有效是因为两个操作需要保持快速:
1. 成员检查: 这个元素是否之前被看过?
2. 有序输出: 按元素出现的顺序返回(有时需要,有时不需要)。
集合在O(1)中处理(1)。如果(2)也重要,保留一个单独的列表以保持有序输出,和一个集合以进行成员检查。两个数据结构,各司其职。
回应审查者
一个拉取请求在项目的图遍历函数中修复MOAD-0001。审查者评论:
> "集合不保留插入顺序——这改变了行为。"
面试分析模式
期望的格式
算法复杂度分析出现在软件工程面试中。一个强的答案遵循四部分模式:
1. 说明当前复杂度 — 时间O(?),空间O(?)。
2. 解释为什么 — 确定负责任的具体构造(嵌套循环、循环内的线性扫描、递归分支)。
3. 提议优化 — 命名改变和它引入的数据结构或算法。
4. 说明新复杂度 — 修复后,时间和空间复杂度是多少?
例:
代码:[检查列表中成员资格的函数在循环内]
当前:O(N²) — `item in seen_list`是每次检查O(N) × N次迭代
优化:用seen_set(哈希集)替换seen_list
之后:O(N) — 集合成员检查是O(1)这项技能转移到面试之外:复杂度感知代码审查、架构设计、性能调试、安全审计。任何处理可变大小输入的系统都从中受益。
本课程向前连接到《unhamming课程》,它在60多个开源项目中的生产缺陷调查中应用完全相同的模式。
面试: 分析has_common_element
对这个函数应用四部分面试格式:
def has_common_element(list_a, list_b):
for item in list_a:
for other in list_b:
if item == other:
return True
return False