2019年11月27日 | ブログ記事

ポテンシャルによる償却計算量解析

noshi91

償却計算量解析で便利な手段であるポテンシャルの扱いについての簡単な部分を書きます。本稿では時間計算量についてのみを扱い、「計算量」は時間計算量を指します。


可変長配列

以下のクエリを処理する可変長配列を考えます。

このデータ構造はメモリ領域を保持し、そのうち先頭からいくらかが実際に要素で埋まっているという構造を持ちます。保持している領域の大きさを capacitycapacity、入っている要素の数を sizesize で表します。各クエリは以下のアルゴリズムで実現されます。

全てのクエリが償却 O(1)O ( 1 ) で実現されることを、計算量の貯金を用いて示します。

pushpush で領域の拡大が起こるとき、定数倍を除くと高々 sizesize の計算量が必要になります。
ここで、pushpush の度に 22 だけ計算量を「貯金」することを考えてみます。この貯金は後で重い処理をするときに使用して計算量を均す目的で使用されます。逆に、貯金をしたクエリは貯金の分計算量が増えたとみなします。この例では 22 は定数であるため、貯金する分はクエリ辺り O(1)O ( 1 ) であり最終的なオーダーには影響しません。
領域の拡大が起こるとき、前に拡大が起きてから 2size2=size2 * \frac {size} 2 = size だけ貯金が貯まっています。よってこの貯金を使うことで償却 O(1)O ( 1 ) と評価することが出来ます。


ポテンシャル

ポテンシャル Φ\Phi を導入することで、前述した手続きが扱いやすくなります。これはデータ構造の状態に対して数値を与える関数で、その状態のデータ構造に貯まっている貯金の量に対応しています。実際に必要となる計算量を実計算量と呼ぶことにすると、ポテンシャルによる償却計算量の表示は以下のようになります。

償却計算量
== 実計算量 +ΔΦ+ \Delta \Phi
== 実計算量 +Φ(+ \Phi (クエリ後)Φ() - \Phi (クエリ前))

貯金をするとき Φ\Phi は増加し、償却計算量は実計算量より大きくなります。
貯金を崩す時 Φ\Phi は減少し、その分償却計算量は小さくなります。

「現在貯まっている貯金量」「どのクエリでどれほど貯金を増やすか、減らすか」などの複雑な条件を、1つの関数にまとめ上げることが出来ました。このような手法を物理学者法と呼びます。

可変長配列の場合、以下のように定義すると上手く行きます。

Φ:=2sizecapacity\Phi := 2 * size - capacity

これを元にもう一度 pushpush の計算量解析をしてみます。size,capacitysize , capacity はそれぞれクエリが呼ばれた瞬間の値とします。

empty,lookupempty , lookupΦ\Phi を変化させないため実計算量が償却計算量と等しくなり、O(1)O ( 1 ) です。

poppop に対応する

可変長配列に新たなクエリを追加します。

poppop を繰り返し呼ぶと、保持している領域に対して要素数が少ししかない状況が発生します。pushpush 時の拡大と同様に、適切に縮小を行うことで空間計算量を O(size)O ( size ) に削減します。アルゴリズムは以下の通りです

poppop も含めた解析は元のポテンシャルだと上手く行かないので、少しだけ拡張します。

Φ:=2sizecapacity\Phi := | 2 * size - capacity |

poppop の償却計算量を評価します。

empty,lookup,pushempty , lookup , push についての解析は全く同様ですので省略します。


ポテンシャルに必要な性質

償却計算量の定義に沿って考えることで、ポテンシャルに対する制限を導出します。
NN 回のクエリを行うとし、ii 回目のクエリの実計算量を TiT_iΦi\Phi_iii 回目のクエリの直前の値とします。最初は Φ0\Phi_0 で全クエリの終了後には ΦN\Phi_N になっています。

実計算量の和 =Ti= \sum T_i
償却計算量の和 =(Ti+Φi+1Φi)=ΦNΦ0+Ti= \sum ( T_i + \Phi_{i + 1} - \Phi_i ) = \Phi_N - \Phi_0 + \sum T_i

償却計算量の和は実計算量の和を下回ってはいけないので、ΦNΦ00\Phi_N - \Phi_0 \geq 0 が必要十分条件です。また、Φ\Phi は平行移動しても問題ないので Φ0=0\Phi_0 = 0 とすることにします。以上をまとめると次の条件を得ます。

ΦN0\Phi_N \geq 0 はすなわち、貯金はよくても借金はしてはいけないことを意味しています。借金のある状態で操作を終了すると踏み倒しになってしまうと解釈できます。


Two Stack Queue

https://scrapbox.io/data-structures/Sliding_Window_Aggregation
アルゴリズム自体の説明はこちらを参照してください。
ポテンシャルを以下のように設定すると上手く行きます。

Φ:=size(back_stack)\Phi := size ( back\_stack )

各要素の移動する回数に着目する解析も鮮やかですが、ポテンシャルもかなり分かりやすいのではないでしょうか。


解析の注意点


一つのデータ構造の解析で異なるポテンシャルを使わない

データ構造は大抵複数の種類のクエリを処理できますが、それぞれで異なるポテンシャルを用いることはできません。あるクエリを処理するとき、他のクエリで使っているポテンシャルが増加しているかもしれないためです。
そのような「計上されない不正な貯金」が発生しない場合、全ての和をポテンシャルとして定義することで上手く行くこともあります。

実計算量が抑えられていても償却計算量を確認する

たとえ実計算量が O(1)O ( 1 ) のクエリがあったとしても、他のクエリの償却解析のためにポテンシャルを導入したら、そのクエリもポテンシャルの増減を考える必要があります。それによって、償却計算量が実計算量よりオーダーのレベルで大きくなる場合もあります。

解析の途中で OO 記法を使う時は気を付ける

ポテンシャルを OO で不適切に扱うと、誤った解析をしてしまう可能性があります。Φ\Phixx 増加させて償却計算量に計上した後、Φ=O(x)\Phi = O ( x ) であるとして 2x2x の貯金を消費すると、貯金量より多く消費しているため不正です。


まとめ



参考文献

Chris Okasaki. Purely Functional Data Structures
アスキードワンゴ 純粋関数型データ構造

この記事を書いた人
noshi91

この記事をシェア

このエントリーをはてなブックマークに追加

活動の紹介

カテゴリ

タグ