設計上二次関数的なアルゴリズムの最適化

WhatChordのエンジンは何をしているのか WhatChordは、MIDIキーボードで演奏されたノートを監視し、演奏中にコード名を付けるアプリです。C-E-Gを同時に押すと、Cメジャーと表示されます。これは辞書検索のように聞こえますし、その例ではほぼその通りです。問題は、実際の演奏はそれほど整然としていないことです。同じノートでも、周囲の音楽によっていくつかの正当な名前を持つことがあり、プレイヤーはノートを省略したり、色音を追加したり、コードが両手にまたがることがあります。そのため、エンジンはコードを検索しません。名前付けをランキング問題として扱います。あらゆるもっともらしい解釈をリストアップし、それぞれがどれだけうまく適合するかをスコアリングし、次にミュージシャンが期待する順序で並べます。 説明に値する2つの用語があります。ボイシングとは、どのノートが一番下にあるか（ベース）を含む、演奏されているノートの特定のセットです。「C-E-G」と「E-G、次にCを1オクターブ上」は、同じコードの2つのボイシングです。候補とは、ボイシングの1つの可能な名前です。4つのノートC-E-G-Aは、C6またはAm7などとして読み取ることができます。そのため、エンジンはボイシングごとに多くの候補を生成し、それらを選択して順序付ける必要があります。この記事は、プロセスの最後のステップ、ランキングについてです。 再現可能なベンチマークを構築し、エンジンがキャッシュミスでどこに時間を費やしているかを測定したところ、その答えは偏っていました。ランキングが約99%を占め、スコアリングは約1%です。キャッシュされていない一般的なセブンスコードの分析は数ミリ秒かかり、その時間のほぼすべてが、すでにスコアリングされた候補を並べるために費やされます。 なぜランキングは通常のソートを使用できないのか リストをソートするために、言語にコンパレータを渡します。これは2つのアイテムを受け取り、どちらが先に来るべきかを報告する関数です。すべての汎用ソートは、その関数が一貫した順序を記述し、特に推移的であると仮定します。AがBより前に来るべきで、BがCより前に来るべきなら、AはCより前に来るべきです。これを破ると、ソートの結果は未定義になります。通常はクラッシュしませんが、アイテムが不合理な位置にドロップされる可能性があります。 WhatChordのコンパレータは意図的に推移的ではありません。ほとんどの場合、2つの候補をフィットスコアでランク付けしますが、2種類の音楽的なオーバーライドがスコアを上回ることができます。ハードルールは、高いスコアが単に間違った名前である場合の構造的なオーバーライドです（例えば、生のノートに合うが読みにくいディミニッシュスラッシュ表記よりも、変更されたドミナントコードを優先するなど）。ハードルールは、スコアの差がどれほど大きくても、低いスコアの読み方を高いスコアの読み方よりも昇格させることができます。タイブレーカーは、2つの候補が互いにわずかな差（コード内の定数である0.20ポイント）にある場合にのみ適用され、単一の数値では捉えられない音楽的なヒューリスティクスを捉えます。 ハードルールはスコアの差の大きさを無視するため、サイクルが発生する可能性があります。AがBを上回り、BがCを上回り、CがAを上回る場合です。3つすべてを同時に満たす単一の順序はありません。そのため、ソートが返すものはありません。循環的なコンパレータを汎用ソートに渡すと、結果は候補の開始順序に依存する可能性があります。したがって、エンジンはソートしません。ペアワイズな好みのウェブを1つの順序付けられたリストに変換して、関係を線形化します。 ``` // beats[i][j] == true => candidate i should rank above j. // The relation may contain cycles: a > b > c > a. List<Candidate> linearize(List<Candidate> cands, List<List<bool>> beats) { final result = <Candidate>[]; final remaining = { ...allIndices }; while (remaining.isNotEmpty) { // Prefer a maximal element: one beaten by nothing still remaining. var pick = firstUnbeaten(remaining, beats); // No maximal element means a cycle. Break it by Copeland win-count: // how many of the others this candidate beats. Global over remaining. pick ??= mostWins(remaining, beats); result.add(cands[pick]); remaining.remove(pick); } return result; } ``` 2つの重要な点があります。第一に、候補が「残りのものに何も負けない」かどうかを知るには、ペアワイズな結果の完全なマトリックスが必要です。すべてのbeats[i][j]の組み合わせです。このマトリックスの構築は、コンパレータへのn²回の呼び出しを意味します。ここでnは候補の数です。第二に、サイクルが進行を妨げる場合、タイブレークは投票理論のCopelandの方法を借用します。各候補が他の候補のいくつに勝つかを数え、最も多く勝ったものを選びます。そのカウントはグローバルで、残りのすべての候補に合計されます。そのグローバルカウントが、魅力的なショートカットのいくつかが安全でない理由です。 コストは現実的であり、コードの複雑さとともに増加します エンジンは、ボイシングで見つけられるルートノートとコードシェイプのあらゆる合理的なペアリングに対して候補を構築するため、ノートを追加すると候補の数は急激に増加します。 Voicing Notes | Candidates ------------|----------- C major triad | 3 | 25 Cmaj7 | 4 | 43 Cm7 | 4 | 46 C7 | 4 | 48 Cmaj9 | 5 | 67 Six-note voicing | 6 | 90 Seven-note dense | 7 | 131 単純な3ノートのトライアドでも25個の候補が生成されます。私たちは、意図的に敵対的で曖昧なボイシングのテストセット（各ケースに既知の正解があり、チェックできるため「オラクルコーパス」と呼ばれます）を保持しており、そこでは候補の数は中央値で約75、最大で143になります。75個の候補のペアワイズマトリックスを構築することは、コンパレータへの5,000回以上の呼び出しを意味します。この関数はコードでは_decideと呼ばれます。各呼び出しは、歴史的に21個すべてのハードルールをスキャンしてから何かを決定していました。マトリックスはすべての候補を他のすべての候補と対比させるため、作業は候補数の二乗で増加します。つまりO(n²)です。そこに時間が費やされていました。目標は、出力を変更せずにそのコストを削減することでした。 ベンチマークは、構築された候補の数や実行された比較の数など、正確な操作カウントを記録することで、私たちを正直に保ちました。これらの整数は入力とコードのみに依存し、ハードウェアには依存しないため、偶然のアルゴリズム変更は、ノイズの多いタイミングに隠れるのではなく、変更されたカウントとして現れます。 勝利 #1: ハードルールスキャンのゲート 最初の観察は、21個のハードルールのほとんどが、特定のペアに適用される可能性がほとんどないということです。各ルールは、特定の構造的なペアリング（リモートスペリングに対する変更されたフィフスドミナント、生のノートに合うが読みにくいディミニッシュスラッシュ表記、など）に対してのみ発火し、そして決定的に、その条件は候補ローカルです。それは単一の候補の品質、拡張、または事前計算された特徴にのみ依存し、比較されている候補には決して依存しません。したがって、各ルールにはゲートがあります。ルールが適用される可能性が常にある場合に「はい」を返すクイックテストです。候補ごとに、ビットマスクを事前計算します。これは、どのルールにその候補が適格であるかを示すフラグが立てられた整数です。ペアの場合、2つのマスクのビットワイズANDは、両方が適格であるルールの正確なセットであり、それらのみをチェックします。 ``` // Precompute once per candidate: O(n * rules), not O(n^2). final gateMasks = [for (final c in cands) gateMaskFor(c)]; // A rule needs one operand in each role, so it can only fire when // both candidates pass its gate. Skipped rules would return null. final shared = gateMasks[i] & gateMasks[j]; for (final rule in rulesIn(shared)) { ... } ``` スキップされたルールは anyway null を返していたため、これは経験的に検証されただけでなく、証明可能に出力同一です。候補生成とスコアリングは変更されておらず、生成カウンターはバイト単位で同一のままであり、ランキングのゴールデンとサイクルおよびハードルール単体テストは変更なくパスします。ゲートが狭すぎると、実際の決定がサイレントにドロップされるため、これらのテストスイートがセーフティネットとなります。結果：敵対的なコーパスのキャッシュされていない分析のタイミングは約27%低下し、日常的なボイシングは1.2〜1.7倍高速化しました。これは定数倍の勝利です。同じペアワイズ作業が、より速く行われました。アルゴリズムは依然としてO(n²)です。 何がうまくいかなかったか、パート1: ゲートを役割で分割する その単一の結合ゲートは、「スラッシュコード」や「セブンスコード」など、もう一方の側が一般的なルールの場合は広すぎます。1つの洗練は、各ゲートを2つの半分、役割Aと役割Bに分割し、2つの候補が反対の役割を果たす場合にのみペアに対してルールを発火させることです。(maskA[i] & maskB[j]) | (maskB[i] & maskA[j])。これを21個すべてのルールに実装しました。出力は同一のままで、カウンターは変更されず、テストもパスしました。