第12回では，以下の項目に関して学ぶ．

  1. 線形探索
  2. 2分探索
  3. ハッシュ法

課題のソースコードのテンプレート:

課題1: 配列を用いた線形探索

データの集まりから，特定のデータを探し出すことを探索(search)という．その際，探索において着目する項目をキー(key)と呼ぶ．たとえば，検索キーを学籍番号とすると，それに一致するキーを持つデータを見つけ出すことが考えられる．この場合の検索条件は，「一致するキーを持つ」である．

ここでは，arraytable-common.h で定義されている構造体の要素がランダムに並んでいる配列に対して．それぞれの要素に対して検索条件の成立を順番に調べる線形探索(linear search)を考える．

struct data {
    int key;
    char value;
};
key は検索キー，value は格納されているデータを指す．

また，検索対象の要素の集まりは，arraytable-common.h で定義されている以下の構造体で管理されている． 

struct table {
    struct data **data;
    int size;
    int num;
};
data は struct data の要素へのポインタを格納した配列( struct data[] )のポインタを指す(ポインタのポインタである)．size は格納できる要素の最大数，num は現在格納されている要素の数を指す．テーブルが空の場合は，num は 0 とする．

いま，配列を用いた線形探索を実現するために，以下に示す2つの関数を用意する．

(1) 格納できる要素の最大数を size とした空のテーブルを生成する．
struct table *create_table(int size);
(2) テーブル table に格納されている要素に画面に表示する．
void print(struct table *table);

これらの関数を利用するためには，arraytable-common.h をインクルードし，arraytable-check.o をリンクすればよい．

配列に格納された要素に対する線形探索を実現するために，以下に示す3つの関数を持つソースコード prog12-1.c を作成する．

(1) table に格納されているデータから，検索キー key を持つ要素を見つける．データが見つからなかった場合は NULL を返す．
struct data *search_array(struct table *table, int key);
(3) table に要素 data を追加する．すでに格納されている要素と同一の検索キーを持つ要素は追加できない．追加に成功した場合は 1，失敗した場合は 0 を返す．
int insert_array(struct table *table, struct data data);
(3) table から検索キー key に一致する要素を削除する．削除に成功した場合は 1，失敗した場合は 0 を返す．
int delete_array(struct table *table, int key);

上記の3つの関数を持つ prog12-1.c を作成せよ．

本課題では，テスト関数 test1() がすでに用意されている．さまざまな配列に対して，要素の探索，追加，削除の振る舞いを確認するテストコードを prog12-1.c に追加せよ．

課題2: 配列を用いた2分探索

arraytable-common.h で定義されている構造体の要素がキーの値でソートされている配列に対して，検索条件の成立を効率的に調べる2分探索(binary search)を考える．

要素を格納する構造体 struct data と，この構造体の要素を格納するテーブル struct table は課題1と同じである．

配列に格納された要素に対する2分探索を実現するために，以下に示す3つの関数を持つソースコード prog12-2.c を作成する．

(1) table に格納されているデータから，検索キー key を持つ要素を見つける．データが見つからなかった場合は NULL を返す．
struct data *search_binary(struct table *table, int key);
(3) table に要素 data を追加する．すでに格納されている要素と同一の検索キーを持つ要素は追加できない．追加に成功した場合は 1，失敗した場合は 0 を返す．
int insert_binary(struct table *table, struct data data);
(3) table から検索キー key に一致する要素を削除する．削除に成功した場合は 1，失敗した場合は 0 を返す．
int delete_binary(struct table *table, int key);

上記の3つの関数とテストコードを含む prog12-2.c を作成せよ．

課題3: ハッシュ法(チェイン法)を用いた探索

データを格納する位置を単純な計算で求めることで，探索，追加，削除を効率的に行う方法にハッシュ法(hashing)がある．もとの検索キーから計算により求めた値をハッシュ値と呼ぶ．

ハッシュ法では，一定の大きさの配列を用意し，ハッシュ値を添え字として配列にデータを保持する要素を格納する．たとえば， 検索キー key を 7 で割った余りをハッシュ値とする場合，大きさ7の配列 a[0]〜a[6] を用意すればよい．この場合，キーの値が 10 の要素は a[3]，キーの値が 14 の要素は a[0] に格納される．

このような方法では，キーの値が 10 と 17 を持つデータのハッシュ値はどちらも 3 となる．このようにハッシュ値が重複することを衝突と呼ぶ．衝突する2つのデータを同時に 1つの領域 (この場合，a[0] )に格納することはできない．そのため，ハッシュ法では，衝突に対処することが必須である．

ここでは，同一のハッシュ値を持つ要素を鎖状に線形リストで管理するチェイン法(chaining)を取り上げる．チェイン法はオープンハッシュ法とも呼ばれる．

チェイン法で実現されたハッシュの例を図12.1に示す．


図12.1: チェイン法で実現されたハッシュの例

ハッシュにより格納される要素の構造体は，chaintable-common.h において，以下のように定義されている． 

struct chain_data {
    int key;
    char value;
    struct chain_data *next;
};
key は検索キー，value は格納されているデータを指す．next は，チェインにおける次の要素を指すポインタである．

検索対象の要素の集まりは，chaintable-common.h で定義されている以下の構造体で管理されている． 

struct chain_table {
    struct chain_data **data;
    int size;
    int num;
};
この構造体は，課題1および課題3と同じである．

いま，チェイン法を実現するために，以下に示す2つの関数を用意する．

(1) 格納できる要素の最大数を size とした空のテーブルを生成する．
struct chain_table *create_chain_table(int size);
(2) テーブル table に格納されている要素に画面に表示する．
void print_chain(struct chain_table *table);

これらの関数を利用するためには，chaintable-common.h をインクルードし，chaintable-check.o をリンクすればよい．

チェイン法による探索を実現するために，以下に示す3つの関数を持つソースコード prog12-3.c を作成する．

(1) table に格納されているデータから，検索キー key を持つ要素を見つける．データが見つからなかった場合は NULL を返す．
struct chain_data *search_chain(struct chain_table *table, int key);
(3) table に要素 data を追加する．すでに格納されている要素と同一の検索キーを持つ要素は追加できない．追加に成功した場合は 1，失敗した場合は 0 を返す．
int insert_chain(struct chain_table *table, struct chain_data data);
(3) table から検索キー key に一致する要素を削除する．削除に成功した場合は 1，失敗した場合は 0 を返す．
int delete_chain(struct chain_table *table, int key);

上記の3つの関数とテストコードを含む prog12-3.c を作成せよ．
prog12-3.c では，ハッシュ値を求める関数 hash(int key, int size) をあらかじめ用意してある．ハッシュ値の計算方法を変えてもよい．

課題4: ハッシュ法(オープンアドレス法)を用いた探索

ハッシュ法において，生得が発生した場合にハッシュ値の再計算することで，配列内の空いている領域を探し出す方法がオープンアドレス法(open addressing)である．

要素を格納する構造体 struct data と，この構造体の要素を格納するテーブル struct table は課題1と同じである．

チェイン法による探索を実現するために，以下に示す3つの関数を持つソースコード prog12-4.c を作成する．

(1) table に格納されているデータから，検索キー key を持つ要素を見つける．データが見つからなかった場合は NULL を返す．
struct data *search_open(struct table *table, int key);
(3) table に要素 data を追加する．すでに格納されている要素と同一の検索キーを持つ要素は追加できない．追加に成功した場合は 1，失敗した場合は 0 を返す．
int insert_open(struct table *table, struct data data);
(3) table から検索キー key に一致する要素を削除する．削除に成功した場合は 1，失敗した場合は 0 を返す．
int delete_open(struct table *table, int key);

上記の3つの関数とテストコードを含む prog12-4.c を作成せよ．
prog12-4.c では，ハッシュ値を求める関数 hash(int key, int size) と ハッシュ値を再計算する関数 rehash(int key, int size) をあらかじめ用意してある．これらの計算方法を変えてもよい．

課題5: 探索時間の比較

課題1〜3で作成した4種類の探索プログラムの実行時間を計測し，その結果について比較して考察せよ．

実行時間を計測するには，以下の6つの関数 

struct data *search_array(struct table *table, int key);

int insert_array(struct table *table, struct data data);

struct data *search_binary(struct table *table, int key);

int insert_binary(struct table *table, struct data data);

struct chain_data *search_chain(struct chain_table *table, int key);

int insert_chain(struct chain_table *table, struct chain_data data);
のコードを prog12-1.c，prog12-2.c，prog12-3.c から prog12-5.c にコピーすればよい．


上記の6つの関数のコードをコピーして prog12-5.c を作成して，実行時間を計測せよ．

探索対象の要素の数( SMALL_NUM，MEDIUM_NUM，LARGE_NUM の値)，探索の実行回数(SEARCH_TRIALS の値)をいろいろ変更して，実行時間を計測するとよい．

また，prog12-5.c 内の scramble(struct data *data, int num) とscramble_chain(struct chain_data *data, int num) が探索対象の要素をかき混ぜる関数である．この関数の呼出しをコメントアウトすることで，テストデータは順番に並んだ要素となる．かき混ぜることで実行時間に差が出るかどうかを確認せよ．

Go to Top