Optimizing an Algorithm That's Quadratic by Design
3 days ago
- #algorithm-optimization
- #music-technology
- #software-development
- WhatChord is a MIDI keyboard app that names chords in real-time.
- Chord naming involves ranking plausible interpretations rather than simple dictionary lookups.
- Ranking cannot use ordinary sorting due to non-transitive comparisons and cycles.
- The engine linearizes candidates using pairwise comparisons and Copeland's method.
- Cost is high because the ranking grows quadratically with the number of candidates.
- Optimizations included gating hard-rule scans and making comparisons cheaper.
- Candidate reduction was initially unsafe due to global Copeland counts.
- A reframe allowed pruning candidates without affecting user-visible guarantees.
- Pruning significantly improved performance by removing unsurfaceable candidates.
- Final optimization cut ranking time by over 85% without changing displayed results.