ソフトウェア性能評価のためのランダムデータ高速生成法

概要

論文の詳細を見る
アルゴリズムの性能の精密な評価を行うためには, 対象となるアルゴリズムの性能に影饗を及ぼす特性を制御して生成されたランダムデータを用いる必要がある. また, 性能評価に要する時間を短くするためには, ランダムデータを高速に生成する必要がある. 特にアルゴリズムの教育において, 学生に作成させたアルゴリズムを正当に評価するためには, 合理的な評価用データが不可欠である. しかし, 所望の特性を有するランダムデータの高速生成は, アルゴリズムの専門家にとっても容易ではない. 例えば, 長さnの順列を等確率, 即ち1/n!で生成する 0(n)アルゴリズムは知られている. しかし, 整列法等の精密な評価のためには, このような一様乱順列による評価では不十分である. 何故ならぱ, アルゴリズムの性能に影響を与える要因はデータのサイズだけではなく, データが有する構造もアルゴリズムの性能を左右するからである. 例えば, 一様乱順列および一様乱数列は, 極めて偏った構造を持つ. 我々は先に各種の性質を有する乱順列を計算機オーバーフロー(またはアンダーフロー)無しで高速に生成する方法を提案した. そこでは順列の含む葉数(数列において自分より小さい隣人を持たない要素の個数)を制御して順列を 0(n)で生成する実用的近似方式についも報告した. そこで述べた精度の高いランダムデータ生成法は, 高性能確率的アルゴリズムの設計にも利用可能であった. そこでの成果に基づき, 我々は, アルゴリズムの研究および教育に関る者が, 各種のランダムデータをインターネット(http://www.futamura.info.waseda.ac.jp/index-j.html)を通じて容易に入手可能にするために, ランダムデータサーバーを開発した. 本稿は, ランダムデータ生成法, ランダムデータサーバー(RDS)およびランダムデータサーバージェネレータ(REGG)の概要について報告する.
一般社団法人情報処理学会の論文
1997-03-12

ソフトウェア性能評価のためのランダムデータ高速生成法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク