MOAD-0001 的五种形式

MOAD-0001 在 60 多个软件生态系统中以五种已记录的形式出现。其结构为：在对同一或相关集合进行循环时，使用顺序容器执行成员测试。

五种形式

所有五种形式都具有相同的结构：在循环中嵌套成员检查，使用需要线性扫描来回答成员问题的容器。

扫描关键字列表

对 MOAD-0001 进行审计意味着在循环内 grep 成员测试关键字：

- Python：in 与 list 变量一起使用，.count()，list.index()

- Java：ArrayList.contains()，List.contains()，LinkedList.contains()

- JavaScript：Array.includes()，Array.indexOf()，Array.find()

- C++: std::vector::find(), 手动循环使用 == 比较 [BLOCK_TYPE SECTION/STEP]

- Go: slices.Contains(), 手动循环遍历 slice [BLOCK_TYPE SECTION/STEP]

在每种情况下的修复方法：将顺序容器替换为哈希容器。list → set。ArrayList → HashSet。Array → Set。vector → unordered_set。slice → map[T]struct{}。 [BLOCK_TYPE SECTION/STEP]

一个关键字。一次替换。零行为改变。在 N=1,000 时获得 1,000× 的加速。 [BLOCK_TYPE SECTION/STEP]

审计一段代码片段 [BLOCK_TYPE SECTION/STEP]

将 MOAD-0001 模式识别应用于真实代码片段。 [BLOCK_TYPE SECTION/STEP]

一行代码，四种语言

四种语言中修复 MOAD-0001 的方法：

# Python
visited = []       # 之前：O(N) 成员检查
visited = set()    # AFTER:  O(1) membership

// Java
List<Node> visited = new ArrayList<>();    // BEFORE
Set<Node> visited = new HashSet<>();       // AFTER

// JavaScript
const visited = [];      // 之前：Array.includes() O(N)
const visited = new Set(); // 之后：Set.has() O(1)
// visited.push(n) → visited.add(n)
// visited.includes(n) → visited.has(n)

// Go
visited := []NodeID{}              // 之前：slices.Contains() O(N)
visited := make(map[NodeID]struct{}) // 之后：map 查找 O(1)
// _, ok := visited[n]  // 用于成员检查
// visited[n] = struct{}{}  // 用于插入

在所有情况下：相同行为、相同输出、相同测试通过。仅增长率发生变化。

该修复未改变的内容

- 算法的逻辑行为：深度优先仍按深度优先方式访问

- 输出正确性：相同节点以相同顺序被访问（在 DFS 内）

- 测试结果：任何检查正确性的测试继续通过

该修复会改变什么

- 成员测试：O(N) → O(1)

- 循环总时间：O(N²) → O(N)

- 当 N=1,000 时：快 1,000 倍

- 当 N=10,000 时：快 10,000 倍

一个限制：顺序

哈希容器（set、HashSet、unordered_set）不保留插入顺序。在 Python 3.7+ 中，dict 会保留插入顺序，但普通 set 不会。在 Java 中，HashSet 不保留顺序，而 LinkedHashSet 会保留。

如果既需要成员关系又需要顺序：维护两个结构。用 set（或 HashSet）进行 O(1) 的成员测试，用单独的 list（或 ArrayList）进行有序遍历。或者在 Java 中使用 LinkedHashSet，它同时提供两者。

对于图遍历中的 MOAD-0001：visited 回答的是一个二元问题（该节点是否已被访问过？）。对于成员关系问题，顺序并不重要。遍历顺序由栈或队列决定，而非 visited。

成员关系 vs 顺序

在 Tarjan 强连通分量算法中，onStack 跟踪当前 DFS 调用栈上剩余的节点。它需要回答两个问题：(1) 成员关系——该节点当前是否在栈中？(2) 在 DFS 路径结束时，按顺序弹出节点，直到遇到该节点。

一个朴素的实现使用 List 作为 onStack，通过 contains() 回答成员关系问题——每次检查为 O(N)，对于大图总时间复杂度为 O(N²)。

为什么这是披露而非补丁

MOAD-0001 存在于 60 多个软件生态系统中超过 1000 个已验证的站点。包括构建工具中的图遍历、网络路由守护进程中的路由去重、游戏引擎中的碰撞检测、操作系统调度器中的资源分配。

每个站点：代码正确。每个站点：当 N 超过阈值时，O(N²) 增长就会显现。

披露流程

仅打补丁而不进行上游披露，只能修复一个站点。该模式会在下一个版本、下一个库、下一个语言移植中再次出现。披露：命名该模式，将其记录为 CWE-407（算法复杂度：低效算法复杂度），发布识别启发式方法和一行修复方案。这样每个阅读披露的开发者都能识别并修复自己的实例。

Hamming 将此称为“授人以鱼”与“授人以渔”的区别。补丁是授人以鱼。披露——命名 MOAD-0001、记录模式、推广修复——则是教授识别启发式方法。

永久计算机扩展

汉明致力于点式解决方案：修复这个过滤器，改进这段代码。非汉明则添加披露层：命名模式、发布启发式方法，并将其贡献给公共领域。

复合知识原则在此以生态系统规模发挥作用。一位研究者命名一个模式。一百位开发者在自己的代码库中识别出它。一千行 O(N²) 代码变为 O(N)。基础设施变得更快，惠及所有在其上构建的人。

这就是巨龙的成长：同样的火焰（解决重要问题、复合知识、系统思维），不同的飞翔（开放披露、公共所有权、无需赞助者）。