プログラムの改良　他¶

※本ページは，いくつかの発展課題に関する参考資料となっている．

ソートのパフォーマンスチューニング¶

以下の例では，struct profileは，168バイトの大きさだと分かります:

#include <stdio.h>

#define MAX_STR_LEN  69

struct date {
  int y;
  int m;
  int d;
};

struct profile {
  int         id;
  char        name[MAX_STR_LEN+1];
  struct date birthday;
  char        address[MAX_STR_LEN+1];
  char        *comment;
};

int main()
{
  printf("sizeof(struct profile) = %ld\n", sizeof(struct profile));
}

実行結果（注：計算機環境によって異なる結果が得られる場合がある）:

sizeof(struct profile) = 168

swap()関数内では，3回の代入が起こっていますから，1回のswap()で504バイトの転送です．頻繁に2要素の入れ替え(swap)が起こるソートでは，実行時間に影響が出るかもしれません．

これを回避するにはどうしたらいいでしょうか．答えは，やはりポインタにあります．構造体の実体を移動させるのではなく，それを指すポインタを並べることでソートを実現する方法があります．ポインタどうしの入れ替えは，int型どうしの入れ替えとほぼ同じなので，非常に高速です．

QUIZ（参考）:構造体のサイズ，および，ポインタのサイズは，自分で調べましたね？（ヒント：資料を鵜呑みにしてはいけませんよ．演習1のレポートで，「プログラムは，・・・で動作を確認しているが，・・・」という記述をしていますよね？）

以下の例では，配列要素1つ1つに対応するポインタの配列を用意しています．（参考：教科書K&R「5.6節ポインタ配列：ポインタへのポインタ」）

ポインタの配列は，これまでの実装でも見た記憶がありますね．覚えてますか？

/* これには構造体の実体が入っているのでサイズ大 */
struct profile profile_data_store[MAX_PROFILES];

/* これは ポインタの配列なのでサイズ小 */
struct profile *profile_data_store_ptr[MAX_PROFILES];

void make_profile_shadow(struct profile data_store[],
                         struct profile *shadow[],
                         int size)
{
  int i;
  for (i = 0; i < size; i++)
    shadow[i] = &data_store[i];
}

int main()
{
  /* 初期化 */
  make_profile_shadow(profile_data_store,
                      profile_data_store_ptr,
                      MAX_PROFILES);

  /* 以降 profile_data_store_ptr を使った処理に変更 */
}

こうしておいて，以降では，ポインタの配列profile_data_store_ptrをソートし，ポインタ経由で，実体の配列要素の操作（表示や検索）をするといった方法が考えられます．両者の動作や構造を比較するのは，いいレポートのネタになるでしょう．

バイナリ入出力¶

※教科書K&Rでは，「バイナリファイル (Binary file)」が「2進ファイル」という表現になっています．

前項で構造体のサイズを考えましたが，ファイルサイズの観点から，さらに考えられないでしょうか．

CSVデータは，1行あたり，1つのデータが含まれているはずです．では，1つのCSVデータを格納したファイルのファイルサイズは，構造体のサイズと同じ・・・でしょうか？

ファイル入出力の際に，バイナリ形式での入出力を検討してみることで，これらの問いに対する考えが思い浮かぶことでしょう．

ファイルサイズの調べ方は，緑教科書の『4.1.2 ディレクトリ操作のコマンド』を読めば，書かれています．（注：緑教科書とは，工学基礎実験実習の「大テーマ1」の教科書です．）

バイナリ入出力する際に，最低限必要となることは以下の2つです．

fopen()で開く際，"r"や"w"ではなく，"rb"や"wb"を指定する．

教科書K&R 7.5節「ファイルオープン」 p.196冒頭

教科書K&R 付録B1「入力と出力」 pp. 302-303

fread()やfwrite()を利用して，指定アドレス（＝ポインタ）を起点とした指定バイト数の読み書きをおこなう．

教科書K&R 付録B1.5「直接入出力関数」 pp. 310-311

各関数の使い方は，教科書やmanコマンドを参照してください．

バイナリファイルを閲覧する場合は，hexdumpコマンドを使うとよいでしょう．

二分探索¶

探索にも目を向けてみましょう．

ソートされたデータ構造に対しては，より高速な探索方法が知られています．例えば，二分探索 (Binary search) は，他の講義（浅野ら著, アルゴリズム論, 2.5節 2分探索法）で履修しているのではないでしょうか．

C言語による実装としては：

教科書K&R pp.70-71 に記載されたプログラム
教科書K&R pp.162-163 に記載されたプログラム

が参考になるでしょう．

ライブラリ関数によるクイックソートqsort()関数と同様，bsearch()関数（教科書K&R p.319）も存在します．これらのライブラリ関数を活用すれば，自作の二分探索との比較により，動作テストができそうですね．

なお，qsort()やbsearch()には，関数のポインタ（教科書K&R 5.11節「関数へのポインタ」）を理解する必要があります．

注意点として，二分探索を用いると，名簿管理プログラムの基本仕様を満たした%Fの実装が困難となります．従って，%Fの拡張ではなく，新コマンドとして，適切な仕様を与えたうえで作成した方がよいでしょう．

最後に，表現を変えて，もう一度繰り返します．

「適切にソートされている」ことが前提です．例えば，「id でソートされたデータに対して，name に対する二分探索をする」事はできません．

プログラムの改良 他¶

ソートのパフォーマンスチューニング¶

バイナリ入出力¶

二分探索¶

プログラムの改良　他¶