第1回 演習問題 外部ハッシュ法の実装・性能評価

・JAVA, C++で作成する場合もレポート番号は同一となります。
■ 共通
実行・測定環境
 hardware: 貸与されたnotePC(3年生、任意のPC or WS、性能記載の必要がある)
 OS: Linux
測定時は、当該プログラム以外のプロセスはできるだけ動作しないようにする
・構築関数、探索完成を作成し、下記に示す測定手順・結果に基づき多面的に分析する。
(a) 構築
・下表のような形式で測定、出力する。
------------------------------------------------------------
  10万レコード  総探査回数:*******、実行時間: ***.*** 秒
  20万レコード  総探査回数:*******、実行時間: ***.*** 秒
  30万レコード  総探査回数:*******、実行時間: ***.*** 秒
   ・・・・・
   ・・・・・
  90万レコード  総探査回数:*******、実行時間: ***.*** 秒
 100万レコード  総探査回数:*******、実行時間: ***.*** 秒
------------------------------------------------------------

(b) 探索
・成功探索、不成功探索をそれぞれ連続して行い。100個の総探索時間を測定する。
・開放番地法以外の下記のハッシュ法の探索において、あるキーで探索したときに、そ のキーの同族のキーを出力した例をレポートに記載する(順序が正しいかどうかの確認 のため)。


1g 同族連作法と外部ハッシュ法の性能比較  難易度: B
作成関数:   初期化、格納、探索、メイン関数
 キー:   整数値
 使用ファイル: integer10MR.dat
 測定項目 (a) 構築時間: 100万、200万、・・・、1000万
        (b) 総探索時間: 成功探索(10000)、不成功探索(10000)
・それぞれについて構築時間、総探索時間(成功探索、不成功探索)を測定する
実行時間の正確な計測を規すため、最初に元データ集合、成功探索用整数集合、不成功探索用整数集合用に、計3つの配列を動的に生成する。
(1)ファイルから整数値を読み込み、元データ集合用の配列に格納する。
(2)rewindし、先頭の任意データをから読みし、その後10000個の整数値を成功探索用配列に格納する。その際、1つの整数値に当該整数集合の最大値(integer1MS.dat)の末尾の要素の値を加算し、不成功探索用配列に格納する。
(a) については、元データ集合用の配列から読み込み同族連鎖法、外部ハッシュ法、それぞれ構築する。このとき、 10万、20万、・・・、100と、10万要素単位で、構築時間を計測する。結果として、2つの表が得られる。この表から1つの折れ線グラフを作成する。
(b)については、総探索時間から平均探索時間を算出する(成功探索、不成功探索)。、計4つのデータが得られる。