|
[ 0307: sort アルゴリズムの性能比較 ]
[ 南門疾矢君の出題 ]
sort というのはデータを大小順に並べ直すことです。
昇順 (小さいものから大きいものへ) と降順 (大きいものから小さいものへ)
がありますが、この評価ではどちらでもいいです。
sort には昔から様々な方法が提案されており、主なものの一欄は以下のとおりです。
O(n) は実現不可能ですが、O(n*log(n)) は実用になると言えます。
このうち、2 分木ソート、マージソート、クイックソートに関して実行時間の比較
をしてください。どんな結果になるでしょう？
-
1000 個 のテストデータ (整数で可) をあらかじめ乱数で生成し、これをそれぞれの
アルゴリズム用の Perl プログラムに配列 (array) としてコピーして入れてください。
-
処理時間の測定には time perl QuickSort.pl みたいに
time コマンドを使ってください。
time perl QuickSort.pl
Count 5149
real 0m0.244s
user 0m0.009s
sys 0m0.008s
-
アルゴリズムは GeekForGeeks
サイトなどで公開されていますから、
自分で真似してください。
[ 湯会老人のコメント ]
実際にプログラムを作って実行し処理時間を計測するとかえって本質を見失います。
Sort アルゴリズムの性能とは:
「こういう状態のデータに対して大小比較を何回やれば sort しきれるか」
ということです。
サブルーチンを含むプログラムではサブルーチンを呼び出す際に引数 (ひきすう)
を与え、サブルーチンから戻ってくる際に間違いなく戻ってくるための情報を記録します。
自分自身を呼び出す再帰的関数 (recursive function) では
これらの情報をスタック (stack) に入れる方法を取るため、
再帰的呼び出しが深くなるとスタック領域をそれだけ消費し
極端な場合は stack overflow になります。
実際に実行するとアルゴリズム以外のところで
こうした overhead (余分な処理) がありますから、
実行時間よりも:
「大小比較演算が何回おこなわれたか」をカウントしたほうがいいでしょう。
[ 南門疾矢君のコメント ]
たしかにそうですね。
ふつうアルゴリズムの性能比較は今でも擬似コード (pseudo code)
を書いて該当処理部分の「行数」を数えたりしています。
了解しました。まずは「大小比較演算のカウント方式」で進めましょう。
各アルゴリズムのサンプルコード (Perl 言語でいいでしょう) を乗児君に渡します。
あとは楽にできるでしょう。
|