阅读代码以识别增长率
代码审查的正确性 vs 复杂性意识的代码审查
正确性的代码审查捕获逻辑错误：错误的条件、off-by-one索引、缺少null检查。复杂性意识的代码审查捕获一个不同的缺陷类别：代码在N = 100时正确，但在N = 100,000时增长灾难性。
这一课将链接到未汉明课程的更深入的调查：[缺失章节：算法复杂性](/en/un/unhamming_algorithmic_complexity)在生产缺陷的背景下介绍了大O符号，[MOAD-0001：沉积缺陷](/en/un/unhamming_moad_sedimentary)将模式映射到60多个软件生态系统。
两种审查启发式法
嵌套循环会增加复杂性。 两个嵌套循环遍历N个项目产生O(N²)。三个产生O(N³)。在审查时：首先计算循环嵌套深度。
热循环中的顺序容器。 在循环中任何.contains(), .includes(), .find()或in list检查每次检查成本为O(N)。总计：O(N²)。这个模式出现在生产代码中，跨数十个生态系统——Haskell GHC编译器、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-1000 倍。
解决方案的原因是两个操作需要保持快速:
1. 成员资格检查：这个元素是否已经被看到过？
2. 有序输出：返回元素的出现顺序（有时需要，有时不需要）。
集合处理 (1) 需要 O(1)。如果 (2) 也是重要的，保留一个有序输出的单独列表，并为成员资格检查保留一个集合。两个数据结构，每个都在做一个工作。
回应评论
一个拉取请求在项目的图遍历函数中修复了 MOAD-0001。一个评论者评论:
> "Sets 不保留插入顺序 — 这会改变行为。"
面试分析模式
期望格式
算法复杂度分析在软件工程面试中出现。一个强大的回答遵循四个模式:
1. 说明当前复杂度 — 时间复杂度O(?)、空间复杂度O(?)
2. 解释原因 — 标识具体的构造(嵌套循环、循环内的线性扫描、递归分支)
3. 提出优化方案 — 命名更改及引入的数据结构或算法
4. 说明新复杂度 — 在修复后,时间和空间复杂度分别为多少?
示例:
代码:[在循环中检查列表中的成员资格的函数]
当前:O(N²) — `item in seen_list`的检查时间为O(N) × N次迭代
优化:将seen_list替换为seen_set(哈希集)
修复后: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