Optimizing an Algorithm That's Quadratic by Design
The article explores optimizing a chord-ranking algorithm whose complexity is quadratic by design, examining performance trade-offs and potential improvements in its computational efficiency.
Background
- This article details a technique for speeding up the "chord ranking" algorithm used by the whatchord website, which lists likely chord names for a set of musical notes.
- The core problem: the original algorithm compared every possible chord name against every possible pitch set, leading to "quadratic" (n²) complexity — fine for small datasets but slow for large ones.
- The fix: precompute a signature (a bitmask of pitches) for each chord type, invert the lookup map so each pitch-set points directly to its best chord names, and cache results.
- Why it matters: on a "full" test with thousands of enharmonically equivalent note sets, the optimized version ran 94,000× faster, dropping from ~94 seconds to 1 millisecond. This makes real-time chord detection in music apps practical. The author also mentions a "trie" data structure as an even more efficient alternative.