永続データ構造 📖 Wikipedia

永続データ構造（えいぞくデータこうぞう、英: persistent data structure）は、変更される際に変更前のバージョンを常に保持するデータ構造である。このようなデータ構造は、更新の際に元のデータ構造を書き換えるのではなく、新たなデータ構造を生成すると考えられ、イミュータブルなデータ構造の構築に利用可能である。

データ構造としては、それよりずっと前から使われているが、persistent という呼び方は1986年に Driscoll 等が命名した。^[1]

データ構造は下記のように分類されている^[1]。

短命（ephemeral）

永続的でないデータ構造。手続き型プログラミング言語で標準のデータ構造。

部分永続的・半永続的（partially persistent）

全バージョンにアクセス可能で、最新版だけが変更可能なデータ構造。

完全永続的・全永続的（fully persistent）

全バージョンにアクセスも更新も可能なデータ構造。

融合永続的（confluently persistent）

最新版以外の2つのバージョンから新たなバージョンを作成/マージする操作があるデータ構造。

永続データ構造は特に関数型プログラミング言語や論理プログラミング言語でよく使われている。純粋関数型プログラミングでは全てのデータが不変で完全永続的である。

永続性は単に変更のたびにデータ全体をコピーすることでも達成できるが、多くの操作はデータ構造のほんの一部しか変更しないので、時間と領域の効率が悪い。より良い手法は、木構造などの連結構造を使ってバージョン間の類似性を表す方法である。しかし、バージョンが増えるにつれてバージョン間でどの部分が共通なのかを判断することが難しくなり、古いバージョンを捨てられるのが望ましい場合も多いため、ガベージコレクションが可能な環境が必要となる。

赤黒木やキューのような多くの参照ベースのデータ構造は、容易に永続的にすることができる。

片方向連結リストや木などの循環参照のない連結構造（有向非巡回グラフ）を使用するのが基本である^[1]。

最も単純な永続データ構造は片方向連結リストである（リスト上の次のオブジェクトへの参照のある単純なリスト）。このようなリストの2番目以降の要素の尾部を共有し、変更部分だけを先頭のノードとして新たに追加することで永続性を実現できる。尾部がコピーされることはなく、新しいリストと古いリストで共有される。尾部の内容が不変であれば、この共有は振る舞いとして現れない。

片方向連結リストを組み合わせると木構造を表現でき、木構造が表現できるとソースコードが表現できるので、1960年のオリジナルのLISPではこれを基本構造に採用した。

スタックは片方向連結リストで作成できる。

キューは両端キュー（Deque: Doble Ended Queue）が最も簡単な実装方法で、Scala^[2]の標準ライブラリで採用されている。inとoutの2つの片方向連結リストを用意し、キューへの挿入はinに追加し、キューからの取り出しはoutから取り出すのだが、outが空の場合は、inを反転させて、outにする。キューへの挿入はO(1)で、キューからの取り出しは最悪計算量はO(n)だが、ならし計算量はO(1)である。

Clojureの標準ライブラリはバッチキューを使用しており、両端キューとほぼ同じだが、inの方は片方向連結リストではなく、動的配列（Vector）を使用している^[3]。

連想配列や集合は、トライ木などにより実装できる。ScalaやClojureでは、Scalaを開発しているスイス連邦工科大学ローザンヌ校に所属していた Phil Bagwell が2001年^[4]に開発した hash array mapped trie で実装していたが、その後、より高速な compressed hash-array mapped prefix-tree を2015年に開発し切り替えた^[5][6]。

.NET の ImmutableDictionary は平衡二分探索木のAVL木で実装されている。^[7]

ソート済み連想配列（SortedMap）やソート済み集合（SortedSet）は、Scala^[8]やClojure^[9]の標準ライブラリでは1972年にルドルフ・ベイヤーが発表した赤黒木で実装されている。

固定長配列は木で作成できる。

動的配列（Vector）は、Scala^[10]やClojure^[11]の標準ライブラリでは32分木を採用している。Scala 2.8のものは Phil Bagwell が設計したもので^[12]、Scala 2.13.2より radix-balanced finger tree の32分木となっている^[13]。要素の取得の計算量はO(log₃₂ n)で、要素の書き換えの計算量はO(32 log₃₂ n)ではあるものの、対数の底が32と大きいため、要素数が2³⁰個であっても5ホップで要素にたどり着けるので、要素の読み書きが事実上定数時間だとScalaのドキュメントには書かれている^[14]。この方法は、先頭や末尾への要素の追加も事実上定数時間のO(32 log₃₂ n)で可能なため^[14]、双方向キューとしても利用できる。双方向キューは銀行家のキューの方法でも実装可能。

Scalaを開発しているスイス連邦工科大学ローザンヌ校に所属していた Phil Bagwell は、2002年に VList^[15] を発表している^[16]。そして、Phil Bagwell 等は2011年に relaxed radix balanced tree を発表し、これは、挿入・分割・結合も O(log n) で出来るようにしたものである^{[17][18][19][20]}。

他の実装方法としては、Edward Sitarski が1996年に発表した hashed array tree がある^[21]。hashed array tree は末尾への追加は償却計算量 O(1) だが、先頭への追加は O(n) である。

.NET の ImmutableList は平衡二分探索木のAVL木で実装されている。^[22]

優先度付きキューは、2-3 フィンガーツリーなどで実装できる。

ここでは Python で実装する。

空リストは None で表現する。銀行家のキューで必要とするので reverse も実装する。

from dataclasses import dataclass
from typing import Optional

@dataclass(frozen=True)
class LinkedList:
    first: any
    rest: Optional['LinkedList']

    def reverse(self) -> 'LinkedList':
        def reverse_rest(rev: Optional['LinkedList'], rest: Optional['LinkedList']) -> 'LinkedList':
            return rev if rest is None else reverse_rest(LinkedList(rest.first, rev), rest.rest)
        return reverse_rest(None, self)

片方向連結リストを使用したスタックの利用例。

stack = None
stack = LinkedList(1, stack)
stack = LinkedList(2, stack)
v, stack = stack.first, stack.rest
print(v)  # 2
v, stack = stack.first, stack.rest
print(v)  # 1

銀行家のキューを実装する。

@dataclass(frozen=True)
class BankersQueue:
    in_list: Optional[LinkedList] = None
    out_list: Optional[LinkedList] = None

    def enqueue(self, element: any) -> 'BankersQueue':
        return BankersQueue(LinkedList(element, self.in_list), self.out_list)

    def dequeue(self) -> tuple[any, 'BankersQueue']:
        if self.out_list is None:
            if self.in_list is None:
                raise ValueError("空のキューからはdequeueできません")
            return BankersQueue(None, self.in_list.reverse()).dequeue()
        else:
            return self.out_list.first, BankersQueue(self.in_list, self.out_list.rest)

銀行家のキューの利用例。

queue = BankersQueue()
queue = queue.enqueue(1)
queue = queue.enqueue(2)
v, queue = queue.dequeue()
print(v)  # 1
v, queue = queue.dequeue()
print(v)  # 2

2^m分木で実装する。2⁵分木の場合、配列のインデックスが32ビットなら木の高さは0以上6以下の7通り、64ビットなら0以上12以下の13通りしかないので、木の高さ別に処理を分けてループ展開すると高速化する。例えば、木の高さが1ならば、要素の取得は tree[idx >> 5][idx & 31] となる。

m = 2  # 2**m 分木を作成する。ここでは4分木。
bit_mask = (1 << m) - 1  # 下位 m ビットが1

@dataclass(frozen=True)
class FixedLengthArray:
    tree: list[any]
    height: int  # 木の高さ

    @classmethod
    def of(cls, *elements) -> 'FixedLengthArray':
        length = len(elements)
        height = max(0, ((length - 1).bit_length() - 1) // m)
        def create(s, e, d):  # s から e の範囲で再帰的に部分木を作成
            if d == 0:
                return list(elements[s:e])
            else:
                return [create(i, min(e, i + (1 << d)), d - m) for i in range(s, e, 1 << d)]
        return FixedLengthArray(create(0, length, height * m), height)

    def __getitem__(self, idx: int) -> any:
        def get(tree, d):  # idx の上位 m ビットずつ木を下っていく
            return tree[idx & bit_mask] if d == 0 else get(tree[(idx >> d) & bit_mask], d - m)
        return get(self.tree, self.height * m)

    def update(self, idx: int, v: any) -> 'FixedLengthArray':
        def update_child(tree, d):  # idx の上位 m ビットずつ木を下り差し替える
            tree = tree.copy()  # 浅いコピー
            tree[(idx >> d) & bit_mask] = v if d == 0 else update_child(tree[(idx >> d) & bit_mask], d - m)
            return tree
        return FixedLengthArray(update_child(self.tree, self.height * m), self.height)

上記の固定長配列の利用例。

ary = FixedLengthArray.of(0, 1, 2, 3, 4, 5)
ary = ary.update(4, 10)
print(ary[4])

• 永続性 (計算機科学)
• ナビゲーショナルデータベース

• Driscoll, J R; Sarnak, N; Sleator, D D; Tarjan, R E (1986). “Making data structures persistent”. Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (New York, NY, USA: Association for Computing Machinery): 109–121. doi:10.1145/12130.12142. ISBN 0897911938. https://doi.org/10.1145/12130.12142. 
• Kaplan, Haim (2001). Persistent data structures. ISBN 978-1584884354. https://www.cs.tau.ac.il/~haimk/papers/persistent-survey.ps. 
• Chuang, Tyng-Ruey (1992). Krieg-Brückner, Bernd. ed. “Fully persistent arrays for efficient incremental updates and voluminous reads”. ESOP '92 (Springer Berlin Heidelberg): 110–129. ISBN 978-3-540-46803-5. https://link.springer.com/chapter/10.1007/3-540-55253-7_7.