第３回、「ソート時間の測定」

課題の説明

  1. 前回作成したソートプログラムを修正せよ
  2. profile_sort.tar.gz を用いて、以下の測定を行い、結果を簡潔に報告せよ
    • ソート対象
      • ランダムデータのソート時間
      • 一部ソート済みデータのソート時間

    • ただし、ソート時間の計測対象は、以下の通りとする(増やしてもよい)
      • sort コマンド
      • stl_sort.cpp
      • bubble_sort.c
      • 自作のソートプログラム

    • 実行例 
      % tar zxvf profile_sort.tar.gz
% cd profile_sort
% make profile
gcc -O3 -Wall -Werror    bubble_sort.c   -o bubble_sort
g++ -O3 -Wall -Werror    stl_sort.cpp   -o stl_sort
g++ -O3 -Wall -Werror   -c -o dataCreate.o dataCreate.cpp
g++ -O3 -Wall -Werror    createRandomData.cpp dataCreate.o   -o createRandomData
g++ -O3 -Wall -Werror    createPartialSortedData.cpp dataCreate.o   -o createPartialSortedData
# ruby tinyProfile.rb ./a.out
# ↑ こんな感じで Makefile を修正し、自作プログラムを実行すること
ruby tinyProfile.rb ./stl_sort
................................................................
ruby plotProfile.rb *_log.txt > plot_log.gnu
ruby plotProfile.rb *_log_p.txt > plot_log_p.gnu
gnuplot plot_log.gnu

gnuplot plot_log_p.gnu

%

      profile_image.jpg

      測定データの gnuplot 表示例

提出された課題へのコメント

今回の課題では、ソートの計時を通して「プログラム実行結果の測定」の自動化、についての体験が目的でした。何度も行う測定などは、スクリプト等を用いて自動化することを勧めます。なので、どのソートプログラムのアルゴリズムが速いとか、はおまけです。
ソートについては、問題がない限りライブラリ提供のソートを使っておけばよいです。

では、提出された課題へのコメントです。

提出された課題 
１に関しては、前回指摘された「扱う数が５限定」という点を修正しました。
サンプルプログラムと少し形を変えようと試行錯誤したのですが、
なんか結果がイマイチな気がしないでもないです。
あと、バブルソートは効率が悪いという指摘も貰ったのでqsortを使いました。
qsortは前回使ってる人がいたので参考にさせてもらいました。

２に関しては、サンプルとしてある３つと比べると、自作のプログラムの方が早
かったです。
グラフでは細かい数値までは判らないので、timeコマンドも使ってみました。
ランダムの10000個をソートした結果が下記。

$ time ./bubble_sort < random.txt >
real 0m0.537s
user 0m0.523s
sys 0m0.002s
$ time ./stl_sort < random.txt >
real 0m0.082s
user 0m0.026s
sys 0m0.003s
$ time sort < random.txt >
real 0m0.083s
user 0m0.065s
sys 0m0.005s
$ time ./sort2 < random.txt > ←自作
real 0m0.031s
user 0m0.017s
sys 0m0.002s

今回一番手こずったのは、apt-getが正常に動作しなかったので、rubyがなかな
かインストール
できなかったことでした。
web上でエラーメッセージで検索して、なんとか解決できました。

すまん、突っ込みどころが満載です。

あと、「一部ソード済みのデータ」に対するコメントがないです。むぅ。
それから、文章をもう少し簡潔にまとめた方がよいでしょう。


提出されたプログラム 
#include <stdio.h>
#include <stdlib.h>

int compare_int(const int *a, const int *b) {
  return *a - *b;    //aとbを比較する
}

int main(void)
{
  int box[1024], i, max=0, ret;

  //EOFが出るまでboxに放り込む
  while((ret = scanf("%d", &box[max])) != EOF) max++;

  //qsortで並び替え
  qsort(box, max, sizeof(int), (int (*)(const void*, const void*))compare_int);

  for(i=0; i<max; i++) printf("%d\n", box[i]);
  return 0;
}

全体的に良くなってきたと思います。曖昧でないコメントを意識すると、もっとよくなるでしょう。


提出された課題 
●ランダムデータのソート時間
sort コマンド、stl_sort の２つは 32768個 のソートでも 0.1秒 かかっていな
いが、
bubble_sort は指数関数的に計算時間が増えていき、32768 では 3.6秒 かかった。
単純ソート（自作の）も同様に増えていき、32768 では 4.5 秒 かかった。

●一部ソート済みデータのソート時間
sort コマンド、stl_sort、bubble_sort の３つの場合、比例して計算時間が増
えていき、32768 では、

stl_sort ：0.08 秒
sort コマンド：0.06 秒
bubble_sort ：0.05 秒

となった。

自作の単純ソートは、指数関数的に増え、最終的に 1.5 秒かかり、他の物より
大幅に時間が掛かっている。

２つの結果に対して大きく分けられているのが、よいです。ただ文章が微妙に曖昧です。「32768 では 4.5 秒 かかった」->「データ数が 32768 では、計算時間が 4.5 秒かかった」というように、修飾関係は直近にある方が読みやすいです。


提出されたプログラム 
//入力された数列をソートするプログラム

#include<stdio.h>

int main(void){

  enum {size=32768};
  int data[size];
  int n;  //比較する数字の数
  int ret;
  int i,j;
  int min;

  for(n=0;n<size;n++){ //数値を配列に入れる
    if((ret=scanf("%d",&data[n]))==EOF){
      break;
    }
    if(ret<=0){
      n--;
    }
  }

  for(i=0;i<n;i++){ //ソート
    min=data[i];
    for(j=i;j<n;j++){
      if(min>data[j]){
        min=data[j];
        data[j]=data[i];
        data[i]=min;
      }
    }
  }

  for(i=0;i<n;i++){    //出力
    printf("%d\n",data[i]);
  }

  return 0;
}

特に問題ないと思います。「ソート」よりは「バブルソート」と書くべきなくらいか？ まぁ、どっちでもよいです。


提出された課題 
今回のプログラミング勉強会の課題を提出します。

質問なのですが、今回のソートプログラムを任意のサイズの配列について実装
しようとしてＣ言語の関数reallocを使う事にしました。
最初にmallocでint型分のメモリを１０個確保し、読み込む要素が１０を超えた時に
reallocを呼び出し、そこで追加のメモリを１０個確保する様にしたのですが、
何回もreallocを呼び出すと
コンソールに次の様なエラーがでて、プログラムが強制終了してしまいました。

$ ./sort_r_xxx < random_data.txt
与えられた配列のサイズは16384です
ソートを開始します
*** glibc detected *** free(): invalid pointer: 0x0806f018 ***
[3] 14458 abort (core dumped) ./sort_r_xxx < random_data.txt

なお、読み込ませる配列のサイズが小さい時はreallocを呼び出したとしても強
制終了せず、
結果もソートされています。

原因がわからず、mallocで十分大きいサイズをとることで結果を出力しました。
そのため、任意のサイズの配列をソートする題意にはそえませんでした。
申し訳ありません。


エラーに関してですが、reallocで領域を確保する時に
確保する領域のサイズをsizeof(int)にするのを忘れていたためにおこった
ようです。
修正したソースを送ります。
申し訳ありませんでした。

よく頑張りました。プログラムが強制終了したら、デバッガ等で原因を調査するようにして下さい。動的に配列を拡張する方法については、「プログラミング作法」に詳しく説明してありますので、参考にして下さい。

でも、今回の課題はソート結果についての考察を主に要求したのですが...。残念です。本当はプログラムを作ることが目的ではなく、プログラムで問題の解を導くのが目的なのです。目的はしっかり確認しましょう。


提出されたプログラム 
//読み込んだ数字をソートして表中出力

#include<stdio.h>
#include<stdlib.h>

//qsort用比較関数
int cmp(int *n, int *m)
{
  if(*n>*m)
    return 1;
  if(*n<*m)
    return -1;
  else
    return 0;
}

int main(void)
{
  int i;
  int count=0;//配列の要素数を格納する変数
  int *sort;//ソートする配列のポインタ
  int *pointer;//メモリの参照先を記憶しておく
  sort = (int *)malloc(sizeof(int));//int型変数の領域を確保

  //標準出力を一行ずつ読み込みながら、EOFが返るまで行数をカウント
  //reallocで確保する領域をその都度増やし、配列へ標準入力を格納

  while((i=scanf("%d",&sort[count])!=EOF)){
    count++;
    //メモリ領域を追加
    sort = (int *)realloc(sort,sizeof(int)*(count+1));
    if(sort == NULL){
      printf("メモリが確保できません\n");
      exit(1);
    }
  }

  printf("与えられた配列のサイズは%dです\nソートを開始します\n",count);

  qsort(sort,count,sizeof(int),(int(*)(const void*, const void*))cmp);

  for(i=0;i<count;i++)
    printf("%d\n",sort[i]);

  free(sort);
  return 0;
}

まず、*pointer は使ってない気がした。-Wall -Werror を使ってると、このあたりはエラーになるはずですよね。

また、cmp 関数のあたりは、 
int cmp(int *n, int *m)
{
  if (*n==*m)
    return 0;
  return (*n>*m)? 1: -1;
}

という風に、二項演算子を使ってもすっきりするかも。

realloc については、こんな感じでしょうか。データ数が 1 つ増えたからといって、容量を 1 つずつ増やすやり方はよくないです。一般に、alloc系のコマンドは時間的な実行コストが高く、フラグメンテーションの問題もあるため、なるべく呼び出し回数が少なくなるようにするのがよいです。以下は、データ個数が倍々で増加するようにした実装です。

/*
  realloc の動作確認用サンプル
  Satofumi KAMIMURA
  $Id$
*/

#include <stdio.h>
#include <stdlib.h>

enum { FIRST_ARRAY_SIZE = 1 };

typedef struct {
  int size;
  int *data;
} array_t;


/* メッセージを出力して終了 */
static void exitResizeError(int size) {
  fprintf(stderr, "data size is too long: %d\n", size);
  exit(1);
}


/* 伸長可能な配列の初期化 */
static void initArray(array_t *array) {
  array->size = FIRST_ARRAY_SIZE;
  array->data = (int *)malloc(sizeof(int) * array->size);
  if (array->data == NULL) {
    exitResizeError(array->size);
  }
}


/* 配列の解放 */
static void deleteArray(array_t *array) {
  free(array->data);
  array->data = NULL;
}


/* 配列の伸長 */
static int resizeData(array_t *array) {
  int resize_size = (array->size <= 0) ? 1 : 2 * array->size;
  int *p = realloc(array->data, sizeof(array->data) * resize_size);
  if (p == NULL) {
    return -1;
  }
  array->data = p;
  array->size = resize_size;

  return 0;
}

int main(int argc, char *argv[]) {
  array_t data;
  int data_count;
  int num;
  int i;

  /* データの読み出し */
  initArray(&data);
  for (data_count = 0; scanf("%d", &num) != EOF; ++data_count) {
    while (data_count >= data.size) {
      if (resizeData(&data) < 0) {
        exitResizeError(data_count);
      }
    }
    data.data[data_count] = num;
  }

  /* ソート処理、他... */

で、こういう処理関数を作ったらライブラリ化して他でも使いまわせるようにするとよいでしょう。できれば、C++ の vector を使うべきですけど。

あと、ソートプログラムは、正常実行時は数値を行毎に出力する仕様だったはずです。エラー以外のためにメッセージを出力するような仕様変更は避けましょう。少なくとも提出するときには。


提出された課題 
kadai2kai.cが前回の注意点を盛り込もうとした物です。が、データが変な風に
入ってしまう駄目プログラムになってしまいました。
直し途中なのですが、期限が来たのでいったん送ります。明日改善してまた送ります

２番はプログラムの変更点としてMakefileを添付しました
自作プログラムは駄目駄目だったのでおいとくとして
結果、
ランダムデータはバブルソートにおいてのみ要素数増加に比例して時間がかかる
様子がうかがえました。
一部ソート済みは同じデータ数で見たときに、全体的に短時間ですんでいるが、
それぞれの手法を比較したときに、バブルが最も短時間で終わる物になっていま
した。

こちらも、明日、自作を加えて訂正した物を送ります


うまく修正できたと思うので送ります。

自作のプログラムをふまえて、検討すると
ランダムデータに関しては最も効率的と思っていたSTLソートよりも、自作の物
の方が優れていました。クイックソートが最も効率的だということなのだと思い
ました
一部ソート済みの物に関しては自作の物はバブルソートに比べ劣るものの、数回
の試行をしたところ、毎回その他二つよりは優れていました。

ソートの速い遅いが気にならない限り、アルゴリズムのオーダー同じなら何を使ってもよいです。また、STL と自作ソートでソートがどう遅いのか、ってあたりを少し詳しくプロファイルしてみましょう。

やったことは、以下のような測定用のコードを追加し、ソート関数だけに注目しての処理時間の計時です。

  // ソート関数の前後に、時刻取得関数を追加
  Uint32 prev = SDL_GetTicks();
  sort(data.begin(), data.end());
  Uint32 now = SDL_GetTicks();
  fprintf(stderr, "stl spent: %d [msec]\n", now - prev);

実行結果はこんな感じです。データは 60000 個のランダムデータを用いました。
計時時間は、多少ばらつくことがあります。

./stl_sort < random_60k.txt > /dev/null
stl spent: 26 [msec]
./user_qsort < random_60k.txt > /dev/null
qsort spent: 27 [msec]

このように、ソートだけ比べるとちょっとだけ STL を使ったソートの方が速いです。全体での実行時間の違いは、データ入力の処理時間に依存しています。今回の STL の実装では、データ読み込みに動的に配列が伸長する仕組みを用いているため、最初に配列を宣言してしまう実装よりは、多少遅くなるのです。

興味があれば、計時に用いた stl_profile.tar.gz をダウンロードして試して下さい。
本格的な profile のやり方は、そのうち勉強しましょう。

/*データのソートプログラム*/
#include <stdio.h>
#include <stdlib.h>


int cmp(const void *x, const void *y);

int main(){
  enum{
    n=65536
      };
  int a[n],i,m;
  for(i=0;i<n;i++)
    {
/*データの入力*/
      if (scanf("%d",&a[i]) == EOF) {
        m=i;
        break;
      }
    }

  qsort(a,m,sizeof(int),cmp);/*クイックソート関数*/
  for(i=0;i<m;i++){



    printf("%d\n",a[i]);
    if(i<m-1 && a[i+1]-a[i]<0){/*昇順になってないならmissを出力し即終了*/
      printf("miss\n");
      exit(0);
    }
  }
  printf("correct\n");/*ここまでプログラムが走ってたらあってる*/
  return 0;
}


int cmp(const void *x, const void *y)/*クイックソート関数の比較関数：昇順*/
{
  return *(int*)x - *(int*)y;
}

qsort(); for() の後の改行の数とか、意味が不明です。人が見るという意味では、改行も重要な情報源ですので、コーディングスタイルにはもう少し気を配ってみましょう。 それ以外のコメントは以下の通り。


提出された課題 
計測時間の比較ですが、自作のクイックソートについてランダムデータに対して
はライブラリのソートに近い性能が出るものの、ほぼ整列されたデータに対して
は最低の性能でした。ピボットの選択方法をいくつか変えて試してみたものの改
善されないかさらに性能が落ちる結果となりました。

そうです。ソートは結構難しいらしいんですよ。あとは、なぜ２種類のデータについて測定させたか、から類推して、「バブルソートはほとんどソート済みのデータに対しては、高速にソートを終了させることもある」とかあったら完璧でした。

提出されたプログラム 
#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

typedef vector<int> IntVector;

void
QuickSort(IntVector& arr, int first, int last)
{
        int x = arr[(first + last) / 2];                // normal code

//      int x = (last == first) ? arr[first] : arr[(random() % (last - first)) + first];
                                                                                        // experimental code 1

/*
        // experimental code 2
        int x1 = arr[first];
        int x2 = arr[(first + last) / 2];
        int x3 = arr[last];

        int x = x1;

        if( ((x1 < x2) && (x2 < x3)) || ((x1 > x2) && (x2 > x3)) ){
                x = x2;
        }
        else if( ((x1 < x3) && (x3 < x2)) || ((x1 > x3) && (x3 > x2)) ){
                x = x3;
        }
*/

        int i = first;
        int j = last;

        for(;;){
                int tmp;

                while(arr[i] < x) ++i;
                while(x < arr[j]) --j;

                if(i >= j) break;

                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;

                ++i;
                --j;
        }

        if(first < i - 1)
                QuickSort(arr, first, i - 1);
        if(j + 1 < last)
                QuickSort(arr, j + 1, last);
}

int
main()
{
        IntVector arr;

        // read cin
        for(;;){
                int num;
                cin >> num;
                if(cin.eof()) break;
                arr.push_back(num);
        }

        // sort
        QuickSort(arr, 0, arr.size() - 1);

        // display result
        int arrSize = arr.size();
        for(int i = 0; i < arrSize; i++){
                cout << arr[i] << endl;
        }

        return 0;
}

指摘箇所が修正されていて、いい感じです。
そのうち、istream_iterator を用いた数値読み出しにも挑戦してみましょう。

以上です。

「第４回、「シューティングゲーム (1)」 へ」
Generated on Mon Apr 13 22:52:06 2009 by  doxygen 1.5.7.1