2017年度「アルゴリズムとデータ構造」のページ

課題

ソートの実験

非負整数の並びを通常の大小とは異なるある順序で小さい順に並べかえるプログラムを書き、その計算速度を実測します。入力はテキスト形式です。一行が一つの整数でいくつも並んでいます。 入力データの大きさと計算時間の関係を調べてみましょう。

実験用プログラムは15個あります。

  1. 入力して出力するだけのプログラム。ソートしない。
  2. 入力を逆順に出力するだけのプログラム。ソートしない。
  3. バブルソートを実行するプログラム
  4. 選択ソートを実行するプログラム
  5. 挿入ソートを実行するプログラム
  6. シェルソート(2k−1 系列)を実行するプログラム
  7. シェルソート((3k−1)/2 系列)を実行するプログラム
  8. ヒープソートを実行するプログラム
  9. クイックソートを実行するプログラム。先頭の要素をピボットとして使用する。
  10. クイックソートを実行するプログラム。中央の位置の要素をピボットとして使用する。
  11. クイックソートを実行するプログラム。先頭の要素と末尾の要素と中央の位置の要素の中央値をピボットとして使用する。
  12. トップダウンマージソートを実行するプログラム
  13. 単純なマージソートを実行するプログラム
  14. 二方向自然マージソートを実行するプログラム
  15. イントロソートを実行するプログラム。(2017年12月4日追加)

実験用データは ~wd/algo/babylon-2017/ に計90個、あります。

	$ ls ~wd/algo/babylon-2017/
      
で確認してください。 一つのファイルが一揃いのデータです。 r で始まるファイル名のものがランダムに並んだデータ、 s で始まるファイル名のものが正順に並んだデータ、 g で始まるファイル名のものが逆順に並んだデータです。 このデータは大きいので、自分のディレクトリにはコピーしないでください。

入力データの大きさを計るには、wcコマンドを使ってファイルの行数を調べてください。たとえば、

	$ wc ~wd/algo/babylon-2017/r00
      
行数・単語数・バイト数が表示されますが、今回必要なのは行数です。

遅いプログラムに大きなデータを与えると、とてつもなく時間がかかります。 先にデータの個数が少ないファイルについてデータを取り、 その結果、極端に時間ががかかったプログラムについては、データの個数が多いファイルについてはデータ取りを省略してもかまいません。

コンパイルは、最適化を -O2 にそろえて行なってください。たとえば、

      $ cc -O2 babylon-select.c -o babylon-select
    

実験用プログラムは、標準入力から入力し標準出力に出力するよう書かれていますので、リダイレクションを使ってください。実行時間の計測には time コマンドを使ってください。たとえば、

	$ time ./babylon-select <~wd/algo/babylon-2017/r00 >/dev/null
      
なお、この手の実験を行なう場合は、一つの組み合わせにつき最低3回は実験を繰り返し、平均値(か中央値)をとるのが常識です。

補足


戻る