Optimizing an Algorithm That's Quadratic by Design
10 days ago
- #algorithm-optimization
- #music-technology
- #software-development
- WhatChord 是一款实时识别和弦名称的 MIDI 键盘应用。
- 和弦识别涉及对多种合理解释进行排序，而非简单的字典查询。
- 由于存在非传递性比较和循环现象，排序无法使用普通排序算法。
- 引擎通过两两比较和 Copeland 方法将候选和弦线性排列。
- 由于排序复杂度随候选和弦数量呈平方级增长，计算成本较高。
- 优化措施包括启用硬规则扫描门控机制和降低比较运算成本。
- 初期因依赖全局 Copeland 计数导致候选和弦缩减存在安全隐患。
- 通过重构实现了在保持用户可见效果不变的前提下安全剪枝候选和弦。
- 剪除不可呈现候选和弦的策略显著提升了系统性能。
- 最终优化使排序耗时减少超 85%，且未改变显示结果。