Immutableなデータ構造について(Stack, Queue)
この記事はデータ構造とアルゴリズム Advent Calendar 2019 - Qiitaの12日目の記事です．
はじめに
唐突にデータ構造を勉強したくなり，怖そうだからという理由で今まで逃げてきた永続データ構造について勉強したものを一部まとめてみました． 本記事の構成はこんな感じです．
- Mutable, Immutableってそもそも何
- 一般的(Mutable)なStackとQueueについて
- Immutable Stackについて
- Immutable Queueについて(前編)
- Immutable Queueについて(中編)
- Immutable Queueについて(後編)
Immutable Stackについてはパッと見つけることができましたが，効率の良いImmutable Queueについては自分のググラビリティが低すぎて見つけることができませんでした． Immutable Queueを考察しているときに，「もっと簡単な構造に落ち着くはずでしょ。。。」という気持ちになったので，そういうものがあれば教えていただけると嬉しいです．
Immutableってそもそも何
Mutable Objectは「可変オブジェクト」という意味で， より直感的な説明をすると変更できるオブジェクトのことを指します． Mutableなオブジェクトに何かしらの操作を加えると，オブジェクト自身が変化をします．
反対に，Immutable Objectはそのまま日本語にすると「不変なオブジェクト」という意味で，変更できないオブジェクトのことを指します． Immutableなオブジェクトに何かしらの操作を加えると，オブジェクト自身は変化をせず，操作を加えた後の新たなオブジェクトを返してくれます． JavaだとStringなどがImmutable Objectとして知られています．
データ構造をImmutableで持つことの大きなメリットは，
- メソッドに渡しても壊されないことが保証されている
- ある時点の操作後の情報を遡って取得できる
ということが挙げられるかと思います(個人的には実プログラミングでは前者が，競技プログラミングでは後者が大きいと考えています)．
Immutableなデータ構造を作る際にまず最初に思いつくのが以下のようなものではないでしょうか
- 注目しているインスタンスのディープコピーを作成する
- ディープコピーしたオブジェクトに操作を反映し、返り値として返す
この実装だと，データ構造が管理しているデータの数をNとすると毎回の操作でO(N)かかってしまい効率が悪いです．
本記事では効率が良いImmutable Stack，Immutable Queueの実装について紹介しますが， その前にMutableなStackとQueueについて簡単に紹介します
一般的(Mutable)なStackとQueueについて
そもそもStackとQueueって何ですか？という方はこちらの記事がとてもわかりやすかったので参考にしてください． qiita.com
上記記事でも紹介されていますが，StackとQueueはListが実装されているならば簡単に実装することができます(どちらもpush,pop共にO(1))．
後のImmutable Queue実装に関わってくることですが，Queueに関してはStackを2つ持つことでも実装ができます．
具体的なアルゴリズムはこちら
- 2つのスタックをそれぞれback，forwardとする(初期値はそれぞれ空のスタックとする)
- push(a)の操作がされたら，backのスタックにaをpushする
- pop()の操作がされた場合，forwardの状況に応じて以下のように場合分けする
- forwardが空の場合: backが空になるまでpop()し，pop()した順番にforwardにpush()する．その後，forwardをpop()したものを返す
- forwardに要素がある場合: forwardをpop()したものを返す
3番目の「forwardが空の場合」で何をやっているかというと，「先入れ後出し」の性質(Stack)を「先入れ先出し」の性質(Queue)へと変化させています．
スタックを2つ持つ実装の時間計算量ですが，反転させる操作が最悪O(N)かかるので，全体でO(N)かかるように見えますが， 各要素は高々1回しか反転操作をされないので，償却時間計算量はO(1)になります． Listを使って実装した場合はpush，popどちらの操作もO(1)になるので，stackを用いたqueue実装のほうが効率は悪くなってしまいますが， Immutable Queueを手軽に実装しようとすると，ここで紹介したような感じの実装になります．
Immutable Stackについて
Immutable Stackの基本的な考え方は，Immutable Stackにpushするオブジェクトはグローバルに共有し， Immutable Stackの各インスタンスは，オブジェクトがどのように連結(接続)しているかを管理します．
具体的な実装方法は先人様のレポジトリを参照くださいmm github.com
動作例はこちら
public class Main { public static main() { ImmutableStack q0 = new ImmutableStack(); ImmutableStack q1 = q0.push(1); // q1は緑 ImmutableStack q2 = q1.push(2); // q2はオレンジ ImmutableStack q3 = q1.push(3); // q3は黄 ImmutableStack q4 = q3.push(4); // q4は紫 ImmutableStack q5 = q2.pop(); // q5は黒 } }
各インスタンスは色付きの枠でオブジェクトの接続情報を管理しているイメージです． 例えばq3(黄)に管理するオブジェクト(4)をpushしてq4(紫)を作成する場合は，q3への参照と管理するオブジェクト 4への参照の2つを持ち，オブジェクト自体は全インスタンスで共有して参照することで，ディープコピーをせずにImmutable Stackを実装できます． (ただし，head()などでオブジェクトへアクセスし，管理しているオブジェクトがMutableな場合はオブジェクトのディープコピーをする必要があります)
こちらのImmutable Stackの時間計算量はpush, pop共にO(1)になっています．StackをImmutableにしても計算量が変わらないのは 個人的に面白いなと思います．
Immutable Queueについて (前編)
Immutable QueueもImmutable Stackと基本的な考え方は同じで，pushするオブジェクトはImmutable Queueの 全インスタンスで共有し，オブジェクトの接続情報を各インスタンスが管理するという形で実装をします．
一般的(Mutable)なStackとQueueについてで紹介しましたが，Mutable QueueはMutable Stackを2本持つことでも実装をすることができました．
なので，Immutable QueueについてもImmutable Stackを2本もつことで実装できます．
アルゴリズムについては一般的(Mutable)なStackとQueueについてで紹介した方法と全く同じなので省略します．
(Immutable Stackの章でリンクを貼らせていただいたレポジトリの中にImmutable Queueの実装もあります)
1回の操作(popやstack)に対し，Mutable Queueの償却時間計算量はO(1)だったので，Immutable Queueの償却時間計算量もO(1)になりそうですが，悪意に満ちた入力が来た場合はImmutable Queueの時間計算量はO(N)になってしまいます．
悪意に満ちた入力例の一例を以下に示します．
各インスタンスは緑の枠で囲まれた部分と，オブジェクト
を参照としているとします．
あるインスタンス
でpop操作が行われると，
一般的(Mutable)なStackとQueueについてで紹介したように反転処理が
走ります．が，オブジェクトの接続情報(順番)は各インスタンス毎に管理されているため，以外のインスタンスがpop操作をする場合は再び反転処理が走ってしまいます．上図の場合，各インスタンス
が全てpop操作を行うと，各pop操作で
回反転処理が起こります．
したがって，ここで紹介したImmutable Queueの時間計算量はpushがO(1), popがO(N)となります．
Immutable Queueについて (中編)
前編で紹介した方法ではpop操作がO(N)となっており，データ構造警察に見つかれば逮捕されてしまいます． O(N)となってしまう原因は，各インスタンスがそれぞれ独立してオブジェクトの接続情報(順番)を保存していることにありました． ならばいっそのこと，オブジェクトの接続情報をグローバルに管理してしまえばこの問題は回避できそうです． より具体的には，接続情報を木構造でグローバルに管理し，各インスタンスはQueueのhead(H)とtail(T)を管理します．
push操作とpop操作は次のような実装します．
- push操作: push操作を行うImmutable Queueのインスタンスをins, pushするオブジェクトをobjとしたとき，objをins.tailの子要素として接続し，(ins.head, objの参照)を返す
- pop操作: pop操作を行うImmutable Queueのインスタンスをinsとしたとき，(ins.headの子要素で，かつins.tailに繋がるオブジェクトへの参照, ins.tail)を返す
具体的な動作例は次のようになります．
(Queueなのでpopをするとheadが移動することに注意してください)
ここで，pop操作の「ins.headの子要素で，かつins.tailに繋がるオブジェクト」を特定する部分がボトルネックとなってきます．接続情報が木構造となっているので，子要素から先祖の要素へは簡単に辿ることができますが，親要素から特定の子孫の要素へ辿るパスを特定することは簡単にはできません．これは，接続の向きが子要素から親要素に向いているので難しいということではなく，子要素は親要素を高々1つしか持たないが，親要素は子要素を複数持つことがあるからです．
したがって，popをするたびにins.tailから親要素を辿っていき，ins.headの次の子要素を特定する必要がありますが，ここで最悪O(N)かかってしまいます．残念!
このままだと計算量の改善ができていませんが，木構造となっているので子要素から親要素へ2冪のインデックスを貼る(ダブリング)と高速に親要素へ辿ることができます．
ダブリングについてはこちらの記事をご参照ください． satanic0258.hatenablog.com
ざっくりと2冪のインデックスを説明すると，各要素について1つ上の親，2つ上の親，4つ上の親，...，2n上の親，...への参照を持っていると，子要素から特定の親要素への遷移がO()でできるというものです．また，新しい要素が挿入された時，その要素へ2冪のインデックスを貼るのもO(
)でできます．
ここまでを実装すると，push・popの時間計算量がO()になりました．pushした時に2冪のインデックスを貼る必要が生じるので，前編で紹介したImmutable Queueと比べるとpush操作の時間計算量が悪化していますが，
は実質定数(過激派)なので時間計算量が改善しました．
Immutable Queueについて (後編)
ここまでは主に時間計算量，つまり一回あたりの操作でどれくらい計算時間がかかるかに注目してました．この章ではImmutable Queueが消費するメモリについて注目してみたいと思います．
Immutable Queueについて考察する前に，まずはImmutable Stackが消費するメモリ量を確認したいと思います．
上の図はImmutable Stackについてで用いたImmutable Stackの動作例です．ここで，オレンジの枠で囲まれているインスタンス(1,2から構成されているスタック)が破棄されたとします．すると，2を参照しているインスタンスが存在しなくなるので，JavaのGCや参照カウンタ方式の言語では2を表すオブジェクトのメモリを解放してくれます．
Immutable Stackでは，どのインスタンスからも参照されなくなり，今後使用されることがなくなったオブジェクトはいい感じにメモリが解放されます．
Immutable Queue(前編)で紹介させていただいたImmutable Queueは，Immutable Stack2つで動いているので，Immutable Stackと同様，今後使用されることがなくなったオブジェクトはメモリが解放されます．
Immutable Queue(中編)で考察したImmutable Queueにおいては，今後使用されることがないオブジェクトであったとしてもメモリが解放されないことがあります．
左側のような状況の時に，解放されるべきオブジェクトを灰色で表したものが右の木になります．
このうち，5と7については誰からも参照されなくなったので勝手に解放されます． 一方で，1と3については今後必要ないオブジェクトですが，インスタンスからは到達可能なオブジェクトなのでメモリが解放されません．
解放できるオブジェクトとは，どのインスタンスの(head,tail)のパス上にも存在しないオブジェクトになります(上図だと2-6-8が緑のパス，4がオレンジのパスになるので，それ以外の1,3,5,7が解放できるオブジェクトとなる)．
オブジェクトの解放判定に全てのオブジェクトを走査しても良いとするならば，葉から順番にimos法の考え方を適用していけば解放できるオブジェクトを特定できます．
オブジェクトを解放するときに，先ほど利用した2冪のインデックスも外していく必要があります．オブジェクトの数をN個とすると，インデックスの数はO()となるので，1つのオブジェクトのインデックスを外す償却時間計算量はO(
)になります．接続情報を外す償却時間計算量も同じような考え方でO(1)，imos法の時間計算量はO(N)なので，全体でO(
)となります．逮捕!!!
1回のpush, pop操作毎に解放するオブジェクトを特定するのではなく，複数回操作を行なった後に使わないオブジェクトを特定するというやり方を行えば，時間計算量を削減できそうです．より具体的には，現在管理しているデータの個数をN個としたとき，push, popの操作がN回行われたタイミングで管理しているオブジェクトが解放できそうかを判定・解放していきます．push, pop操作がN回行われるとオブジェクト解放判定が1回走り，1回あたりのオブジェクト解放判定はO()かかるので，1回の操作におけるオブジェクト解放判定・解放操作の償却時間計算量はO(
)となります(ほんまか？)．
ここまでの話をまとめると，Immutable Queueは頑張って実装をするとpushがO(), popがO(
)になるので，データ構造警察署から無事に釈放されました!!! 間違ってたら再逮捕で!!!
まとめ
競技プログラミングでImmutable Stackを使う問題は見たことがありますが，Immutable Queueを使う問題は見たことがありません．また，実プログラミングでもImmutable Queueを使うことはおそらくないので，ここで紹介したImmutable Queueの参考実装はありません(は？)． 最後になりましたが，ここまで駄文を見ていただきありがとうございます．最後のオブジェクト解放うんぬんの話はだいぶ怪しいのでコメント等で間違いを指摘していただけるとありがたいですmm
