構造を共有して過去の版を保存・復元する

概要

過去の状態へ戻るたびに配列や木を丸ごとコピーすると、保存する回数と状態の大きさの積だけ費用がかかる。更新で変わる箇所に注目すれば、変更前の値を記録して巻き戻す方法と、変更しない部分を共有して版を残す方法を選べる。

考え方

例えば、2要素の配列の状態を A=(3,7)A=(3,7) とする。添字は0始まりとし、Aの先頭を4へ代入した状態を B=(4,7)B=(4,7)、元のAの2番目を5へ代入した状態を C=(3,5)C=(3,5) とする。BとCは、同じAから分岐した別の状態である。Bの処理後にCを調べるには、Bの4を引き継がず、Aの3を出発点にする必要がある。Bのまま2番目を5にすると (4,5)(4,5) になり、別の枝の変更が混ざってしまう。

rollback:一つの状態を巻き戻して使う

rollback(巻き戻し)では、作業用の配列を一つだけ持ち、値を書き換える前に「変更した場所と旧値」を履歴スタックへ積む。戻りたい時点の履歴の長さを保存したものがcheckpointである。Aに到達したときの履歴が空なら、checkpointは h = 0 になる。

手順配列履歴
Aで h = 0 を保存(3,7)(3,7)空
Bへ:先頭を4に更新(4,7)(4,7)(0,3)
Aへ:旧値3を復元(3,7)(3,7)空
Cへ:2番目を5に更新(3,5)(3,5)(1,7)

(0,3) は「添字0の旧値が3」という記録である。Bから戻るときは、履歴の長さが h になるまで末尾の記録を取り出し、旧値を代入する。Cの処理後も同じ h まで戻せばAになる。checkpointは配列のコピーでも版の識別番号でもなく、現在の履歴のどこまで戻すかを表す。

この取消しに、更新の数学的な逆演算は要らない。4への代入だけから以前の値は求められないが、旧値3を記録すれば戻せる。複数の書換えも、最後の書換えから逆順に旧値へ戻すことで、一つずつ更新直前の状態を復元できる。値だけでなく、更新に伴って変わる個数や集計値も記録し、checkpoint以後の変更をすべて戻すことが条件になる。

Bの状態そのものは巻き戻し後には残らない。それでも、依存する状態を木として表し、子へ入る前にcheckpointを保存して、子から戻るたびに復元すれば、深さ優先探索(DFS)でA→B→A→Cと分岐を巡れる。問い合わせを先読みしてこの順に並べ替えられるオフライン処理では、分岐があってもrollbackを使える。履歴の長さだけを保存しても、取り出して捨てたBの状態へ直ちに移れるわけではない。

永続化:版の入口を残して切り替える

永続化(persistence)では、過去の版を読むための節点を残し、更新後の版と変わらない部分を共有する。各版を参照する入口の節点番号やポインタをrootと呼ぶ。ここでは配列を表す木の根を入口にする。

2要素の配列を、根と二つの葉で表してみる。Aのroot rA は、値3の葉と値7の葉を参照する。Bを作るときは、値4の新しい葉と、それを参照する新しい根 rB を作り、値7の葉はAと共有する。Cも rA を出発点にして、値5の新しい葉と根 rC を作り、先頭の値3の葉をAと共有する。

保存するroot先頭の葉2番目の葉
rA値3の葉値7の葉
rB新しい値4の葉Aと同じ値7の葉
rCAと同じ値3の葉新しい値5の葉

現在の入口を rA→rB→rA→rC と切り替えれば、同じA→B→A→Cをたどれる。rollbackと違い、Bの変更を取り消す必要はなく、保存した rB から再びBを読める。新しい根・葉の初期化を終えたら、保存済みrootからたどれる節点には書き込まない。この条件によりAの内容はB・Cの作成後も変わらず、Bの内容もCの作成に影響されない。例えばCを作る際に、AとBで共有している値7の葉そのものを5へ書き換えると、AとBの2番目まで5に変わってしまう。

この例でrootは各版の木の根だが、入口の選び方は構造による。ABC273 Eの公式解説では、列を根から末尾までの道で表し、保存するのは末尾の節点番号である。版を選ぶ入口と、全履歴を表す木の共通の根を区別して読むとよい。

成立条件と計算量

選ぶときは、まず「状態を訪れる順序を自分で決められるか」「過去の版を同時に参照する必要があるか」を確認する。

  • DFSの入退場に合わせて状態を使い、一つの枝を終えてから兄弟へ進めるならrollbackを考える。各更新の変更箇所を記録できれば、代入のような逆演算のない更新も扱える。具体的な変更記録や時間区間のDFSへの応用は、rollback・DFS入退場の状態復元へ進む。
  • 指定された順に任意の保存版を読み、そこから新しい版を作りたいなら永続化を考える。変更箇所を少数の新節点で表し、共有部分を不変に保てることを確認する。木の更新経路を複製する手順は、永続data structure・structural sharingへ進む。

rollbackのcheckpoint取得は履歴の長さを読むだけなので O(1)O(1)。旧値の記録・復元が一件 O(1)O(1) なら、kk 件を戻す時間は O(k)O(k) になる。全処理で積む記録の総数を RR とすると、各記録は高々一度取り出すため、記録の追加・取出しは合計 O(R)O(R) である。これに初期化、元の更新・問い合わせ・探索の費用を加える。作業用の状態の領域を SS、同時にスタックへ残る記録数の最大値を HH とすると、状態と変更履歴は O(S+H)O(S+H) 空間で済み、終わった枝の記録は再利用できる。入力・答え・探索用のスタックなどの領域は別途数える。

永続化では、既にある版のrootだけを別の保存先へコピーする操作は O(1)O(1) である。更新して新しい版を作る費用まで定数になるわけではない。初期構造の節点数を SS、更新 ii で作る節点数を cic_i、保持するroot数を VV とすると、全節点を残す実装の領域は次のようになる。

O ⁣(S+V+∑ici)O\!\left(S+V+\sum_i c_i\right)

この領域には、現在選んでいないBなどの過去の版も含まれる。同じ初期版を表すrootを多数用意しても、初期構造は一度だけ構築し、rootの保存先だけを増やせばよい。

例えば位置数 MM の永続Segment Treeなら、要約の合成が定数時間のとき、初期構築は O(M)O(M)、一点更新で作る節点は根から葉までの O(1+log⁡M)O(1+\log M) 個である。更新 UU 回・保存root VV 個の領域は O(M+U(1+log⁡M)+V)O(M+U(1+\log M)+V)、一点更新と区間集約は一回 O(1+log⁡M)O(1+\log M) となる。M=1M=1 でも葉を一つ作るので、式には1を含めている。全体時間には初期構築、各更新・問い合わせ、rootの保存先の初期化と一回 O(1)O(1) の保存・切替をすべて数える。rollbackの「今の探索経路に残る履歴」と、永続化の「保存する全版に必要な節点・root」を分けて、時間と空間の両方を見積もる。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

前提・学習成果・出典

導入対象の目安: 青色(1600–1999)。過去へ戻す操作と過去の版を残す操作の違いを理解する入口。

対象色の読み方は本書の読み方を参照してください。

概念上の親: データ構造と問い合わせ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-persistence-rollback

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • 区間更新作用の遅延評価。

根拠