逐次環境部門 全体講評


逐次部門には全部で54件の応募があった。乱数で生成したデータに対してさま
ざまな操作を行なうテストプログラムとリンクし, 期待通りの答が出るかを確
かめたところ, 43件がこの段階をパスしので, これらを参加賞の対象とした。
なお, テストを通らなかったプログラムには, わずかな注意不足による例外的
な場合の対処忘れなどが少なくなかった。

全体として, 課題が比較的やさしかったためか, なんとか正しく動くだけといっ
たプログラムは少数で, ほとんどの作品には性能向上のためになんらかの工夫
が施してあった。この課題はいったん入力データを内部表現にエンコードし,
それに対して演算を施していくので, 内部表現形式が性能を大きく左右する。

エンコード前のデータは, さまざまな形をしている場合が考えられる。同じデー
タの重複の多いもの/少ないもの, 値の範囲がゼロ付近のもの/正または負の絶
対値の大きなあたりに偏っているもの, バラバラの順序のもの/整列済みのも
の, などである。今回は入力データについて課題中に特定の傾向を指定しなかっ
たので, どのような入力に対しても安定してある程度高い性能を示す作品につ
いて, アルゴリズムの設計, プログラミングの工夫, 付属文書のわかりやすさ
などの点も勘案して評価することとした。性能の測定には, 以下のような異な
る性質を持つデータを乱数を元に数多く生成し, これらに対してやはり乱数で
生成した演算を数多く行なう, というプログラムを用いた。

(1) ある程度の重複のあるゼロ付近のデータ
(2) 同様のデータだが昇順に整列してあるもの
(3) 同様のデータだが降順に整列してあるもの
(4) まばらで重複の少ない絶対値の大きなデータ
(5) ある程度の重複のある絶対値の大きなデータ

マルチセットでは同じデータの重複があるので, データの値と重複数のペアを
管理するのが有利である。このような表現を取れば, エンコード後のさまざま
な演算のコストは重複数によらず, データの種類だけに依存する。

応募作品の多くはエンコード時にデータを整列してしまい, 以降の演算は整列
済みデータに対して行なうものだった。データの種類を n とすると, 整列し
た表現なら演算の手間は n に比例する程度で済む。少数だが binary TRIE を
用いるものもあったが, TRIE 構造では演算に n の他に木の深さにも比例する
手間がかかる。ことに値の絶対値の大きい (4), (5) のようなデータに対して
は木が深くなるので, 性能上の不利が大きい。結局入賞作品はすべて整列する
方式のものになった。

整列の方法は性能上の大きな問題になる。Prolog でもそうだが, 論理型言語
の例題として良く出てくるいわゆる「クイックソート」は, (2), (3) のよう
な整列済みデータについては著しく不利である。通常の手続き型言語で書くク
イックソートなら, ピボットの選択を工夫すればこの欠点をカバーできるが,
乱アクセスできる配列ではなくリスト構造を使う場合, そう簡単にはいかない。
また, クイックソート本来の利点である余分な作業場所がデータ個数の対数オー
ダで済むという性質は, 配列要素の一定の手間での入れ換えに依っており, 論
理型言語で書くいわゆる「クイックソート」にこの利点はない。

というわけで, 論理型言語でソーティングを行なうには「クイックソート」よ
りマージソートを用いた方が良いのが普通である。実際性能評価の結果, マー
ジソートを用いたものの方が良い成績を収めている。

整列した表現を取る場合, 演算自体には工夫の余地が大きくないようだ。比較
的低レベルのメモリ節約の工夫などが可能な程度である。


他部門の表彰 並列環境部門発表