リカーシブスローダウン
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/12/25 08:02 UTC 版)
ナビゲーションに移動 検索に移動サイズがnである再帰的データ構造に対する演算の計算量をT(n)と置くと一般的にT(n)は次のように書ける。
T(n) = X + c T(f(n))
ここでXは1つのノードに必要な計算量で、cは定数、fは部分構造のサイズを返す関数である。ここではXがO(1)、f(n) = n − 1の場合を考える。もしcを1未満にできれば等比数列の性質からT(n)はO(1)となる。例えばc = 1/2の場合、1 + 1/2 + 1/4 + 1/8 + ... = 2であるので全体の計算量は最初の要素の最悪計算量の2倍を超えない。そのため親ノードをO(1)で処理し、子ノードをその半分の計算量で処理できれば全体の計算量は定数時間となる。しかし計算量は離散的であるため再帰処理の中で計算量を半分にし続けることはできない。そこで、代わりに親ノードを2回処理する間に子ノードを1回だけ処理するようにする。
例: 2進カウンタ
例として可変長の2進カウンタを考える[2]。カウンタを数字のリストで表現する。1桁目(最も下位の桁)を増やしていくと繰り上がりにより再帰的に上の桁も増えていく。繰り上がりの際には複数の桁が変化する場合があるが、0である数字が1に変化するのはカウンタ全体で1ヶ所のみである。例えば2回に1回は1桁目、4回に1回は2桁目である。そのため1にすべき桁を特定する処理と1の桁を0にする処理がO(1)でできれば全体の計算量はO(1)となる。
それらの処理をO(1)の計算量で実行するために2つの工夫をする。まず0から1にすべき桁は1桁目から見て最初に0となる桁である。そこで連続する1の列を1つのノードで表す。つまり1だけからなるリストへの参照と、1でない最初の桁への参照を含むノードで表す。例えば次の図は46(十進)を表すカウンタである(このページでは見栄え上、1の塊の最初のノードが1ででない最初の桁へのポインタを持つように表現する。また、「2」の意味はすぐ後の段落で説明する)。
これで最初の1でないノードを定数時間で特定できるようになった。次に1の桁を0にする処理をO(1)で実行するようにする。通常のカウンタでは1の桁を0にする際に連鎖的に繰り上がりが発生する場合があり、O(1)とならない。そこで繰り上がり処理を遅延させる。遅延した繰り上がりと0を合わせて表す数字として2を導入する。2進法に対して数字が3つあるので同じ数に対する表現が複数あることになる(冗長表現)。例えば6(十進)は110とも表現できるし、102とも22とも表現できる。しかし処理を定数時間で終わらせるためには表現に制限を加える必要がある。数字は2までであるので3になりそうになると遅延していた繰り上がりを処理しなければならない。このとき2が複数連続していると繰り上がり処理が連続するので定数時間で処理できない。2の隣が1か0であれば良いが、その条件を満たしていても212のパターンの時に下の2を繰り上らせると220となり2が連続してしまう。そこで次のような不変条件を課する。
「2である任意の桁の下には0個以上の1が続き、さらにその下の桁に0が必ずある」
カウンタを単純に1増やした場合に不変条件が崩れるのは次の2つの場合である。
- 最も下位の桁が2になった場合(例: 102)
- 最も下位の桁が1になり、その上に0個以上1が続いて2がさらに続く場合(例: 211)
前者の場合、最初の桁を0にしてその次の桁(これは必ず1か0である)を1増やす。カウンタを増やす前に不変条件が成り立っていたことを考えると、2桁目より上にある1でない最初の桁は必ず0であるので不変条件は再び満たされるようになる。後者の場合は最初の2を0にしてその次の桁を1増やす。これも同様に不変条件が再び満たされるようになる。以上の処理は全て定数時間で処理できる。
以下に0から始めて17(十進)まで数える例を示す。
矢印の左側は単純に増やした状態で、右側は不変条件を満たすように修正した状態である。どのステップでも高々定数個のポインタを辿り、高々定数個の桁だけを変化させていることがわかる。
一般化
この例のカウンタは3種類の数字から成り、増加のみをサポートする。しかし減算など別の演算を定数時間の計算量でサポートする場合、さらに多くの数字を使う必要があり、不変条件は複雑になってしまう。そこで各ノードの状態を3つの状態に分類して不変条件を統一する。
ノードをその状態により緑・黄・赤に分類する。前の例では0, 1, 2の桁がそれぞれ緑・黄・赤となる。赤はそのままでは処理できないが、次の桁を変化させて自身を緑にできるような状態である。緑は黄に変化する場合はあるが、1回の変化で赤になることはない。黄はそれ以外であり、1回の変化で赤になる可能性がある。このとき不変条件は次のようになる。
「赤である任意の桁の下には0個以上の黄が続き、さらにその下の桁に緑が必ずある」
連続する黄は1つのノードとして表現する。
- ^ a b c Haim Kaplan and Robert E. Tarjan, “Persistent lists with catenation via recursive slow-down”, In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing (STOC '95), New York, NY, USA: ACM, 1995, pp. 93–102. DOI=10.1145/225058.225090 http://doi.acm.org/10.1145/225058.225090
- ^ a b c d Chris Okasaki, Purely Functional Data Structures, New York, NY, USA: Cambridge University Press, 1998.
- ^ Ralf Hinze and Ross Paterson, “Finger Trees: A Simple General-purpose Data Structure”, In Journal of Functional Programming Vol. 16, No. 2, 2006, pp. 197–217, doi:10.1017/S0956796805005769
- 1 リカーシブスローダウンとは
- 2 リカーシブスローダウンの概要
- 3 亜種
- リカーシブスローダウンのページへのリンク
