設計上二次関数的なアルゴリズムの最適化
Optimizing an Algorithm That's Quadratic by Design (whatchord.earthmanmuons.com)
要約
音楽アプリ「WhatChord」は、MIDIキーボードで演奏されたノートをリアルタイムで認識し、コード名を判定します。この判定プロセスは、単純な辞書検索ではなく、複数の解釈候補を生成し、それぞれをスコアリングしてランク付けする問題として扱われます。特に、候補の順序付け(ランキング)は処理時間の約99%を占めます。本記事では、このランキング処理における、通常のソートでは対応できない循環的な関係性を線形化するアルゴリズムと、そのパフォーマンスを改善するための最適化手法について解説しています。
全文翻訳
設計上二次関数的なアルゴリズムの最適化
エンジンは何をしているのか
WhatChordは、MIDIキーボードで演奏されたノートを監視し、演奏中にコード名を付けるアプリです。C-E-Gを同時に押すと、Cメジャーと表示されます。これは辞書検索のように聞こえ、その例ではほぼその通りです。しかし、実際の演奏はそれほど整然としていることは稀です。同じノートでも、周囲の音楽によっていくつかの正当な名前を持つことがあり、プレイヤーはノートを省略したり、テンションノートを追加したり、コードが両手にまたがることがあります。そのため、エンジンはコードをルックアップしません。コード名を付けることをランキング問題として扱います。つまり、考えられるすべての解釈をリストアップし、それぞれがどれだけ適合するかをスコアリングし、次にミュージシャンが期待する順序で並べます。
説明に値する用語が2つあります。
- ボイシングとは、どのノートが最も低いか(ベース)を含む、演奏されているノートの特定のセットのことです。「C-E-G」と「E-G、次に1オクターブ上のC」は、同じコードの2つのボイシングです。
- 候補とは、ボイシングの可能な名前の1つです。C-E-G-Aの4つのノートは、他のものの中でもC6またはAm7として読むことができるため、エンジンはボイシングごとに多くの候補を生成し、それらを選択して順序付ける必要があります。
この記事は、プロセスの最後のステップであるランキングについてです。再現可能なベンチマークを構築し、キャッシュミス時にエンジンがどこに時間を費やしているかを測定したところ、その答えは偏っていました。ランキングがその約99%を占め、スコアリングは約1%でした。 キャッシュされていない一般的なセブンスコードの分析は数ミリ秒かかり、その時間のほぼすべてが、すでにスコアリングされた候補を並べ替えるために費やされました。
ランキングが通常のソートを使用できない理由
リストをソートするには、言語にコンパレータ、つまり2つのアイテムを受け取り、どちらが先に来るべきかを報告する関数を渡します。すべての汎用ソートは、その関数が一貫した順序を記述し、特に推移的であると仮定します。つまり、AがBより前、BがCより前なら、AはCより前でなければなりません。それに違反すると、ソートの結果は未定義になります。通常はクラッシュしませんが、アイテムが不合理な位置にドロップされる可能性があります。
WhatChordのコンパレータは意図的に推移的ではありません。ほとんどの場合、スコアの適合度で2つの候補をランク付けしますが、音楽的なオーバーライドは2種類あり、スコアを上回ることができます。
- ハードルールは、より高いスコアが単に間違った名前である場合の構造的なオーバーライドです(たとえば、生のノートには適合するが、読みにくいディミニッシュスラッシュ表記よりもオルタードドミナントコードを優先するなど)。ハードルールは、スコアの差がどれだけ広くても、スコアの低い読み方をスコアの高い読み方より昇格させることができます。
- タイブレーカーは、2つの候補が互いにわずかなウィンドウ(コード内の定数
nearTieWindow、0.20ポイント)内にスコアする場合にのみ適用され、単一の数値では表せない音楽的なヒューリスティックを捉えます。
ハードルールはスコアの差の大きさを無視するため、サイクルが発生する可能性があります。AがBを上回り、BがCを上回り、CがAを上回る場合です。3つすべてを同時に満たす単一の順序付けはありません。そのため、ソートが返す一貫したものがありません。サイクリックコンパレータを汎用ソートに渡すと、結果は候補の開始順序に依存する可能性があります。
ハードルールがどのようなものであるかに注意してください。スコアは1つの候補に関する事実ですが、ハードルールは特定の対戦に関する判定です。この読み方は、その2つが出会ったときに、その読み方がその読み方を上回ります。他のペアリングについては何も述べていません。それが、オーバーライドを単純にスコアに折り込むことができない理由です。たとえば、常に勝つような大きなボーナスとしてです。ボーナスはそれほど狭くは保てません。それは、ルールが書かれたライバルだけでなく、リスト内のすべての候補を上回るようにその保持者を持ち上げます。スコアは候補を1つずつ評価し、ルールは2つずつ評価します。2つずつ評価する種類だけがサイクルを生成できます。この分割は、後続のすべてで静かな作業を行います。
したがって、エンジンはソートしません。それは関係を線形化し、ペアごとの選好のウェブを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は候補の数です。第二に、サイクルが進行を妨げる場合、タイブレークは投票理論からコープランドの方法を借用します。他の候補のうちそれぞれがいくつ勝つかを数え、最も多く勝つものを選びます。そのカウントはグローバルであり、残りのすべての候補に合計されます。そのグローバルカウントが、魅力的なショートカットが安全でない理由のいくつかです。
コストは現実であり、コードとともに増加する
エンジンは、ボイシングで見つけられるルートノートとコードシェイプの合理的なペアリングごとに候補を構築するため、ノートを追加すると候補数は急激に増加します。
| ボイシング | ノート数 | 候補数 |
|---|---|---|
| Cメジャートライアド | 3 | 25 |
| Cmaj7 | 4 | 43 |
| Cm7 | 4 | 46 |
| C7 | 4 | 48 |
| Cmaj9 | 5 | 67 |
| 6ノートボイシング | 6 | 90 |
| 7ノート密 | 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のすべてのルールに実装しました。出力は同一のままで、カウンターは変更されず、テストもパスしました。典型的なボイシングで1〜3%、密なコーパスで約0%のパフォーマンス向上をもたらしましたが、これはベンチマークのノイズ内でした。私たちはそれを元に戻しました。
組み合わせゲートはすでに大きな勝利を捉えていました。つまり、どちらの候補も適格でないペアをスキップすることです。役割の分割は、両方の候補が同じ役割で適格であるペアをトリムするだけです。これは薄いスライスであり、2番目のマスクは事前計算を倍増させます。組み合わせゲートの後、ボトルネックはもはやハードルールスキャンではありません。それはO(n²)の仕組み、つまりペアごとの行列と線形化です。
候補の削減がランキングを壊した理由
トライアドの25の候補が浪費のように感じる場合、直接的な解決策はそれらを生成または保持する候補を減らすことです。候補セットを縮小することは、n²項に直接対処します。残念ながら、コープランドカウントはグローバルであるため、これは安全ではありません。
- スコアで上位N件を保持すると、ランキングが実行される前にスコアの低い候補が破棄されます。しかし、タイブレークはグローバルなコープランドカウントであるため、候補を削除すると他のすべての候補の勝利合計が変更されます。これにより、アプリがユーザーに表示する代替案が再編成される可能性があります。これは、任意のNおよび任意のカットオフに当てはまります。問題は、ドロップされた候補が、生き残った候補が測定されていたものの1部であったことです。
- 生成時に候補を早期にドロップする場合も、問題は同じです。候補を生成できるルートまたはコードテンプレートを制限するかもしれませんが、ランキングの前に削除された候補は、いずれにしてもすべての人の勝利合計から削除されます。
- 証明可能な安全なドロップは、コンドルセ敗者のみです。つまり、他のすべてに負け、何も勝たず、ハードルールの勝利がない候補です。しかし、それを見つけるには、そもそも回避しようとしていた完全なペアごとの比較が必要です。
したがって、候補の削減は行き止まりのように見えました。私たちはそれを脇に置き、同じ完全なランキングをより速く計算しようとしました。
うまくいかなかったこと、パート2: ソート済みランクの再設計
次の再設計は、まったく同じ出力を維持し、それをより速く計算しようとしました。安価な最初の推測から順序を開始します。スコアでソートし、ルートノートでタイをブレークします。それをシード順序と呼びます。高価なコンパレータは、ほとんどすべてのペアでこの安価なシード順序と一致します。それは2つの状況でのみ不一致になります。
- ハードルールがトリガーされた場合。これは、ゲートマスクがすでに適格としてフラグ付けしている2つの候補の間でのみ発生します。
- タイブレーカーがスコアを上書きした場合。これは、0.20ポイント以内にスコアする2つの候補の間でのみ発生します。
それ以外のすべてのペアは、構築によりシード順序と一致しています。理論は、単純なボイシング、つまり一般的なライブプレイケースが、高速終了することでした。順序外のペアのみを、隠れることができる2つの場所でチェックし、それらが存在しない場合は、シード順序をそのまま返して、n²行列全体をスキップすることでした。もしあれば、完全な線形化にフォールバックします。
構築する前に、再設計が正しいコストをターゲットにしていることを確認するためにプロファイリングしました。オラクルコーパス全体でのランキング内のテンポラリフェーズタイマー:
| フェーズ | ランキングのシェア |
|---|---|
| ペアごとの行列構築 | 97.0% |
| 線形化 | 2.1% |
| 特徴 | 0.4% |
| ゲートマスク | 0.4% |
| シードソート | 0.1% |
行列の構築はランキングの97%を占め、その中で_decide呼び出しのn²ループは99.8%です(行列自体の割り当ては0.2%)。より少ない比較が正しいターゲットでした。
私たちは、高速パスと完全なアルゴリズムの両方をテスト中に実行し、それらが同じ順序を生成することをアサートするセーフティハーネスでそれを構築しました(チェックはリリースビルドからコンパイルアウトされます)。それは正確でした。また、トリガーされませんでした。
高速パスは、測定したすべてのボイシング、単純なCメジャートライアドを含むゼロでトリガーされました。測定されたすべてのボイシングには、長い候補リストのどこかにタイブレークが反転させる少なくとも1つのニアタイペアがあり、1つの順序外ペアでも完全なフォールバックが強制されます。検出パスは作業を追加しましたが、使用可能な高速パスは見つからず、正味の損失は約1%でした。
次に、すべてのnではなく、絡み合った候補のみを再ランク付けしようとしました。ニアタイまたは共有ハードルールによってリンクされた候補です。それらの絡み合いがどれだけ大きくなるかを見つけるために、ユニオンファインドを使用して候補を接続されたクラスターにグループ化しました。下の表は、各候補セットの最大接続クラスターのシェアを示しています。100%に近い値は、ローカライズされたフォールバックがほぼすべてを再ランク付けする必要があることを意味します。
| 入力セット | 候補数 | 最大クラスターシェア |
|---|---|---|
| オラクルコーパス | 75 中央値 / 143 最大 | 99% 中央値 / 100% 最大 |
| Cメジャートライアド | 25 | 100% |
| Cm7 / C7 | 46 / 48 | 100% / 100% |
| Cmaj9 / Cm11 | 67 / 90 | 99% / 100% |
最大の絡み合いは本質的に候補セット全体です。スコアは十分に密接しているため、0.20以内のニアタイリンクはほぼすべてをチェーンするため、絡み合いだけを再ランク付けしても、ほぼすべてを再ランク付けすることになります。分離する小さなものはありません。
勝利 #2: 各比較を安価にする
n²が本質的である(候補は安全にドロップできず、関係には局所性がありません)ため、残された唯一のレバーは、単一の_decide呼び出しのコストです。ペアがどこに行くかを測定します。コーパスパス全体で:
| ペア | シェア |
|---|---|
| スキップ可能(スコアのみで決定) | 20% |
_decide呼び出し | 80% |
| …そのうちタイブレークに到達するのは | 全ペアの5% |
タイブレークスキャンはコストではありません。5%のペアしかそれに到達しません。大部分は、ハードルール適格であるがタイウィンドウを超えているペアの約75%です。つまり、_decideを呼び出し、ゲートされたハードルールループを実行し、その後スコアで決定します。そのループは、ビットが1つまたは2つ設定されている場合でも、1800万回の無駄な反復をコーパスパスごとに実行して、マスクビットをチェックしていました。2つの出力同一の高速パスがそれに対処します。
- スコアショートサーキット: ペアごとの行列ループで、共有ゲートマスクが空(ハードルールはトリガーできない)で、スコアギャップが
nearTieWindowを超えている場合、結果をスコアから直接設定し、割り当てを含め、_decide全体をスキップします。 - セットビット反復:
_decide内で、共有マスクのセットビットのみを、ルール順序を維持するために最も低いものから順にウォークします。21のすべてのルールをスキャンするのではなく。
どちらも古い出力と証明可能な同一であり、コープランドの再シャッフルリスクを一切持ちません。そして、合わせて約4%を敵対的コーパスで獲得しました。途中で1つの推測が間違っていました。これらの比較は大量の一時的なメモリを消費すると予想していました。しかし、ショートサーキットがペアごとの割り当ての約20%を削除した後、総割り当てはほとんど移動しなかったため、より高度な割り当てフリーバージョンを構築する価値はありませんでした。
それが安全なペアごとの勝利の終わりでした。ゲートマスクインデックスとペアごとの高速パスは保証可能で証明可能な同一ですが、残りは密にスコアリングされた候補に対するn²反復です。私たちが保持していた制約の下では、もうレバーはありませんでした。安全な最適化を組み合わせると、約30%の改善が得られました。
再フレーム: 私たちは間違った質問に答えていた
上記のすべての結論、行き止まりのプルーニング、および本質的なn²は、1つの仮定の下で正しいです。バイト単位で同一の出力。私たちはすべての候補の正確な順序を保護していました。それはアプリが必要とするものよりも強力でした。
ユーザーインターフェースの契約には、正確に2つの保証があります。
- 選択された#1コードが保持されること。
- 表示される代替案のセットが保持されること。
代替案#2以降の順序は保証ではありません。ニアタイの代替案は、しばしば同じ音のエンハーモニックなスペルミス、つまり異なる方法で書かれた同じノートであり、それらの相対的な順序はすでに任意の後続処理(ルートノートによるソート)によって決定されていました。したがって、行き止まりの議論が失格と見なすコープランドの再シャッフルは、もともと固定されていなかった出力しか移動しません。以前の推論は、「バイト単位で同一の出力をプルーニングできるか?」という質問に答えました(いいえ)。製品の質問は、「ユーザーへの約束を破らずにプルーニングできるか?」です(はい)。
プルーニングは、2つの生存候補間のヘッドツーヘッド比較を決して変更しません。それは、線形化がサイクルをブレークする必要がある場合に、サイクルをブレークするために使用されるグローバルコープランドカウントを変更するだけです。そのカウントは部分的に人工的なものです。つまり、明らかに間違った読み方をすべて打ち負かした候補の合計は、別の妥当な読み方と比較してどのように見えるかについてはほとんど語っていません。表示不可能なテールをドロップすると、そのパディングが削除されます。結果はより正確な順序ではありません。コープランドカウントは音楽的品質の尺度ではなかったためです。それは、破棄された読み方をそれぞれがどれだけ打ち負かしたかによってもはや揺るがされない、より任意でないフォールバックです。
プルーニングマージンの選択
プルーニングは、上位スコアから固定マージン内にあるすべての候補を保持し(rankingPruneMargin)、残りをランキングの前にドロップします。ただし、このマージンはチューニングノブではなく、正確さのしきい値です。それが、候補がユーザーに表示される可能性のあるギャップよりも常に小さい場合、プルーニングはユーザーが見るべきものを削除します。したがって、それは最悪の場合の境界であり、平均または標準偏差から設定するのは間違いです。典型的なケースのバンドは、マージンが保護するはずのまれなケースで失敗する可能性が最も高くなります。
表示される候補は、上位スコアからどれだけ下に座ることができますか?それを表示ギャップと呼びます。最初の推定は単純で間違っていました。ハードルールの到達範囲に0.20のニアタイウィンドウを加えたもの、約1.8です。しかし、エンジンは表示されるすべての候補を、最低ランクのニアタイ候補まで表示し、線形化は厳密にスコア順ではありません。そのため、より深い読み方が表示バンドに引き上げられる可能性があります。測定された表示ギャップは、到達範囲ではなく、拘束力のある数値です。
下の3つの列は、部分を分離しています。到達範囲は、ハードルールが勝者を昇格させることができる上位スコアからの距離です。代替バンドは、表示セットがランキングリストのどこまで広がるかです。表示ギャップは、表示されている候補の最大スコアギャップです。プルーニングをオフにしたエンジンでこれらすべてを測定しました。
| コーパス | 到達範囲 | 代替バンド | 表示ギャップ |
|---|---|---|---|
| オラクル(実) | 1.283 | 1.443 | 1.599 |
| 一般(実) | 1.429 | 1.443 | 1.599 |
| 密な7〜12(敵対的) | 0.484 | 2.858 | 2.858 |
クリーンなテンプレートフィットがない密な8ノート以上のボイシングはスコアを圧縮し、マージンを安全に保つと予想していました。その到達範囲の半分は正しいです。スコアが圧縮されるにつれて1.28から0.48に縮小します。しかし、到達範囲は拘束力のある項ではありません。代替バンドは反対方向に移動します。なぜなら、より多くの候補とより多くのハードルールサイクルにより、線形化はより深い読み方を上に引き上げることができるため、表示ギャップは密なクラスターで2.858に増加するからです。
マルチシード敵対的スイープ(5,000以上の密なボイシング、サイズ7〜12)は、天井を2.858(8ノートクラスター)に維持し、2.5を超えるボイシングは4つだけでした。パフォーマンスはマージン全体でほぼフラットでした。オラクルコーパスは、マージン2.0で約10候補、3.0で15候補、4.0で20候補を保持しており、約86候補のベースラインと比較してn²ペアの94%以上の削減でした。速度は数を選びませんでした。正確さが選びました。私たちは3.0を採用しました。これは2.858の敵対的上限をクリアし、3つのコーパスすべてで表示されるすべての読み方を保持し、ミュージシャンが見るものを何も変更しません。
ゴールデンフェイラーのチェック
プルーニングは、正確な期待出力を固定するゴールデンテストの3つを壊しました。「順序は契約ではない」に頼る前に、それらの3つの変更が音楽的に意味のあるものではなく、恣意的なものであったことを確認しました。これは、命名問題と同様に、外部参照とクロスチェックしました。
壊れた各ケースは同じ形状でした。#1ピックは変更されず、シャッフルは同じスコアでの代替案の間でした。これらは同じ音を異なる方法で綴るものでした(たとえば、A♭7♯5♯11対G♯7♭5♭13)。ルートノートの後続処理によってのみ分離されていました。それらの間には音楽的に正しい順序はありません。したがって、1つを固定することは過剰指定でした。ソースでゴールデンを緩和しました。ケースバイケースではなく、期待される代替案のアサーションは順序なしの包含チェックになり、期待されるすべての代替案は表示される必要がありますが、その順序は自由です。
ロックイン
境界は経験的なものであるため、マージンを正直に保つために2つのガードを記述しました。
candidatesRankedカウンターにより、プルーニングは決定論的なベンチマーク信号になります。プルーニングは生成後に実行されるため、生成は変更されません。このカウンターがないと、これまでに行った最大のアルゴリズム変更は、ノイズの多い時間でのみ表示されます。オラクルコーパスでは11,983から2,120に低下します。- ガードテストはマージンを無限大に引き上げて非プルーニングランキングを回復し、オラクルコーパスと密なスイープ全体で表示ギャップを測定し、それがプロダクションマージンに達した場合は失敗します。将来のスコアリングまたはランキングの変更がギャップを3.0以上に広げた場合、CIはサイレントに代替案をドロップするのではなく失敗します。
結果
#1ピックと表示される代替案のセットは、両方の実コーパス全体で変更されませんでした。6つのオラクルケースと7つの一般的なケースのみが、代替案#2以降(明示的に非契約部分)を並べ替えました。キャッシュされていないランキング時間は、オラクルコーパスで86.7%、一般的なプールで91.7%低下しました。分析が保持するメモリは約3.5%減少しました。
これはO(n²)の複雑さを削減しません。明確な勝者がいない密なボイシングは、プルーニングがトップスコアに近い候補をドロップできないため、依然として完全なセットをランク付けします。それは、一般的なケースと敵対的なケースが順序付けするために完全なランキングコストを支払っていた、表示不可能な読み取りの長いテールを削除します。
まとめ
この作業で最も高価な制約は、私たち自身が課したもので、決して明言しなかったものです。バイト単位で同一の出力。その制約の下では、安全な最適化は定数倍のみでした。10倍の勝利は、より巧妙なアルゴリズムから来たものではありませんでした。それは、制約と製品が約束するものを比較することから来ました。
ゲートマスクとペアごとの高速パスは依然としてエンジンにあり、依然として証明可能な同一であり、依然としてその約30%を稼いでいます。しかし、ヘッドラインの数字は、アプリが実際には必要としない保証を削除することから来ました。
自分でスピードを体験してください。
WhatChordは、オンデバイスでリアルタイムにコードを識別します。iOSおよびAndroidで無料、サブスクリプションなし、広告なし。
[画像: Download on the App Store][画像: Get it on Google Play]
インストールしたくないですか?ブラウザでコードを識別してみる →