优化天生二次复杂度的算法

背景

WhatChord 是一款 MIDI 和弦识别应用：它监听用户在 MIDI 键盘上弹奏的音符，并实时显示和弦名称。例如，同时按下 C、E、G 三个音，它会显示 C major。这听起来像是一个字典查找，对于这个例子也确实差不多。但实际的演奏远没有那么规整：相同的音符可能因周围音乐环境而有多个合法名称；演奏者会省略音符或添加色彩音；和弦还可能在两只手之间分散排列。因此，WhatChord 的引擎并不直接查找和弦，而是将命名问题转化为一个排序问题：列出所有合理的解释（候选名），对每个候选项进行评分，然后按照音乐家期望阅读的顺序排列。

文中需要解释两个术语：

• 声部（voicing）：指正在演奏的具体音符集合，包括最低音（低音）。例如“C-E-G”和“E-G，然后高八度的 C”是同一个和弦的两种不同声部。
• 候选名（candidate）：一个声部可能的名称之一。例如，四个音符 C-E-G-A 可以被解读为 C6 或 Am7 等，因此引擎为每个声部生成多个候选名，并需要从中选择并排序。

本文聚焦于这个过程的最后一步：排序。当团队构建了一个可重现的基准测试，并测量引擎在缓存未命中时的时间消耗时，结果非常不平衡：排序约占 99% 的时间，评分仅占 1%。一个常见的七和弦在未缓存时的分析需要几毫秒，其中几乎所有时间都花在了对已评分的候选名进行排序上。

核心内容

为什么不能使用普通的排序

要对列表排序，你需要给语言提供一个比较器（comparator）：一个接受两个元素并报告哪个应该排在前的函数。所有通用排序算法都假定该函数描述了一个一致的顺序，特别是传递性：如果 A 在 B 前，B 在 C 前，那么 A 一定在 C 前。违反传递性会导致排序结果未定义——通常不会崩溃，但可能将元素放在无意义的位置。

WhatChord 的比较器故意不满足传递性。大多数情况下，它根据候选名的拟合分数（fit score）排序，但有两种音乐上的覆盖规则可以超越分数：

• 硬规则（hard rules）：结构化的覆盖，用于处理分数更高但名称错误的情况（例如，优先选择改编的属和弦，而不是一个虽符合原始音符但读起来更差的减七和弦重拼写）。硬规则可以无视分数差距，让低分候选名排在高分候选名之上。
• 平局裁决（tie-breakers）：仅当两个候选名分数相差很小（0.20 分以内，代码中称为 nearTieWindow）时生效，用于捕捉单个数字无法表达的音乐启发式规则。

由于硬规则忽略分数差距，可能导致循环：A 打败 B，B 打败 C，C 打败 A。不存在一个同时满足所有三者的顺序，因此排序算法无法返回一致的结果。如果将一个循环比较器交给通用排序，结果将取决于候选名的初始顺序。

引擎的线性化方法

因此引擎不进行排序，而是将关系线性化，把成对偏好网络转化为一个有序列表：

// beats[i][j] == true 表示候选 i 应排在 j 之上
// 关系可能包含循环：a > b > c > a
List<Candidate> linearize(List<Candidate> cands, List<List<bool>> beats) {
  final result = <Candidate>[];
  final remaining = { ...allIndices };
  while (remaining.isNotEmpty) {
    // 优先选择一个最大元素：没有被任何剩余元素打败的元素
    var pick = firstUnbeaten(remaining, beats);
    // 如果没有最大元素，说明存在循环。通过 Copeland 胜场数打破循环：
    // 该候选打败了多少个其他候选。全局统计剩余元素。
    pick ??= mostWins(remaining, beats);
    result.add(cands[pick]);
    remaining.remove(pick);
  }
  return result;
}

两个关键点：

1. 要知道一个候选是否“没有被任何剩余元素打败”，需要完整的成对结果矩阵：每个 beats[i][j] 组合。构建这个矩阵需要 n² 次比较器调用，其中 n 是候选数。
2. 当循环阻碍进展时，平局裁决借鉴了投票理论中的 Copeland 方法：统计每个候选打败了多少个其他剩余候选，选择打败最多的那个。这个计数是全局的，对所有剩余候选求和。正是这个全局计数使得许多看似诱人的捷径不可靠。

成本随和弦增长而增加

引擎为每个合理的根音与声部中可找到的和弦形状组合生成一个候选名，因此候选数随音符增加而急剧上升：

• 即使是一个简单的三音三和弦，也会产生 25 个候选名。
• 团队保留了一组故意设计成对抗性、歧义性强的声部测试集（称为“神谕语料库”，每个用例都有已知正确答案），其中候选数中位数约为 75，最大为 143。
• 构建 75 个候选的成对矩阵意味着超过 5000 次比较器调用（代码中称为 _decide）。每次调用历史上都要扫描所有 21 条硬规则才能做出决定。由于矩阵将每个候选与所有其他候选进行对比，工作量随候选数平方增长：O(n²)。

这就是时间消耗的主要来源。目标是降低这一成本，同时不改变输出。基准测试通过记录精确的操作次数（如生成了多少候选、进行了多少次比较）来保持诚实。这些整数只取决于输入和代码，与硬件无关，因此算法意外改变会表现为计数变化，而不会隐藏在噪声计时中。

优化 #1：为硬规则扫描添加门控

第一个观察是：几乎所有 21 条硬规则都不可能适用于给定的一对候选。每条规则只在特定的结构配对中触发（例如，变五度属和弦与远程重拼写，完整三和弦与有缺陷的转位解读等），而且关键的是，该条件是候选局部的：它只取决于单个候选的质量、扩展或预计算特征，从不依赖于与之比较的候选。

因此，每条规则都获得一个门控（gate）：一个对单个候选的快速测试，保证只要规则可能适用就返回“是”。每个候选预计算一个位掩码（bitmask），其比特位标记该候选符合哪些规则。对于一对候选，两个掩码的按位与运算结果正好是两者都符合的规则集合，然后只检查这些规则。

// 每个候选预计算一次：O(n * rules)，而非 O(n^2)
final gateMasks = [for (final c in cands) gateMaskFor(c)];
// 一条规则需要两个操作数分别扮演不同角色，因此只有当两个候选都通过其门控时才可能触发。
// 跳过的规则本来也会返回 null，因此这是证明输出相同的，不仅仅是经验验证。
final shared = gateMasks[i] & gateMasks[j];
for (final rule in rulesIn(shared)) { ... }

一个被跳过的规则本来也会返回 null，因此这个优化在数学上保证了输出相同，而不只是经验上有效。候选生成和评分未受影响，生成计数器保持字节一致，排名黄金数据以及循环和硬规则的单元测试均通过不变。如果门控过于狭窄，会静默丢失真实决策，因此这些测试套件是安全网。

结果：对抗性语料库的未缓存分析时间下降了约 27%，日常声部加速了 1.2 到 1.7 倍。这是一个常数因子优化：相同的成对工作量，但执行更快。算法仍然是 O(n²)。

什么没起作用：按角色拆分门控

那个单一的联合门控对于“其他”侧很常见的规则（例如“任何斜杠和弦”或“任何七和弦”）过于宽泛。一个改进思路是将每个门控拆分为两半，角色 A 和角色