と
第2回 演習問題
第2回 演習問題 拡張ハッシュ法の作成
実行・測定環境
hardware: 貸与されたnotePC(3年生、任意のPC or WS、性能記載の必要がある)
OS: Linux
測定時は、当該プログラム以外のプロセスはできるだけ動作しないようにする
■ 2a, 2b 共通
・下記に示す、測定手順・結果に基づき多面的に分析する。
(1) 構築
・下表のような形式で測定、出力する。
------------------------------------------------------------
10万レコード 総探査回数:*******、実行時間: ***.*** 秒
20万レコード 総探査回数:*******、実行時間: ***.*** 秒
30万レコード 総探査回数:*******、実行時間: ***.*** 秒
・・・・・
・・・・・
90万レコード 総探査回数:*******、実行時間: ***.*** 秒
100万レコード 総探査回数:*******、実行時間: ***.*** 秒
------------------------------------------------------------
(2) 探索
・成功探索、不成功探索をそれぞれ連続して行い。100個の総探索時間を測定する。
作成済み2a 削除関数の作成 難易度: A+>
作成関数: 初期化、格納、探索、削除、メイン関数
キー: 整数値
使用ファイル: integer1MR.dat
作成済み2b 削除関数の作成 難易度: A+
作成関数: 初期化、格納、探索、削除、メイン関数
キー: 文字列
使用ファイル: wordE100KR.dat
2c 同族連鎖法と拡張ハッシュ法の比較 難易度: B
作成関数: 初期化、格納、探索、メイン関数
キー: 整数値
使用ファイル: integer10MR.dat
ハッシュ関数: 除算法(同族連鎖法)
先頭ビット列(拡張ハッシュ-ディレクトリー)
除算法(拡張ハッシュ-ブロック: 残りのビット列の整数値に対して)
拡張ハッシュ法用ハッシュ関数
次数(d)の初期値: 12
ブロックサイズ: 128、除数: 127(ブロック内探索時のハッシュ関数の除数)
測定項目: 全成功探索の総探索回数、全不成功探索の総探索回数
全成功探索の平均探索時間、全不成功探索の平均探索時間
(1) 使用ファイルを読み込み、個々の要素を配列a(成功探索用)に、このとき個々の要素に定数を加算した値を配列b(不成功探索用)に格納する。
(2) 配列aから同族連鎖法の格納関数によりの同族連鎖法のハッシュ表、および拡張ハッシュ法の格納関数によりハッシュ表(およびバケット)に格納する。
(3a) 配列aを使用し、同族連鎖法の探索関数により同族連鎖法のハッシュ表に対して探索を行う(全成功探索)。
(3b) 配列bを使用し、同族連鎖法の探索関数により同族連鎖法のハッシュ表に対して探索を行う(全不成功探索)。
(4a) 配列aを使用し、拡張ハッシュ法に対して探索を行う(全成功探索)。
(3a)〜(4b)に際しては、それぞれ探索の開始時と終了時の時刻、およびその差を出力表示・計測し全探索時の総探索時間を測定する(これを1Mで除せば、平均探索時間が測定できる)。
作成済み2d 同族連鎖法と拡張ハッシュ法の比較 難易度: B
作成関数: 初期化、格納、探索、メイン関数
キー: 文字列
使用ファイル: wordE100KR.dat
測定項目: 全成功探索の平均探索時間、全不成功探索の平均探索時間
・2cと同様に行う
2e 外部ハッシュ法と拡張ハッシュ法の比較 難易度: B
作成関数: 初期化、格納、探索、メイン関数
キー: 整数値
使用ファイル: integer10MR.dat
ハッシュ関数: 先頭ビット列(拡張ハッシュ-ディレクトリー)
除算法(拡張ハッシュ-ブロック: 残りのビット列の整数値に対して)
拡張ハッシュ法用ハッシュ関数
次数(d)の初期値: 12(2の12乗 = 4096)
ブロックサイズ: 128、除数: 127(ブロック内探索時のハッシュ関数の除数)
測定項目: 全成功探索の総探索回数、全不成功探索の総探索回数
全成功探索の平均探索時間、全不成功探索の平均探索時間
(1) 使用ファイルを読み込み、個々の要素を配列a(成功探索用)に、このとき各要素に定数を加算した値を配列b(不成功探索用)に格納する。
(2) 配列aから読み込み、外部ハッシュ法および拡張ハッシュ法の格納関数により、それぞれのハッシュ表に格納する。
(3) 配列a(成功探索用要素集合)から読込み、外部ハッシュ法、拡張ハッシュ法に対して、全探索を行う(全成功探索)。
(4) 配列b(不成功探索用要素集合)から読込み、外部ハッシュ法、拡張ハッシュ法に対して、全探索を行う(全不成功探索)。
(3)--(4)に際しては、それぞれ探索の開始時と終了時の時刻、およびその差を出力表示・計測し全探索時の総探索時間を測定する(これを1Mで除せば、平均探索時間が測定できる)。
2f 外部ハッシュと拡張ハッシュ法の比較 難易度: B
作成関数: 初期化、格納、探索、メイン関数
キー: 文字列
使用ファイル: wordJ1MR.dat
測定項目: 全成功探索の平均探索時間、全不成功探索の平均探索時間
・2eと同様に行う
作成済み2h. Javaでの拡張ハッシュ法の実装 難易度: A+
作成関数: 初期化、格納、探索、メイン関数
キー: 文字列
使用ファイル: wordE100KR.dat
(C-0) Cで書かれたテキストの拡張ハッシュ法の上記関数を作成する。
(C-1) 上記ファイルを通常の配列(文字列ポインター配列)および拡張ハッシュ法に格納する下記のデータ構造に格納する。
(C-2) 配列内の全要素(全文字列)をキーとして、拡張ハッシュ法に対して全探索を行い、そのときの総探索時間を測定する。この値から平均探索時間を算出する。
(J-0) Cで書かれたテキストの拡張ハッシュ法の上記関数をJavaで実装する。
(J-1) 上記ファイルを通常の配列(文字列ポインター配列)および拡張ハッシュ法に格納する下記のデータ構造に格納する。
(J-2) 配列内の全要素(全文字列)をキーとして、拡張ハッシュ法に対して全探索を行い、そのときの総探索時間を測定する。この値から平均探索時間を算出する。
上記の測定時間をExcelで編集し、表、グラフを作成し、分析せよ。