第1章 bmsonからBMSへの変換における離散格子量子化と彩色パッキング数理¶

本章では、オブジェクト指向型かつ制限のないタイムライン構造を持つ bmson フォーマットから、古典的でありながら強固な格子の制約構造を持つ BMS フォーマットへのダウンコンバートを実行する際、時間軸およびオブジェクト配置において発生する誤差を数学的に最小化する最適化理論を提案する。

Note

本章における主要な略称・用語 - GC: ガベージコレクション (Garbage Collection) - LCM: 最小公倍数 (Least Common Multiple) - Sweep-Line: 走査線アルゴリズム

1.1 変換問題の数理的定式化と形式の定義¶

bmsonとBMSは、データを配置する空間の数学的定義が根底から異なる。

定義 1.1 (bmson のデータ空間)¶

bmsonにおける音符イベントの集合を \(E_{\text{bmson}} = \{ e_1, e_2, \dots, e_M \}\) とする。各イベント \(e_i\) はタプル \((p_i, k_i, w_i)\) で構成される。ここで \(p_i \in [0, 1)\) は小節内の相対時間を表す連続な実数座標（位相）、\(k_i \in \mathbb{N}\) はキー（チャンネル/レーン制限のない任意のID）、\(w_i \in \mathcal{W}\) は対応する音源データ（ファイル名）である。bmsonにおいては、同一タイミングでの多重発音に物理的な制約が存在しない。

定義 1.2 (BMS のデータ空間)¶

対して、BMSにおけるデータ配置空間は、小節ごとの有限離散格子として定義される。 BMS上の任意の音符オブジェクトは、ある整数分割数（解像度） \(D \in \mathbb{N}\) により、位置 \(s \in \{0, 1, \dots, D - 1\}\) の格子点 \(s / D\) に射影されなければならない。さらに、BMSのチャンネル \(C \in \mathcal{C}\) （総数は最大 1296）は、同一の格子点 \((m, s)\) において高々1つの音源オブジェクトしか保持できないという排他制約を持つ。

\[\forall c \in \mathcal{C}, \ \text{格子点 } (m, s) \text{ において配置可能な } e \in E_{\text{BMS}} \text{ は高々 } 1 \text{ 個} \quad \cdots (1.1)\]

1.2 課題：量子化ノイズとパッキングにおける多重衝突 (Why)¶

この連続空間から離散格子空間へのダウンコンバートを素朴に実行すると、以下の2大ボトルネックによって譜面データの完全性が破壊される。

1.2.1 課題①：格子点量子化に伴う量子化誤差¶

bmsonでの発音タイミング \(p_i\) を、BMSの分割数 \(D\) の格子に丸める際、必ず以下の量子化誤差 \(e_{\text{quant}}\) が発生する。

\[e_{\text{quant}} = \min_{s \in \{0, \dots, D\}} \left| p_i - \frac{s}{D} \right| \quad \cdots (1.2)\]

固定値 \(D=192\) などへ一律に丸めると、三拍子などの非2のべき乗ビートにおいて誤差が蓄積し、聴覚上でミリ秒単位のハネやモタりといったプレイアビリティの破壊が生じる。これを防ぐには、誤差 \(\epsilon\) を満たす「最適な最小分割数 \(D^*\)」を動的に決定しなければならない。

1.2.2 課題②：オブジェクトのアロケーション爆発とGCストール¶

多重発音のチャンネル競合を回避するためには、「ノートが現在どのチャンネルを占有しているか」を追跡する状態管理が必要となる。素朴な実装では、ノートの処理ごとに List<ActiveNote> のようなオブジェクトをヒープ上に動的なインスタンス生成し、走査のたびに破棄することになる。しかし、総ノート数 \(M > 10^5\) の巨大譜面においてこの操作を行うと、数千万のメモリアロケーションとGCが誘発され、メモリ爆発と致命的な実行ストールを引き起こす。

1.3 定理の提示と数学的証明 (Proof)¶

Important

最適分割数 \(D^*\) の定数時間探索 各小節におけるノートの相対位置集合を \(P = \{ p_1, p_2, \dots, p_k \} \subset [0, 1)\) とする。許容誤差を \(\epsilon > 0\)（例えば \(10^{-6}\)）としたとき、最適分割数 \(D^*\) は以下の最適化問題の解である。

\[D^* = \min \left\{ D \in \mathcal{D}_{\text{valid}} \ \middle| \ \max_{p \in P} \left( \min_{s} \left| p - \frac{s}{D} \right| \right) \le \epsilon \right\} \quad \cdots (1.3)\]

Note

導出と証明

\(\mathcal{D}_{\text{valid}}\) はBMS規格で許容される分割数の有限集合（通常は \(1 \le D \le 192\) など）である。集合 \(P\) の要素数 \(k\) に対して、特定の \(D\) が条件を満たすかの判定は \(O(k)\) で可能である。素朴な探索では全 \(D\) を試すため \(O(|\mathcal{D}_{\text{valid}}| \cdot k)\) となるが、実用上は \(p_i\) が有理数 \(q_i / r_i\) として表される音楽理論上の制約に基づく性質を利用する。各 \(p_i\) の既約分数の分母の集合を \(R = \{r_1, \dots, r_k\}\) とすると、最適分割数 \(D^*\) は \(R\) の LCM に一致するか、その倍数となる。よって、ユークリッドの互除法を \(k-1\) 回適用することで、時間計算量 \(O(k \log(\max R))\) という実質的な定数時間で一意に \(D^*\) を導出できる。\(\blacksquare\)

1.3.2 グラフ彩色問題への射影と区間干渉の定義¶

多重発音のチャンネル割当は、離散数学における「区間グラフの彩色問題」に射影される。

各ノート \(i\) の発音区間を、開始時刻 \(t_i\) と波形長 \(L_i\) を用いた半開区間 \(I_i = [t_i, t_i + L_i)\) とする。干渉グラフ \(G = (V, E)\) において、ノート \(v_i, v_j\) に辺が張られる（干渉する）条件は、区間の共通部分が空でないことである。

\[(v_i, v_j) \in E \iff I_i \cap I_j \neq \emptyset \quad \cdots (1.4)\]

このグラフ \(G\) に対し、BMSのチャンネル集合 \(\mathcal{C}\) を用いて彩色数 \(\chi(G)\) を最小化する。区間グラフというトポロジー的性質から、左端 \(t_i\) でソートしたSweep-Line と貪欲法を用いることで、最適彩色が \(O(M \log M)\) で得られることが数学的に保証される。

1.4 実装極限：インデックス構造によるGCゼロ最適化¶

素朴なスイープアルゴリズムが抱える「オブジェクト生成に伴うGCストール（課題2.2.2）」を回避するため、本システムでは動的リストを棄却し、ポインタのような振る舞いをするフラットな1次元配列を用いたインプレース状態管理を採用する。

1.4.1 空間計算量 \(O(|\mathcal{C}|)\) への圧縮¶

チャンネル数 \(|\mathcal{C}|\) はBMSの仕様上、最大1296（\(ZZ_{36}\)）に固定されている。したがって、各チャンネルが「いつ解放されるか（占有終了時刻）」だけを保持する固定長配列を1つ用意し、それをポインタ（インデックス）で直接参照・更新すれば、オブジェクト生成は完全にゼロとなる。

// 【疑似コード】ポインタ（フラット配列）構造を用いた GC-Free 彩色アルゴリズム
public class BmsonToBmsConverter {
    // BMSの最大チャンネル数（36進数「01」〜「ZZ」の1296個）
    private const int MAX_CHANNELS = 1296; 

    public BmsData DownConvert(BmsonData bmson) {
        var bms = new BmsData();

        // O(M log M): ノートの開始時刻でソート
        var sortedEvents = bmson.Notes.OrderBy(n => n.Time).ToArray();

        // 【極限最適化】動的リストを排除し、固定長配列をポインタとして扱う
        // 各チャンネルの「占有終了時刻」のみを記録する。初期値は 0（空き）
        double[] channelEndTimes = new double[MAX_CHANNELS]; 

        for (int i = 0; i < sortedEvents.Length; i++) {
            var ev = sortedEvents[i];
            int assignedChannel = -1;

            // O(|C|): 終了時刻を指す配列を走査し、最若番の空きチャンネルを貪欲に探索
            for (int ch = 1; ch < MAX_CHANNELS; ch++) {
                // 記録されている終了時刻が現在時刻より前なら、そのチャンネルは「空き」
                if (channelEndTimes[ch] <= ev.Time) {
                    assignedChannel = ch;
                    break;
                }
            }

            if (assignedChannel == -1) 
                throw new Exception("BMS Specification Limit Exceeded: チャンネル枯渇");

            // BMSオブジェクトの生成
            bms.AddObject(ev.Measure, ev.Position, assignedChannel, ev.WavId);

            // 【状態更新】該当チャンネルの終了時刻を上書き更新
            channelEndTimes[assignedChannel] = ev.Time + ev.Duration;
        }

        return bms;
    }
}

このアーキテクチャにより、状態管理に必要なメモリ領域は数百バイトの連続した配列空間（L1キャッシュに完全に収まるサイズ）に固定され、空間計算量は動的な \(O(M)\) から絶対的な \(O(|\mathcal{C}|)\) レベルへと圧縮される。メモリアロケーションが完全に排除されたことで、どれほど巨大なbmsonファイル群であっても、ダウンコンバート処理中にGCが発火することは数学的にあり得なくなり、純粋なCPU演算速度の物理的上限に到達する。

1.4.2 メモリ局所性とアーキテクチャ・パターンの数理¶

前述の「ヒープアロケーションを伴うオブジェクト参照」を完全に棄却し、固定長配列に対する「整数インデックス」を擬似的なポインタとして使い回すアーキテクチャは、単なるC#のTipsではなく、ソフトウェア工学における以下の3つの高度なデザインパターンを数学的に融合させた極限の実装である。

Flyweightパターンの極限変形 通常、Flyweightパターンは「共有インスタンスへの参照」を保持してメモリを節約するが、マネージド言語ではその参照ポインタ自体がGCの追跡対象となりオーバーヘッドを生む。本システムでは、実体参照の代わりに「整数インデックス」をハンドルとして状態を配列に外部化することで、GCトラッキングを完全に無効化している。
Array-Backed Object Pool 動的な Queue<T> 等を用いたオブジェクトプールは、コンテナ自体の操作コストを生む。本システムは「BMSのチャンネル上限は1296個に固定されている」という不変の境界条件を利用し、連続成分 double[1296] を直接プールとして扱い、オブジェクトの動的な「生成・破棄」を、配列要素の「定数時間 \(O(1)\) の値上書き」へと射影している。
データ指向設計と Handle パターン オブジェクト指向のようにデータと振る舞いをカプセル化してヒープに散在させると、メモリアクセスの際に深刻なキャッシュミスが発生する。これを防ぐため、データを一次元の連続配列に分割し、プログラムはインデックスだけを持ち回る。これにより、状態遷移に必要なメモリ領域はL1キャッシュのラインに完全に適合し、CPUのメモリスループットが極限まで引き出される。

1.5 参考文献 (References)¶

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.