＜ プログラムの説明 ＞ 【 概要 】 逐次環境でのマルチ集合の高速な演算モジュールである. 内部表現は [ 要素１の値, 要素１の個数, 要素２の値, 要素２の個数, ...] のように, 値と個数の組を, 要素の値の昇順に並べたリストである. 例えば, マルチ集合 [7,1,2,7,7] と [5,7,2,7] の内部表現はそれぞれ, [1,1,2,1,7,3], [2,1,5,1,7,2] となる. encode のコストは, 平均的な入力: ほぼ O(N) 最善の場合: O(N) 最悪の場合: O(NlogN) である. decode, union,intersection などは O(N), choose は定数時間で処理される. 【 内部表現の決定 】 union/3, intersection/3, difference/3 などは内部表現が昇順のリストのよう にソートされている場合は, 先頭から逐一比較していくと, 線形時間で処理できる. ここで, intersection/3 と difference/3 は比較していくときに要素を「とばす」 ことがある. そこで, ちょうど M 文字のテキストから N 文字のパターンを検索す るときに, 通常は O(M + N) で行なうが, パターンをコンパイルすると O(M / N) で行なうことができる(Boyer-Moore)ように, リストをスキップしながら一部のみ 比較していくアルゴリズムが期待される. ただし, このような「とばし読み」のた めにはリストの任意の要素を等しいコストで参照できる必要がある. そのためには ベクタを使えばよいが, もともと線形時間で処理できる問題であるから, KLIC で は, ベクタを用いてわずかに比較回数を下げるよりも, 参照コストの低い線形リス トを用いて, 素直に N 回比較する方が良いだろう. 一方, ハッシュを用いると encode を含め, 一連の操作を O(N) で行なえる. た だし, ハッシュ表のサイズは要素数のオーダになるため, union, intersection な どの操作では, 内部表現がソートされたリストである場合と比較して, ( ベクタ参 照コスト／リストの参照コスト ) 程度遅くなる. また, ハッシュ表のサイズを適 当に見積もれないときは更にロスが生じる. 以上のことから, 内部表現はソートされたリストとするのが適当である. 【 エンコード方法 】 そこで, encode を高速に行なうことが最も重要になる. 単純にソートすると O(NlogN) であるが, 入力が整数であることを活かして, 線形に近い時間でソート することを考える. また, 最悪の場合でも O(NlogN) を保証したい. 問題の趣旨から考えて, 与えられたマルチ集合の要素数を N としたとき, 要素 の大部分は 0 〜 C*N (Cは定数) 程度におさまる場合が多いであろう, と期待する ことができる. 例えば, 要素数 100 のマルチ集合では多くの要素は 0 〜 数百 程 度であろうと期待される. この, 「出現が期待される領域」に対しては, 要素の値 をハッシュ値 ( hash(X)=X ) としてハッシュすると線形時間でソートが行なわれ, 処理時間を短縮できる. それ以外の領域は最悪の場合の性能を保証できるマージソー トを用いることにすると, encode のコストは, 入力リストの要素の最大値 Max, 要素数 N, 定数 C, N*C より大きい要素数 Plus, 負の要素数 Minus としたとき, Max < N*C のとき (N - Minus) + Minus log(Minus) Max >= N*C のとき (N - Plus - Minus) + Plus log(Plus) + Minus log(Minus) である. 最も良いのは任意の要素 X が 0 =< X < N*C であるときの O(N), 最悪の 場合は O(NlogN) であり, 平均的な入力であれば, ほぼ O(N) でエンコードされる. 定数 C は任意の非負数であるが, ここでは, C=4 とした. 【 マージソートについて 】 マージソートは入力に最初の並び方に左右されず, 安定して NlogN 回の比較で整 列する. まず, encode モジュール中の mergesort_init で整数のリストを [ [ 値, 個数, 値, 個数 ], [ 値, 個数, 値, 個数 ], ... ] のように初期化する. mergesort(L,M) の入力 L は上のような, リストのリストで ある. merge_pairs(L,R) はリスト L の要素(リスト)を先頭から順に２個ずつマー ジしていく. すなわち, mergesort が merge_pairs を呼ぶたびに, ボトムアップ に整列が進行していく. -------------------------------------------------------------------------- 宇佐治彦 東京大学工学系研究科 E-Mail: usa@logos.t.u-tokyo.ac.jp