実装コラム 永続文字列
前置き（ほぼ余談）
2012 年の JOI 春合宿の問題「コピー＆ペースト」は、文字列の任意区間のコピーペーストを高速に処理することを要求します。
https://atcoder.jp/contests/joisc2012/tasks/joisc2012_copypaste
この問題を解くには、まず文字列を永続化することで、切り取った部分を別の部分に貼り付ける操作を可能にしなければなりません。もちろん、列の自由なアクセス・分割・連結には平衡二分探索木が必要です。よって、この問題は永続化された平衡二分探索木で解くことになります。
ここで難しいのが、問題全体ではノードの生成回数が非常に多く、メモリ確保が非常にたくさん起こることで実行時間がかさむことです。この問題では $1$ つの文字列のみを保持しながら、長さの上限も保証されつつ操作を行う問題ですから、大きなメモリプールを持って定期的にガベージコレクションあるいは再構築を作動させれば、比較的簡単に処理できます。しかし実際は他のデータ構造が使用するメモリも必要で、さらに多くのバージョンを保持するため、「十分大きいメモリプールを持つこと」は適切ではありません。やはりメモリを動的に確保したいものです。
メモリ使用量を減らすことくらいはできないでしょうか？
本編
末端が $8$ bits の要素であるような永続平衡二分探索木のメモリ効率を上げたいです。 $3$ つのアプローチで効率化します。
- 葉ノードに複数要素を詰め込む
- 赤黒木の代わりに AVL 木を使用する
- 継承を用いて、不要な情報を持たないようにする
まず、葉ノードに複数の要素を詰め込みます。各要素は $8$ bits ですから、コピーのコストが非常に小さいことが保証されています。また、 $64$ bits は同時に操作できますから、例えば末端に $32$ 個の要素を入れても、それなりに高速に処理できます。そもそも探索の計算量が $\log n$ オーダーなので、末端 $1$ 回が多少大きくても問題になりません。
問題は split/merge を適切に処理することです。次の不変条件を持つことで処理します。
- 最大容量を $2D$ とする。その木が $2$ つ以上の葉ノードを持つ場合、各葉ノードは少なくとも $D$ 個の要素を持つ。
二分木の split/merge が葉で起こる場合のみの変更で、この条件を保つことができます。
次に、 AVL 木を使用します。「コピー＆ペースト」では赤黒木が解説されていますが、赤黒木が回転しない場合でも色の変更により途中でノードが余分に複製されます。比べて AVL 木は回転以外で余分にノードを変更せず、生成するノードの個数が少し抑えられます。
最後に、継承を用いてメモリ使用量を最適化します。
struct Node{
u32 state;
u32 refcnt;
size_t size;
};
struct MidNode : public Node {
Np l;
Np r;
};
struct LeafNode : public Node {
Elem a;
};
葉は文字列の情報を持ちますが、子は持たないのでポインタは不要です。それに対して中間ノードは、左右の子のポインタが必要ですが、文字列の情報が不要です。現在のノードがどちらであるかを Node::state に記録し、必要に応じて場合分け、キャストすることで、メモリ使用量を抑えます。
例えば構造体を new するごとに $8$ バイト余分に消費すると仮定します。二分木を与えられた文字列を初期化したときは、 MidNode と LeafNode が 1:1 で生成され、 LeafNode には $32$ バイト入りますから、文字列 $1$ バイトあたり $(8+32+8+48)/32=3$ バイト消費すると考えられます。また、文字列に対する基本的な操作 $1$ 回（ ex. split ）あたり MidNode を $20$ 個、 LeafNode を $2$ 個生成するとしたとき、全体で $(8+32)\times 20+(8+48)\times 2\approx 900$ バイトを消費すると考えられます。