第3回 演習問題 各種ハッシュ法の順序ハッシュ版の作成
・JAVA, C++で作成する場合もレポート番号は同一となります。
■ 共通
実行・測定環境
hardware: 貸与されたnotePC(3年生、任意のPC or WS、性能記載の必要がある)
OS: Linux
測定時は、当該プログラム以外のプロセスはできるだけ動作しないようにする
・構築関数、探索完成を作成し、下記に示す測定手順・結果に基づき多面的に分析する。
(a) 構築
・下表のような形式で測定、出力する。
------------------------------------------------------------
10万レコード 総探査回数:*******、実行時間: ***.*** 秒
20万レコード 総探査回数:*******、実行時間: ***.*** 秒
30万レコード 総探査回数:*******、実行時間: ***.*** 秒
・・・・・
・・・・・
90万レコード 総探査回数:*******、実行時間: ***.*** 秒
100万レコード 総探査回数:*******、実行時間: ***.*** 秒
------------------------------------------------------------
(b) 探索
・成功探索、不成功探索をそれぞれ連続して行い。100個の総探索時間を測定する。
・開放番地法以外の下記のハッシュ法の探索において、あるキーで探索したときに、そ
のキーの同族のキーを出力した例をレポートに記載する(順序が正しいかどうかの確認
のため)。
・余裕があれば、順序でない元のハッシュ法について、上記の構築・探索について実行し、
両者の比較を行う。
作成済み3a 開放番地−順序ハッシュ法 難易度: B
作成関数: 初期化、格納、探索、メイン関数
キー: 整数値
使用ファイル: integer1MR.dat
測定項目−構築時間: 10万、20万、・・・、100万
−探索時間: 成功探索(100)、不成功探索(100)
作成済み3b 開放番地−順序ハッシュ法 難易度: A
作成関数: 初期化、格納、探索、メイン関数
キー: 文字列
使用ファイル: wordE100KR.dat
測定項目−構築時間: 1万、2万、・・・、10万
−探索時間: 成功探索(100)、不成功探索(100)
作成済み3c 分離連鎖−順序ハッシュ法 難易度: B
作成関数: 初期化、格納、探索、メイン関数
キー: 整数値
使用ファイル: integer1MR.dat
測定項目−構築時間: 10万、20万、・・・、100万
−探索時間: 成功探索(100)、不成功探索(100)
作成済み3d 分離連鎖−順序ハッシュ法 難易度: A
作成関数: 初期化、格納、探索、メイン関数
キー: 文字列
使用ファイル: wordE100KR.dat
測定項目−構築時間: 1万、2万、・・・、10万
−探索時間: 成功探索(100)、不成功探索(100)
作成済み3e 外部−順序ハッシュ法 難易度: B
作成関数: 初期化、格納、探索、メイン関数
キー: 整数値
使用ファイル: integer1MR.dat
測定項目−構築時間: 10万、20万、・・・、100万
−探索時間: 成功探索(100)、不成功探索(100)
作成済み3f 外部−順序ハッシュ法 難易度: B
作成関数: 初期化、格納、探索、メイン関数
キー: 文字列
使用ファイル: wordE100KR.dat
測定項目−構築時間: 1万、2万、・・・、10万
−探索時間: 成功探索(100)、不成功探索(100)
3i 外部−順序ハッシュ法と非順序ハッシュ法の性能比較 難易度: B
作成関数: 初期化、格納、探索、メイン関数
キー: 整数値
使用ファイル: integer1MR.dat
測定項目−構築: 10万、20万、・・・、100万
−総探索時間: 成功探索(1000)、不成功探索(1000)
・非順序の外部ハッシュ法と順序外部ハッシュ法について、以下を比較する。
総探索時間(成功探索、不成功探索)
・探索については、平均探索時間を算出する(成功探索、不成功探索)。
・上記について、折れ線グラフで表す(両者の比較対象)。
3j 外部−順序ハッシュ法と非順序ハッシュ法の性能比較 難易度: B
作成関数: 初期化、格納、探索、メイン関数
キー: 文字列
使用ファイル: wordE100KR.dat
測定項目−構築: 1万、2万、・・・、10万
−総探索時間: 成功探索(100)、不成功探索(100)
・非順序の外部ハッシュ法と順序外部ハッシュ法について、以下を比較する。
総探索時間(成功探索、不成功探索)
・探索については、平均探索時間を算出する(成功探索、不成功探索)。
・上記について、折れ線グラフで表す(両者の比較対象)。
3k Javaでの外部−順序ハッシュ法と非順序ハッシュ法の実装性能比較 難易度: A+
作成関数: 初期化、格納、探索、メイン関数
キー: 文字列
使用ファイル: wordE100KR.dat
測定項目−構築時間: 1万、2万、・・・、10万
−総探索時間: 成功探索(1000)、不成功探索(1000)
・非順序の外部ハッシュ法と順序外部ハッシュ法について、以下を比較する。
構築時間、総探索時間(成功探索、不成功探索)
・探索については、平均探索時間を算出する(成功探索、不成功探索)。
・上記について、折れ線グラフで表す(両者の比較対象)。
3l 拡張ハッシュ法の順序ハッシュ化 難易度: A
作成関数: 初期化、格納、探索、メイン関数
キー: 文字列
使用ファイル: integer1MR.dat
ハッシュ関数: 先頭ビット列(拡張ハッシュ-ディレクトリー)
拡張ハッシュ法用ハッシュ関数
・測定項目−構築時間(クイックソートの比較)
−総探索時間: 全探索(分離連鎖法と比較)
初期値の次数d = 16、バケットサイズ(BS = 256, 512)とする。この条件の下で、拡張ハッシュ法を構築する。その際、テキストの実装とは異なり、バケットは単純な配列とする。バケット内では挿入法を用いてキーを整列させる。追加関数に対応させるため、バケット内の探索は二分探索法(または逐次探索法)を用いる。