********************************** * * * プログラムの説明書 * * * ********************************** 1. プログラムの設計方針 プログラムを書くに当たって、次のようなことを目指した: (a) 処理速度をなるべく上げる。 (b) どんな入力に対してもある程度の速度を確保する。 (c) なるべく大きな入力を扱えるようにする。 (d) encode 時間をある程度犠牲にしても、他の演算の処理速度を上げる。 (審査プログラムにおける encode の割合は小さいであろう、ということを念 頭に置いた。) 2. 内部表現のデータ構造 当初、与えられた集合をプロセスネットワークに展開して保持し、encode の結 果としてネットワークへのストリームを返すということも考えたが、今回指定され た述語呼び出しの形式では無理である。従って、内部表現は「本当の」データ構造 として保持しなければならない。 内部表現のデータ構造は、入力や演算の性質を反映し、さらに演算の際に演算以 外の後処理をしなくても演算結果が自然にそのデータ構造の制約を満たすことが望 ましい。マルチ集合およびその演算の性質には次のようなものがある: (a) 与えられるマルチ集合および演算結果の大きさは未知である。 (b) 要素間のマッチングを必要とする演算(intersection, difference)がある。 (c) 同じ要素の個数に関係する演算(intersection, difference, contraction)が ある。 (a)から、生成の際にあらかじめ大きさを指定しなくてもよいデータ構造として リストを用いることにした。(b)から、2つの集合間で同じ要素を見つけやすいよう にリスト内をソートすることにした。(c)から、同じ要素の個数がすぐに分かるよ うに、同じ要素の個数を保持することにした。 まとめると、本プログラムで用いる内部表現は、要素とその個数のペアのリスト で、ペアは要素の大きさでソートされている。 ex.) [1,5,2,3,32,2,32,5,2,1] → [(1,2), (2,3), (3,1), (5,2), (32,2)] 要素と個数のペア構造にファンクタを用いたのは、リストやベクタを用いるよりも 処理が速かったからである。また、要素毎にハッシュして、1本ではなく複数のリ ストを持つことで、演算によっては計算量のオーダを下げられるかもしれないが、 オーバヘッドを考えると実時間の短縮にはつながりそうもなかったので採用しなかっ た。 3. プログラムの内容 ほとんどの述語は、内部表現のデータ構造を利用した単純で素直な構成である。 プロセスネットワークは、ネットワーク/内部表現の変換がオーバヘッドとなるの で利用しなかった。 (A) encode 入力リストをソートし、同じ要素を1つにまとめて内部表現を作る。ソートは、 クイックソートとマージソートを入力列の性質に応じて切替えている。 クイックソートでは、リストの先頭3要素のうち真中の大きさの要素を分割の境 界とすることで、なるべく分割後の2つのリストの大きさを揃え、処理時間の短 縮を図っている。 クイックソートだけでは、元々入力リストがソートされているような場合の処理 時間が非常に長くなってしまう。そこで、このような場合にはマージソートを用い る。マージソートは、最初のマージ単位が1要素の単純マージソートではなく、元 から存在する昇順あるいは降順の部分列を利用する自然マージソートを用いた。 クイックソートとマージソートの切替えは、次のように行なう。まず、入力リス トの先頭100要素に存在する昇順/降順列の個数を調べる。 ex.) 入力リスト [1,5,2,3,32,2,32,5,2,1] の場合、 昇順列: [1,5], [2,3,32], [2,32], [5], [2], [1] の6個。 降順列: [1], [5,2], [3], [32,2], [32,5,2,1] の5個。 昇順列の個数がある程度少ない(1つ1つの昇順列が大きい)場合には昇順列を利用 したマージソートを行ない、降順列が少ない場合には降順列を利用したマージソー トを行なう。それ以外の場合にはクイックソートを行なう。本プログラムでは、入 力リストの先頭100要素での昇順/降順列の個数が30未満であればマージソートを利 用する。 (B) decode 内部表現を先頭から順番にリストに変換する。デコード結果はソートされたリス トとなる。 (C) union, intersection, difference 3つの述語とも、「2つのソートされた列から1つのソートされた列を作る」とい う、基本的にマージソートと似た処理を行なう。 (D) contraction 内部表現の要素の個数を全て1に書き換える。 (E) choose 内部表現の先頭から1要素をとり、個数を1減らす。先頭要素の個数が1のときは、 そのペアを内部表現から削除する。 4. 実行結果 コンテスト課題に添付されている審査プログラム例を用いて実行したときの実行 時間を示す。環境は Sparc Station 20 + SunOS4.1.3 + klic2.004 + gcc2.7.2.1 で、-O2 -n を付けてコンパイルし、-H 4m を付けて実行した。 入力リスト長 /bin/time での計測結果 10,000 2.2 real 1.4 user 0.3 sys 20,000 3.6 real 2.9 user 0.6 sys 30,000 5.3 real 4.2 user 1.0 sys 40,000 7.5 real 6.1 user 1.3 sys 50,000 9.6 real 7.2 user 2.2 sys 60,000 10.9 real 8.9 user 1.9 sys 70,000 12.2 real 10.2 user 1.9 sys 80,000 15.0 real 12.4 user 2.5 sys 90,000 18.0 real 14.6 user 3.2 sys 100,000 19.3 real 15.3 user 4.0 sys 入力リスト長は、最大 360,000 要素まで動作可能であることを確認した。 5. 参考文献 プログラム作成に当たり、主に次のものを参考にした。 (a) KLIC 講習会テキスト -- KL1 言語編 -- (b) 日本語版 KLIC Emacs Info [感想] 素人同然の状態からプログラムを始めたが、結構簡単に作れた。ただ、今回の課 題は以外と選択の余地が少なく、スピードを追求するとどれも同じようなプログラ ムになってしまうのではないかと心配である。モジュールだけではなくて、プログ ラム全体を作らせてもらえれば、もっといろいろなものが作れたと思う。また、 KLIC のリファレンスマニュアルの類をもっと充実させて欲しいと思った。