変更履歴を保存するデータ構造に関するメモ(定義とか)

永続データ構造とは

永続データ構造 - Wikipedia

• 変更履歴(バージョン)を記録するデータ構造．

本記事について

• 永続データ構造の性質について取り上げたい．

Stack

Stackとは

• 次のようなメソッドを持つデータ構造

struct Stack {
    using T = int;
    vector<T> data;

    Stack(){}

    void push(T val) {
        data.push_back(val);
    }

    void pop() {
        data.pop_back();
    }

    T top() const {
        return data.back();
    }

    int size() const {
        return data.size();
    }
};

永続化しよう

• 永続データ構造とは、変更される際に変更前のバージョンを常に保持するデータ構造なので，愚直に前の状態を保存すれば良い．
• 永続データ構造の定義通りにコードを書けば，次のようになる

struct PersistentStack {
    using T = Stack::T;

    vector<const Stack> stacks;

    PersistentStack() {
        stacks.emplace_back();
    }

    void push(T val) {
        Stack s = stacks.back(); // 最後のバージョンをコピー
        s.push(val);
        stacks.push_back(s);
    }

    void pop() {
        Stack s = stacks.back(); // 最後のバージョンをコピー
        s.pop();
        stacks.push_back(s);
    }

    T top() const {
        return stacks.back().top();
    }

    int size() const {
        return stacks.back().size();
    }

    // index-1番目に新しいバージョンを取得する．最新バージョンは0．
    const Stack& get_version(int index) {
        int n = stacks.size();
        return stacks[n - index - 1];
    }

    // index回前のバージョンに戻す．
    void rollback(int index) {
        stacks.push_back(get_version(index));
    }
};

本当に永続化出来ているか？

• 最新版を変更可能
  • push，popで変更できる．
• 全バージョンにアクセス可能
  • get_versionより，任意の過去のバージョンのStackにアクセス可能である．(用語を間違えて理解しているかも？)
• 全バージョンに更新可能
  • rollbackより，任意の過去のバージョンのStackに書き換えることが出来る．

全永続的．

高速化

• このコードには高速化の余地がある．例えば，vector<const Stack> stacks ．差分だけ保持することで，空間計算量・時間計算量を削減することが出来る．

• 高速化については別記事で．

• 纏めた状態ではないもの

github.com