优化一个设计上为二次的算法

# 优化一个本质上是二次的算法 来源：https://whatchord.earthmanmuons.com/articles/chord-ranking-performance.html ## 引擎在做什么 WhatChord 是一个应用，它监控你在 MIDI 键盘上弹奏的音符，并在你弹奏时命名和弦。按下 C、E 和 G 一起，它会显示 C major。这听起来像是一次字典查询，对于这个例子，它几乎就是。问题在于，真实的演奏很少如此整洁：相同的音符可以根据周围的音乐有多种合法名称，演奏者会省略音符并加入色彩音，而且一个和弦可以分布在两只手上。因此，引擎并不进行和弦查找。它将命名视为一个**排名**问题：列出所有可能的解释，对每个解释进行评分以确定其适合程度，然后按照音乐家预期阅读的顺序排列。 两个术语反复出现： - **Voicing** 是正在演奏的特定音符集合，包括哪个音符是最低音（低音）。“C, E, G”和“E, G，然后高八度的 C”是同一个和弦的两种 voicing。 - **Candidate** 是一个 voicing 的一个可能名称。四个音符 C， E, G， A 可以被解读为 C6 或 Am7 等，因此引擎为每个 voicing 生成许多 candidate，并且必须进行选择和排序。 本文涉及过程的最后一步：排名。当我们构建一个可重复的基准测试，并测量引擎在缓存未命中时的时间花费时，答案是不平衡的：**排名大约占 99%；评分只占 1%。** 对一个常见七和弦的未缓存分析需要几毫秒，几乎所有时间都用在了对已经评分的 candidate 进行排序上。 ## 为什么排名不能使用普通的排序 要对列表进行排序，你需要向语言提供一个**比较器**：一个接受两个项目并报告哪个应该排在前面的函数。所有通用排序都假设该函数描述了一个一致的排序，特别是它是可传递的：如果 A 应该在 B 之前，B 在 C 之前，那么 A 必须在 C 之前。违反这一点，排序的结果是未定义的。它通常不会崩溃，但可能会将项目放置在不合理的位置。 WhatChord 的比较器故意不是可传递的。大多数情况下，它根据契合度评分对两个 candidate 进行排名，但两种音乐上的覆盖规则可以超越评分： - **硬规则** 是结构性的覆盖规则，用于处理即使评分更高但名称错误的情况（例如，倾向于一个改变属性和弦而不是一个减和弦斜线转位，后者虽然符合原始音符但读起来更差）。无论差距多大，硬规则都可以将评分较低的解读提升到评分较高的之上。 - **平局打破规则** 仅当两个 candidate 的评分在一个小窗口内（0.20 分，代码中常量称为 `nearTieWindow`）时适用，捕获单一数字无法表达的音乐启发式规则。 由于硬规则忽略评分差距的大小，你可能会得到一个循环：A 胜 B，B 胜 C，C 胜 A。没有单一排序能同时满足这三个条件，所以排序无法返回连贯的结果。将一个循环的比较器交给通用排序，结果可能取决于 candidate 的初始顺序。 因此，引擎不进行排序。它**线性化**关系，将成对偏好的网络转换为一个有序列表： ```dart // beats[i][j] == true => candidate i 应排在 j 之上。 // 关系可能包含循环：a > b > c > a。 List linearize(List cands, List<bool> beats) { final result = []; final remaining = { ...allIndices }; while (remaining.isNotEmpty) { // 倾向于一个最大元素：没有被任何剩余元素打败的。 var pick = firstUnbeaten(remaining, beats); // 如果没有最大元素，即存在循环。通过 Copeland 胜局数打破： // 该 candidate 打败了其他剩余中的多少个。全局计算剩余元素。 pick ??= mostWins(remaining, beats); result.add(cands[pick]); remaining.remove(pick); } return result; } ``` 两个重要点。首先，要了解一个 candidate 是否“没有被任何剩余元素打败”，你需要完整的成对结果矩阵：每个 `beats[i][j]` 组合。构建该矩阵需要 `n²` 次比较器调用，其中 `n` 是 candidate 的数量。其次，当循环阻塞进展时，平局打破借用了投票理论中的 Copeland 方法：计算每个 candidate 打败了多少其他剩余 candidate，并选择打败最多的那个。该计数是**全局的**，在所有剩余 candidate 上求和。正是这个全局计数使几种有吸引力的捷径不安全。 ## 代价是真实的，并且随和弦增长而增长 引擎为每个合理的根音与 voicing 中找到的和弦形状配对构建一个 candidate，因此随着你添加音符，candidate 数量急剧增加： | Voicing | 音符数 | Candidates | |---------|--------|------------| | C major 三和弦 | 3 | 25 | | Cmaj7 | 4 | 43 | | Cm7 | 4 | 46 | | C7 | 4 | 48 | | Cmaj9 | 5 | 67 | | 六音 voicing | 6 | 90 | | 七音密集 | 7 | 131 | 即使是一个简单的三和弦三音也产生 25 个 candidate。我们保留了一个测试集，包含故意制造歧义的 voicing（一个“预言语料库”，因为每个案例都有一个已知正确的结果来检查），其中 candidate 的中位数约为 75，最大值 143。为 75 个 candidate 构建成对矩阵意味着超过 5000 次比较器调用，代码中称为 `_decide` 的函数。每次调用历史上都要扫描所有 21 条硬规则才能决定任何事情。因为矩阵将每个 candidate 与每个其他 candidate 配对，工作量随 candidate 数量的**平方**增长：它是 O(n²)。这就是时间的去向。 目标是在不改变输出的情况下削减成本。基准测试通过记录精确的操作计数来保持诚实，例如构建了多少 candidate 以及运行了多少次比较。这些整数仅取决于输入和代码，而不依赖于硬件，因此偶然的算法更改会显示为更改的计数，而不是隐藏在嘈杂的计时中。 ## 胜利 #1：门控硬规则扫描 第一个观察结果是，在给定的配对中，21 条硬规则几乎不可能全部适用。每条规则仅在特定的结构配对时触发（例如，改变五音的属和弦与一个遥远的拼写、完整三和弦与一个不完整的转位解读等），关键是，该条件是**candidate 局部**的：它仅取决于单个 candidate 的质量、扩展或预先计算的特征，而从不取决于它与之比较的 candidate。 因此，每条规则都有一个**门**：一个在单个 candidate 上的快速测试，保证在规则可能适用时返回“是”。每 candidate 一次，我们预先计算一个 bitmask，一个整数，其位标记该 candidate 有资格应用哪些规则。对于一个配对，它们两个掩码的按位与正是两者都有资格的规则集合，我们只检查那些。 ```dart // 每 candidate 预先计算一次：O(n * rules)，而不是 O(n²)。 final gateMasks = [for (final c in cands) gateMaskFor(c)]; // 一个规则需要每个角色一个操作数，因此它仅在两个 candidate 都通过其门时才能触发。 // 跳过的规则将返回 null。 final shared = gateMasks[i] & gateMasks[j]; for (final rule in rulesIn(shared)) { ... } ``` 跳过的规则本来会返回 null，因此这是**可证明输出相同**的，而不仅仅是经验验证。candidate 生成和评分未受影响，生成计数器保持字节相同，排名黄金测试以及循环和硬规则单元测试通过且未更改。过于狭窄的门会静默地丢弃真实的决策，因此这些测试套件是安全网。 结果：对预言语料库的未缓存分析计时下降了约 **27%**，日常 voicing 加速了 1.2 到 1.7 倍。这是一个常数因子的胜利：相同的成对工作，完成得更快。算法仍然是 O(n²)。 ## 无效的方法，第 1 部分：按角色拆分门 那个单一的组合门对于“另一侧”常见的规则来说很宽泛，比如“任何斜线和弦”或“任何七和弦”。一种细化是将每个门分成两半，角色 A 和角色 B，并且仅当两个 candidate 占据相反角色时才触发规则：`(maskA[i] & maskB[j]) | (maskB[i] & maskA[j])`。我们为所有 21 条规则实现了它。它保持输出相同，计数器未变且测试通过。它在典型 voicing 上带来了 1% 到 3% 的改进，在密集语料库上大约 0%，在基准噪音之内。我们恢复了它。组合门已经捕获了主要胜利：跳过了**两个** candidate 都没有资格的配对。拆分角色只能修剪两个 candidate 在相同角色都有资格的配对，这是一个薄片，而第二个掩码使预计算加倍。在组合门之后，瓶颈不再是硬规则扫描。它是 O(n²) 机制本身：成对矩阵和线性化。 ## 为什么减少 candidate 打破了排名 如果三和弦的 25 个 candidate 感觉浪费，直接的做法是生成或保留更少。缩小 candidate 集合直接攻击 n² 项。不幸的是，这不安全，因为 Copeland 计数是全局的。 - **按评分保留前 N 个**会在排名运行前丢弃评分较低的 candidate。但平局打破是全局的 Copeland 计数，因此删除 candidate 会改变其他人的胜局总数。这可能会重新打乱应用向用户显示的备选项。这适用于任何 N 和任何截断；问题在于被丢弃的 candidate 曾是幸存者的衡量标准的一部分。 - **在生成时更早丢弃 candidate** 有相同的问题。你可能会限制哪些根音或和弦模板允许生成 candidate，但排名前移除的任何 candidate 同样从每个人的胜局总数中消失。 - 唯一可证明安全的丢弃是 Condorcet 失败者：一个打败了所有其他且没打败任何人的 candidate，且没有硬规则胜利。但找到一个需要完整的成对比较，而我们正是试图避免这个。 因此，减少 candidate 看起来是死胡同。我们把它放在一边，并尝试计算相同的完整排名得更快。 ## 无效的方法，第 2 部分：排序排名重新设计 下一个重新设计保持完全相同的输出，并试图更快地计算它。从基于评分的廉价初始猜测顺序开始：按评分排序，平局按根音打破。称之为**种子顺序**。昂贵的比较器在几乎每对上都与这个廉价种子顺序一致。它只能在两种情况下不一致： - 硬规则触发，这只能在两个候选者的门掩码都已标记为有资格时发生；或 - 平局打破规则推翻评分，这只能在两个 candidate 评分相距不超过 0.20 时发生。 其他每一对都按构造与种子顺序匹配。理论是，简单 voicing（常见的实时演奏情况）会走快速路径：仅在两个可能隐藏无序对的地方检查，如果没有，则返回种子顺序不变，跳过整个 n² 矩阵。如果出现任何无序对，则回退到完整线性化器。 在构建之前，我们进行了性能分析以确认重新设计甚至针对正确的成本。在预言语料库上，排名内的临时阶段计时器： | 阶段 | 占排名比例 | |------|------------| | 成对矩阵构建 | 97.0% | | 线性化 | 2.1% | | 特征 | 0.4% | | 门掩码 | 0.4% | | 种子排序 | 0.1% | 构建矩阵占排名的 97%，其中 `_decide` 调用的 n² 循环占 99.8%（分配矩阵本身占 0.2%）。更少的比较是正确的目标。 我们构建了一个安全框架，在测试期间同时运行快速路径和完整算法，并断言它们产生相同的顺序（该检查在发布构建中被编译掉）。它是正确的。它也**从未触发**。快速路径在我们测量的**每个** voicing 上**零次**触发，包括一个简单的 C major 三和弦。每个测量的 voicing 在其长 candidate 列表的某个地方至少有一个近平局对，平局打破规则翻转了它，而单个无序对就强制完全回退。检测过程增加了工作却没有找到可用的快速路径，净损失约 1%。 然后我们尝试只对**纠缠**的 candidate 重新排名，而不是所有 n，即那些通过近平局或共享硬规则链接的。为了找出这些纠缠有多大，我们使用联合查找将 candidate 分组为连接集群。下表显示了每个 candidate 集合中最大连接集群的份额。接近 100% 的值意味着局部回退仍然必须几乎重新排名所有内容： | 输入集合 | Candidates | 最大集群份额 | |-----------|------------|--------------| | 预言语料库 | 75 中位数 / 143 最大值 | 99% 中位数 / 100% 最大值 | | C major 三和弦 | 25 | 100% | | Cm7 / C7 | 46 / 48 | 100% / 100% | | Cmaj9 / Cm11 | 67 / 90 | 99% / 100% | 最大的纠缠本质上是整个 candidate 集合。评分足够接近，以至于 0.20 以内的近平局链接链几乎贯穿所有内容，因此只重排纠缠意味着还是几乎重排所有内容。没有小东西可以隔离。 ## 胜利 #2：使每次比较更便宜 由于 n² 是固有的（candidate 不能安全地丢弃，关系没有局部性），剩下的唯一杠杆是单次 `_decide` 调用的成本。在语料库上测量配对的去向： | 配对 | 份额 | |------|------| | 可跳过（仅评分决定） | 20% | | 调用 `_decide` | 80% | | ...其中达到平局打破 | 全部配对的 5% | 平局打破扫描不是成本；只有 5% 的配对达到它。大部分是大约 75% 的硬规则有资格但超出平局窗口的配对：它们调用 `_decide`，运行门控硬规则循环，然后仍然根据评分决定。该循环仍然迭代所有 21 条规则检查掩码位，即使只设置了一个或两个位，每次语料库传递大约 1800 万次浪费的迭代。两个输出相同的快速路径解决了这个问题： - **评分短路：**在成对矩阵循环中，当共享门掩码为空（没有硬规则可以触发）且评分差距超过 `nearTieWindow` 时，直接从评分设置结果并完全跳过 `_decide`，以及它的分配。 - **设置位迭代：**在 `_decide` 内部，只遍历共享掩码的设置位，从最低位开始以保持规则顺序，而不是扫描所有 21 条规则。 两者都可证明与旧输出相同，没有 Copeland 重排风险，一起在对抗语料库上带来了约 **4%** 的改进。 一个猜测被证明是错误的：我们期望这些比较会消耗大量短期内存。但在短路移除了约 20% 的每次比较分配后，总分配几乎没有变化，因此更花哨的无分配版本不值得构建。 那是安全的每对胜利的终点。门掩码索引和每对快速路径是可靠的且可证明相同，但剩余的是在密集评分的 candidate 上的 n² 迭代。在我们所持的约束下，没有剩余的杠杆了。 综合起来，安全的优化带来了大约 30% 的改进。 ## 重新审视：我们在回答错误的问题 以上的每个结论，包括死胡同剪枝和本质上的 n²，在一个假设下都是正确的：**字节相同的输出**。我们一直在保护每个 candidate 的确切顺序。这比产品需要的更强。面向用户的契约只有两个保证： 1. 选择的 #1 和弦被保存； 2. 呈现的备选项集合被保存。 #2 及之后的备选项的**顺序**不是保证。近平局备选项常常是同一个声音的等音转写，相同音符的不同写法，它们的相对顺序已经由一个任意的回退（按根音排序）决定。 （文章在这里结束，后续还有内容但未给出。翻译依据提供的英文文本进行，截至此处。）