永続データ構造

永続データ構造とは

永続データ構造（Persistent Data Structure）は、データが変更される際に、変更前の状態を保持し続けるデータ構造です。これは、データ更新時に元のデータを書き換えるのではなく、新しいデータ構造を生成するという考えに基づいています。この性質から、イミュータブル（不変）なデータ構造を構築するのに役立ちます。

データ構造の概念自体は以前から存在していましたが、「永続的」という用語が使われるようになったのは、1986年にDriscollらによって命名されてからです。

データ構造の分類

永続データ構造は、その永続性のレベルによって、以下の4種類に分類されます。

短命 (Ephemeral)：通常のデータ構造で、変更によって過去の状態は失われます。手続き型プログラミング言語で標準的に使用されるものがこれに該当します。
部分永続的 (Partially Persistent)：すべてのバージョンへのアクセスが可能ですが、更新は最新バージョンのみに限定されます。
完全永続的 (Fully Persistent)：すべてのバージョンへのアクセスと更新が可能です。
融合永続的 (Confluently Persistent)：最新以外の複数のバージョンから新たなバージョンを生成・マージする操作が可能です。

永続データ構造の利用

永続データ構造は、特に関数型プログラミング言語や論理プログラミング言語で広く利用されています。純粋関数型プログラミングでは、全てのデータが不変であり、完全永続的であることが求められます。

実装上の課題

永続性を実現する最も単純な方法は、データ変更のたびにデータ全体をコピーすることですが、これは非効率です。なぜなら、ほとんどの操作はデータ構造の一部しか変更しないからです。より効率的な方法は、木構造などの連結構造を用いて、バージョン間の類似性を表現することです。ただし、バージョンが増えるにつれて、どの部分が共通かを判断するのが難しくなるため、ガベージコレクションが可能な環境が望ましいです。

多くの参照ベースのデータ構造（例えば、赤黒木やキューなど）は、比較的容易に永続化できます。

完全永続データ構造の実装手法

完全永続データ構造の基本的な実装手法は、循環参照のない連結構造（有向非巡回グラフ）を使用することです。以下に具体的な例を挙げます。

片方向連結リスト

最も単純な永続データ構造は、片方向連結リストです。リストの2番目以降の要素の尾部を共有し、変更部分だけを先頭のノードとして追加することで永続性を実現します。尾部がコピーされることはなく、新旧のリストで共有されます。この共有は、尾部の内容が不変であれば問題なく機能します。

片方向連結リストを組み合わせることで木構造を表現でき、さらに木構造を用いてソースコードも表現できるため、初期のLISPではこれを基本構造として採用しました。

スタック

スタックは、片方向連結リストで簡単に実装できます。

キュー

キューの簡単な実装方法としては、銀行家のキューがあります。これは、2つの片方向連結リスト（inとout）を使用し、挿入はinに追加、取り出しはoutから行います。outが空の場合は、inを反転させてoutにします。挿入はO(1)で、取り出しは最悪O(n)ですが、ならし計算量はO(1)です。

Clojureの標準ライブラリでは、銀行家のキューとほぼ同じバッチキューを使用しています。ただし、inには片方向連結リストではなく、動的配列（Vector）を使用しています。

連想配列・集合

連想配列や集合は、トライ木などで実装できます。ScalaやClojureでは、hash array mapped trieが使用されていましたが、現在はより高速なcompressed hash-array mapped prefix-treeに切り替えられています。.NETのImmutableDictionaryは、平衡二分探索木のAVL木で実装されています。

ソート済み連想配列・ソート済み集合

ソート済みの連想配列や集合は、赤黒木で実装されるのが一般的です。

固定長配列

固定長配列は、木構造で表現できます。

動的配列・双方向キュー

動的配列（Vector）は、ScalaやClojureでは32分木を採用しています。要素の取得はO(log32 n)で、書き換えはO(32 log32 n)ですが、対数の底が32と大きいため、要素数が非常に多くても高速にアクセスできます。また、先頭や末尾への追加もほぼ定数時間で可能なため、双方向キューとしても利用できます。双方向キューは、銀行家のキューでも実装可能です。

優先度付きキュー

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

実装例（Python）

ここでは、Pythonでの実装例をいくつか紹介します。

片方向連結リスト

python
def cons(x, xs):
return (x, xs)

def head(xs):
return xs[0]

def tail(xs):
return xs[1]

def reverse(xs):
result = None
while xs:
result = cons(head(xs), result)
xs = tail(xs)
return result

スタック

python
stack = None
stack = cons(1, stack)
stack = cons(2, stack)
print(head(stack)) # Output: 2
stack = tail(stack)
print(head(stack)) # Output: 1

キュー

python
def enqueue(queue, x):
return (queue[0], cons(x, queue[1]))

def dequeue(queue):
if queue[0] is None:
if queue[1] is None:
raise IndexError("dequeue from empty queue")
return (reverse(queue[1]), None), head(reverse(queue[1]))
return (tail(queue[0]), queue[1]), head(queue[0])

queue = (None, None)
queue = enqueue(queue, 1)
queue = enqueue(queue, 2)

queue, value = dequeue(queue)
print(value) # Output: 1
queue, value = dequeue(queue)
print(value) # Output: 2

固定長配列（2分木）

python
def make_array(size, init):
height = (size-1).bit_length()
if height == 0:
return [init for _ in range(size)]

tree = [None] (1 << height)
for i in range(len(tree)):
if i2 < size:
tree[i] = [init,init]

return tree

def get_element(tree,index):
height = (len(tree) - 1).bit_length()
if height == 0:
return tree[index]

node = tree
for i in range(height,0,-1):
node = node[ (index >> (i-1))&1 ]
return node

array = make_array(8,0)
print(get_element(array,5))
array[2][1] = 10
print(get_element(array,5))

まとめ

永続データ構造は、データの不変性を保証し、関数型プログラミングにおいて重要な役割を果たします。効率的な実装には、連結構造や木構造が利用され、様々な種類のデータ構造を永続化する手法が存在します。これらの実装例は、永続データ構造の理解を深めるのに役立つでしょう。

参考文献

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.
Kaplan, Haim (2001). Persistent data structures. ISBN 978-1584884354.
* Chuang, Tyng-Ruey (1992). “Fully persistent arrays for efficient incremental updates and voluminous reads”. ESOP '92 (Springer Berlin Heidelberg): 110–129.

もう一度検索

永続データ構造