リストの可逆分割アルゴリズムを利用したゴミ情報が最適な可逆クイック整列法の生成
2010SE273 山下健太
指導教員：横山哲郎

はじめに

13

既存の可逆クイックソート
文献 [1] では，従来のリストの分割操作に代わり，次本論文では文献 [1] におけるゴミ情報の生成・マージの手法を応用し，より一般性の高い手法を提案する．文献 [1]では，ゴミ情報量が最適なリストの可逆分割アルゴリズムを提案している．ここではさらに提案したアルゴリズムを利用してクイックソートを生成し，分割の際のゴミ情報量の ア ル ゴ リ ズ ム RSplit F (L) を 提 案 し て い る ．ま た ，RSplit F (L) の検証を行うために，このアルゴリズムを′利用したクイックソートのアルゴリズム Q (L) を示している．なお，文献 [1] では各アルゴリズムの入出力に labeled partial order を利用しているが，本論文の範囲におが最適であること，再帰呼び出しの際にゴミ情報の最適ないては通常のリストを利用しても一般性が失われないた
伝播が実現できていることの 2 点を示している．しかし， め，本論文においては通常のリストを利用している．
この手法はクイックソートに特有のサブプロシージャに対して最適なゴミ情報の生成を保証することにより実現されており，この手法をそのまま他のアルゴリズムに応用することが難しい．そこで，本研究ではアルゴリズムのより小さな構成要素に最適なゴミ情報を生成させ，それらの最適性を保ったままより大きな構成要素へとマージを行う手法

Algorithm 1 Reversible Split algorithm: Forward computing （[1] より改変）
Input: a discrete list L.
Output: a three-layered series list (Y1 , Y2 , Y3 )and reversal index : RIndexを提案し，既存の手法の応用性を高める．なお，ここでは
ゴミ情報とは非可逆アルゴリズムを可逆化する際に記録する必要があり，可逆化する前の非可逆アルゴリズムにおいては記録する必要のない情報を表す．

2関連研究

2.1

可逆アルゴリズム

可逆アルゴリズムとは，出力から入力を復号できるアルゴリズムである．なお，この性質は可逆性と呼ばれる．本RSplit F (L) :(Y1 , Y2 , Y3 ) ← Split(L)RIndex ← f ({pos(yi ) − 1}yi ∈Y1 )return (Y1 , Y2 , Y3 ), RIndex

Algorithm 2 Reversible Quicksort algorithm: Forward
computing （[1] より改変）
Input: a discrete list L
Output: a linear list L∗ and reversal index

来は可逆性をもたないアルゴリズムについても，入力を特定するための情報を出力に追加することで可逆化を行うことができる．なお，この情報はゴミ情報と呼ばれる．

2.2

In-Place アルゴリズム

In-Place アルゴリズムとは，入力されたデータを直接改変するアルゴリズムである．このようなアルゴリズムを可逆化するためには，ゴミ情報と呼ばれる付加情報を出力する必要がある．例えば n 個の要素をもつリストをソートす
る In-Place アルゴリズムを可逆化する場合，log2 n! ビッ′

Q (L) :if |L| ≤ 1 thenreturn (L, 1)else(Y1 , Y2 , Y3 ), C0 ← RSplit F (L)′′(Y1 , C1 ) ← Q (Y1 ), (Y3 , C2 ) ← Q (Y3 )return ([Y1 : Y2 : Y3 ], |Y3 |(|L| − 1)! + C0 |Y1 |!|Y3 |! +(C1 − 1)|Y3 |! + C2 )end if

トのゴミ情報を出力する必要がある [2] [3]．

RSplit F (L) はリスト L を入力とし，L の先頭の要素を2.3比較ソートの理論限界

各要素の大小関係を比較し，要素の位置を入れ替えることでソートを行うソート法は比較ソートと総称される．比較ソートは入力されるデータに何らかの制約を設けない限り，入力の要素数 n 個に対して最悪計算量が O(n log2 n)を下回ることはないことが知られている．

ピボットとして L をサブリスト Y1 ，Y2 ，Y3 に分割する．
その際にピボットより大きい要素を Y1 に，ピボットを Y2に，ピボットより小さい要素を Y3 に格納する．分割後，|Y |

1
Y1 に格納された要素の L における位置 {xi }i=1を関数

f ({xi }ki=1 ) =k∑
i=1

xi −1 Ci

(1)

によって RIndex に変換し，これを記録する．

格納する．このとき要素を Y1 に格納した場合はゴミ情報

文献 [1] では RSplit F (L) を利用してリストの分割を′|Y1 |+|Y3 |−1 C|Y1 | を生成し，その時点での RIndex に加算す行うことで，可逆クイックソート Q (L) を実現している． ることでマージを行う．以上の処理を再帰的に繰り返すこ′

可逆性を実現するために，Q (L) は 4 つの整数 |Y3 |，C0 ， とで，Algorithm 3 は Algorithm 1 と同様の分割処理を

C1 ，C2 を記録する必要がある．これらはそれぞれ Y3 の要
素数，RIndex ，Y1 のゴミ情報，Y3 のゴミ情報を表す．こ′れらの情報を 4 つの値として記録する場合，Q (L) が自身を再帰的に呼び出すたびに返り値の数が大きくなる．その′ため，Q (L) では式

reversal index =|Y3 |(|L| − 1)! + C0 |Y1 |!|Y3 |!
+(C1 − 1)|Y3 |! + C2(2)行う．

Algorithm 3 Reversible Split algorithm: Forward computing （Algorithm 1 より改変）
Input: a discrete list L, a three-layered series
list (Y1 , Y2 , Y3 ), and reversal index : RIndex .
Output: a three-layered series list (Y1 , Y2 , Y3 ),and reversal index : RIndex .
′を用いて 4 つの値から reversal index を算出し，これを記RSplit F (L, (Y1 , Y2 , Y3 ), RIndex ) :if Y2 = ∅ thenY2 ∪ L[0], L ← tail(L)else if L[0] < Y2 [0] thenY1 ∪ L[0], L ← tail(L)RIndex ← RIndex + |Y1 |+|Y3 |−1 C|Y1 |else
Y3 ∪ L[0], L ← tail(L)end ifif L ̸= ∅ then((Y1 , Y2 , Y3 ), RIndex )′RSplit F (L, (Y1 , Y2 , Y3 ), RIndex )end ifreturn ((Y1 , Y2 , Y3 ), RIndex )録する．文献 [1] において，{pos(yi ) − 1}yi ∈Y1 と RIndexの値の組み合わせが全単射の関係にあることが証明されているため，reversal index とリスト (Y1 ，Y2 ，Y3 ) の組み合わせからリスト L を一意に特定できることが分かっている．また，要素数が n 個のリスト L に対し RIndex の値′が n! 通りの値をとることから，Q (L) の処理全体ではゴミ情報量が最適であることが明らかである．そのため，既存の手法によって 4 つの情報を最適にマージできていることが分かっている．しかし，文献 [1] ではその理由が明らかにされていない．また，文献 [1] で示されている手法は4 つの整数をマージするものであり，一般性が低い．そのため，現時点では文献 [1] の手法を他のアルゴリズムに応用することが難しい．

4提案する手法

4.1

ゴミ情報の定式化と演算子 15

←

おわりに

そこで，本研究ではゴミ情報を 2 つの整数の組として定本研究では，ゴミ情報の定式化・ゴミ情報のマージを行式化し，2 つのゴミ情報をオペランドとして reversal index

う演算子 1 の定義を行った．これによって，プロセスを細を求める演算子 1 を提案する．演算子 1 によって行われ分化した可逆クイックソート・可逆マージソートを実現しる演算は，式た．今後の課題として，入力の組み合わせ以外を記録する(g1 , h1 ) 1 (g2 , h2 ) = (g1 × h2 + g2 , h1 × h2 )ためのゴミ情報を生成するプロセスの確立が挙げられる．

(3)

として定式化できる．ただし，n は自然数，gn はゴミ情報の値，hn は gn の取り得る最大値に 1 を加算した値とする．また，ここでは演算子 1 は結合性をもつ．演算子 1 を用いて，式 (1) と同様の reversal index を生成可能であることが確認できる．既存の手法を利用して reversal indexを生成する際には不必要な情報が発生していないことが証明されているため，1 によってゴミ情報の最適なマージができていることが確認できる．

4.2

プロセスを細分化した可逆分割アルゴリズム

可逆アルゴリズムの一般性を高めるため，Algorithm

1 に対して処理の細分化を行ったアルゴリズムが次に示
す Algorithm 3 である．Algorithm 3 は入力としてリス
ト L，サブリストの組 (Y1 , Y2 , Y3 )，ゴミ情報 RIndex を受け取り，リスト L の先頭の要素を適切なサブリストにこれを実現できた場合，リストの分割を利用したアルゴリズム以外のアルゴリズムの可逆化が可能になると考えられる．

参考文献[1] Early, D., Gao, A. and Schellekens, M.: Frugal Encoding in Reversible MOQA: A Case Study for
Quicksort, Proc. Reversible Computation, Glück, R.
and Yokoyama, T. (Eds.), Lecture Notes in Computer Science, Vol. 7581, Springer-Verlag, pp. 85–96(2012).
[2] Perumalla, K. S.: Introduction to Reversible Computing, CRC Press (2013).
[3] Hall, J. S.: A Reversible Instruction Set Architecture and Algorithms, Proc. Physics and Computation, IEEE Press, pp. 128–134 (1994).