あなたの庭に永続データ構造を飾りませんか？

2019/02/06 永続 Stack のやや丁寧な実装例を追加しました

概要

あなたのライブラリに新しい彩りを与える永続データ構造の紹介です。

永続データ構造とは

永続データ構造とは、普段のデータ構造で更新をするときに更新前の状態のデータも保存しておけるデータ構造です。 唐突ですが、数列 X に対するクエリを処理する問題を考えてみてください。

A : X[i] に c を加える
B : "t 番目のクエリ直後の" X[l]...X[r] の和を出力

クエリBをソートすればいつもの Segment Tree で解くことが出来ます。 ではこれがオンラインクエリだったらどうでしょうか。 これは Segment Tree では容易には解くことが出来ません。
こういった「過去の状態が必要になる」状況で永続データ構造は効率的です。

永続 Stack

具体的に、基本的なデータ構造である Stack の永続化をしてみましょう。整数を要素とする Stack は次の 3 種類のクエリを処理します。

int top() : 先頭要素にアクセス
void push(int x) : x を追加
void pop() : 先頭要素を削除

これを永続化すると以下のようになります。

int top() : 先頭要素にアクセス
Stack push(int x) : x を追加した結果得られる Stack を作成
Stack pop() : 先頭要素を削除した結果得られる Stack を作成
※ push, pop について元のデータは書き換えられない

計算量を考慮しなければ、毎回 Stack の中身を全部コピーすればこれらのクエリは実現可能です。 しかしよく考えると、末尾のほとんどの要素は一切変化していません。これを利用して効率的に、具体的には計算量を O(1) のままで処理できるのです！

具体的にはどうすればよいのでしょうか。一般的に Stack は配列で実装すると思いますが、実は配列は永続化と相性が悪いので単方向連結リストを使います。 すると永続 Stack はリストの先頭ノードへのポインタそのものになります！各関数の処理を確認しましょう。

top : ポインタから先頭ノードの値を読む
push : 追加する値とポインタから新しく作成したノードへのポインタを持つ Stack を作成
pop : ポインタから先頭ノードを読み、次のノードへのポインタを持つ Stack を作成

以上をコードにまとめると以下のようになります。(行儀や効率やらを投げ捨てています)

#include <iostream>

struct Node {
    int value;
    Node *next;
};

struct Stack {
    Node *list;

    int top() { return list->value; }
    Stack push(int x) { return Stack({ new Node({x, list}) }); }
    Stack pop() { return Stack({ list->next }); }
};

int main() {

    Stack st0;
    Stack st1 = st0.push(1);
    Stack st2 = st1.push(2);
    Stack st3 = st2.pop();

    std::cout << st1.top() << " " << st2.top() << " " << st3.top(); //1 2 1

    return 0;
}

st1, st2 は push や pop がされていますが、その後でも top で先頭要素を取得可能なことがお分かりいただけるでしょうか。これこそが永続たる所以です。

実装例

上記の実装はメモリの解法処理を行っていないためメモリリークを起こすあまりよろしくない実装例です。 もう少しちゃんとした実装は以下を参考にしてください。

github.com

まとめ

永続データ構造は過去の状態の保存が可能で、様々なデータ構造に対してその永続版が提案されています。現在コンテストでお目にかかることは稀ですが、その理論は大変美しく技巧的です。データ構造やライブラリ整備が好きな人は是非調べてみてください。