Clojureの永続データ構造
Clojure Advent Calendar 2018 の19日目の記事として、Clojureの永続データ構造について書いている。
永続データ構造とはデータの変更履歴を保存しているデータ構造である。データ構造に対して追加、更新、削除などを行った場合、もとのデータ構造を破壊せず、新しいデータ構造を返す。
Clojureとは異なり、変更前のデータ構造を破壊する例を以下に示す。0から8までの整数を持つfooを用意し、6番目の値を9に更新すると、元のfooが破壊されている。（下のようなコードはfooが破壊されることを期待して書かれるだろう。）
irb(main):001:0> foo = [0, 1, 2, 3, 4, 5, 6, 7, 8]
=> [0, 1, 2, 3, 4, 5, 6, 7, 8]
irb(main):002:0> foo[6] = 9
=> 9
irb(main):003:0> foo
=> [0, 1, 2, 3, 4, 5, 9, 7, 8] # fooが変更されているこの例がRubyである必要はなく、ミュータブルなデータ構造を一般的に使用する言語なら何でもよい。※ 1
次は変更前のデータ構造を破壊しない例をClojureで示す。上のRubyを使用した例と同じく、0から8までの整数を持つfooを用意し、6番目の値を9に更新する。しかし、元のfooは破壊されていない。
user=> (def foo [0 1 2 3 4 5 6 7 8])
#'user/foo
user=> (assoc foo 6 9)
[0 1 2 3 4 5 9 7 8]
user=> (println foo)
[0 1 2 3 4 5 6 7 8] ; fooは元のまま
nilfooが破壊されないメリットとして、fooが2箇所以上から参照されている場合でも、fooに対して追加、更新、削除などを行った影響を考慮しなくてよくなるということが挙げられる。
Clojureは元のデータから一部を変更したコピーを作成しているのではなく、更新前後のバージョンのデータ構造を共有して、永続性とイミュータビリティを実現している。可能な限りデータ構造を共有することで、メモリ消費量が抑えられている。
いかにして更新前後のバージョンのデータ構造を共有しているかを木構造を用いて示す。Clojureのベクタの木構造は以下の特徴を持つ。
- Leaf nodeのみにベクタの要素を持つ
- 左から順に格納する
- 深さが均一である
- ベクタの長さを持つ
ここまでが元のfooで状態である。6番目の値を9に更新すると以下のような木構造になる。オレンジの部分が追加した箇所で、白い部分は更新前後のバージョンで共有している箇所である。ベクタの要素へのパスをコピーしており、ベクタの要素自体のコピーは最小限に抑えられている。
上の２つの図では簡略化のために、nodeごとに２要素しかないように書いたが、実際にはnodeごとに32要素を持つ浅い木構造になっている。ベクタへの追加や削除などのパターンはUnderstanding Clojure’s Persistent Vectors, pt. 1を参照するとよい。
また、保存している変更履歴のどのバージョンに対する操作でも性能に差がないことが保証されているようである。
※１ fooをコピーし、新しいオブジェクトを生成すれば、Rubyでも永続性を担保できる。
