Report for Chap.2(2017, 2019)

演習課題第2回ハッシュ法Ⅱ(2017、2019年度)

■ 実験用データ
　整数集合:　　集合の濃度(要素数): 1,000,000、　キーの型: 整数、　　ファイル: integer1MS.dat
　文字列集合: 集合の濃度(要素数): 100,000、　　キーの型: 文字列、　ファイル: wordE100KS.dat
　　　(文字列集合: 英単語集合)

■ 計測値出力単位
整数集合　　　U = 100,000　　(要素数の1/10)
英単語集合　 U = 10,000　　　(要素数の1/10)

■ 集合、パラメーター設定
・学籍番号の最下位桁の値によって、演習問題に対する集合、パラメーター(対象集合、除数、線形探査法のハッシュ増分(CONSL)、等)が異なります)
　　　　前半のグループ　　　　後半のグループ
　　　　集合: 整数集合　　　　集合: 文字列集合
番号　　除数　　CONSL　　　除数　　CONSL
　　0: 　999983　　19　　　　　99991　　19
　　1: 　999983　　23　　　　　99989　　23
　　2: 　999979　　29　　　　　99971　　29
　　3: 　999979　　31　　　　　99929　　31
　　4: 　999961　　37　　　　　99929　　37
　　5: 　999961　　41　　　　　99923　　41
　　6: 　999959　　43　　　　　99907　　43
　　7: 　999959　　47　　　　　99901　　47
　　8: 　999953　　53　　　　　99881　　53
　　9: 　999953　　59　　　　　99877　　59

■ 留意事項
・誤った集合、誤った設定値でのレポートは受理されません。

2a 二分探索法と同族連鎖法の探索関数の効率性の比較
　上記で指定されたファイル(集合)を読み込み、二分探索法(アルゴリズム論Ⅰ、第3回)を用いた探索を行うmain関数、、および同族連鎖法によるハッシュ表の生成・探索を行うmain関数を作成する。
　後者は占有率αを1.0とし、探査方式は線形探査法を用いる。ハッシュ関数の除数および探査法のハッシュ増分CONSLは上記指定のとおり)。
　探索関数のキー集合としては、生成時の集合の同一とする(テキスト掲載main関数と同様にrewind文を利用すればよい)。したがって、探索は成功探索だけとなる。
　探索においては、総照合回数(2分探索法)、総探査回数(同族連鎖法)と連続探査時間を測定し、以下のように出力する。
2分探索法
　　　　　　　　総比較回数　　　連続探索時間
　　 1U　　　・　・　　・　・　　　　　・　・
　　 2U　　　・　・　　・　・　　　　　・　・
　　　　　　　　・　・　・　・　　　　　　・　・
　　　　　　　　・　・　・　・　　　　　　・　・
　　 9U　　　・　・　　・　・　　　　　・　・
　　10U　　　・　・　　・　・　　　　　・　・

同族連鎖法
　　　　　　　衝突キー総数　総探査回数　　　連続探索時間
　　 1U　　　・　・　　・　・　　　　　・　・
　　 2U　　　・　・　　・　・　　　　　・　・
　　　　　　　　・　・　・　・　　　　　　・　・
　　　　　　　　・　・　・　・　　　　　　・　・
　　 9U　　　・　・　　・　・　　　　　・　・
　　10U　　　・　・　　・　・　　　　　・　・

(総探査回数: 1つのキーの探索において、ハッシュ関数そのものの探索(1回)は含めない)。
　結果として、上記のような測定データが得られる(2分探索法main関数の実行、同族連鎖法main関数の実行)。
　上記の測定結果を様々な観点、例えば前回の問題(1a)の分析結果と比較対照するなど、多角的に分析せよ。
　なお、提出exeファイルは、同族連鎖法main関数のexeファイルだけでよい。