整列法評価のためのランダム順列の生成
スポンサーリンク
概要
- 論文の詳細を見る
整列法(ソーティングアルゴリズム)の性能評価のための入力列として、従来は多くの場合に一様乱数列が利用されてきた。しかし現実の問題としてソーティングを扱う場合には、与えられた数列はほとんど整列済みであることが多いと言われている。従って、ソーティングアルゴリズムの性能評価をする際には、入力列の整列度合を表す各種の事前整列性測度を制御しながら入力列を生成する必要がある。実際ある種の整列性測度で見ると一様乱数は非常に偏った値を持ち、整列法の性能評価には不適である。本稿では(1)事前整列性測度のうち、葉数(数列内で隣接する要素より小さい要素の個数)を制御し、任意に与えられた葉数mを持つ順列を一様に生成する方法、(2)生成された順列の一様性を検定する方法および(3)検定結果について報告する。葉数の事前整列性測度としての妥当性については[4]で述べた。
- 一般社団法人情報処理学会の論文
- 1995-03-15
著者
-
青木 健一
早稲田大学理工学部
-
二村 良彦
早稲田大学理工学部コンピュータ・ネットワーク工学科
-
大谷 啓記
NTTコミュニケーションウェア(株)
-
大谷 啓記
早稲田大学大学院理工学研究科情報科学専攻
-
白井 千恵子
早稲田大学理工学部
-
遠藤 貢一
早稲田大学理工学部
-
遠藤 貢一
早稲田大学 理工学部
-
白井 千恵子
早稲田大学大学院理工学研究科
-
大谷 啓記
早稲田大学大学院理工学研究科:(現)NTTコミュニケーションウェア(株)
関連論文
- 「計算過程の部分評価」再び
- 累積変数を用いるリスト処理関数とその融合法
- Recursion Removal under Environments with Cache and Garbage Collection (Program Transformation, Symbolic Computation and Algebraic Manipulation)
- 木再帰プログラムからの再帰還元(一般発表)
- 再帰除去のごみ回避効果
- ある種の木再帰プログラムからの再帰除去
- ラベル付き連結グラフ高速ランダム生成のための構成比近似法
- 96-1 高性能計算機のためのコンパイラ最適化法, David F. Bacon, Susan L. Graham and Oliver J. Sharp, Compiler Transformations for High-Performance Computing, [ACM Computing Survey, Vol.26, No.4, pp.343-420(Dec.1994)], Key : Compilation, dependence analysis, locality, multiproc
- 単純指標を持つ乱順列の高速生成法
- ソフトウェア性能評価のためのランダムデータ高速生成法 (第54回全国大会 (平成9年前期 於 : 千葉工大) 大会優秀賞受賞論文 (11件)