演習問題 第2回 ハッシュ法Ⅱ(2014、2016年度)


■ 実験用データ
 整数集合:  集合の濃度(要素数): 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 開放番地法と同族連鎖法の探索関数の効率性の比較
(0) 探索用要素集合の配列を静的に宣言する。この配列の大きさは0.1Uで、型は上記指定のとおり。
(1) 指定されたファイルを読み込み、同族連鎖法でハッシュ表を生成(store関数)する。生成関数で使用されるハッシュ関数は除算法で除数の値は上記記載のとおり。また、探査方式は線形探査法でハッシュ増分Cの値は上記記載のとおりである(演習課題1aと同一)。
(2)次に、ファイルポインターを先頭に戻す(rewind)。
(3) [前半のグループ]101000まで空読みし、101001から0.1U個取り出し、(0)で作成した配列に格納する。
  [後半のグループ] 81000まで空読みし、81001から0.1U個取り出し、(0)で作成した配列に格納する。
(3)この探索用要素配列(成功探索)から要素を取り出し、(1)で構築した同族連鎖法によるハッシュ表に対して探索する。この探索(search)を0.1U回行うが、0.01U毎に以下の項目を計測し、print出力する。
 (a)総探査回数、(b)同族リンク番地数 (c)0.01〜0.1U個までの要素の探索時間

----------------------------------------------------------------
       同族連鎖法による探索操作
  探索要素数 同族リンク番地数  探索時間(msec)
  0.01U         *******     *******    ***.***
  0.02U     ・・     *******     *******     ***.***
  0.03U     ・・     *******     *******     ***.***
   ・・・・・
   ・・・・・
  0.09U          *******     *******    ***.***
  0.1U          *******     *******     ***.***
----------------------------------------------------------------
 上記と同様の計測を解放番地法についても行う。
----------------------------------------------------------------
       開放地鎖法による探索操作
  探索要素数 総探査回数  探索時間(msec)
  0.01U         *******     *******    ***.***
  0.02U     ・・     *******     *******     ***.***
  0.03U     ・・     *******     *******     ***.***
   ・・・・・
   ・・・・・
  0.09U          *******     *******    ***.***
  0.1U          *******     *******     ***.***
----------------------------------------------------------------
これら2つの計測結果をレポートに記載し、様々な観点から分析せよ。なお、提出実行形式(exe)ファイルは、同族連鎖法の生成-探索main関数のexeファイルだけでよい





◆演習問題プログラム作成における注意事項

下記の要件を必ず満たすようにプログラムを作成せよ。

 (1) 最初に読み込むファイル名は絶対パスとしてmainプログラム中で記述し、コマンドライン上の引数による指定、およびリダイレクトによる入力指定はしないこと。

 例.char infile[80] = "/home/algorithm_data/texte.dat" ;

 (2) 探査回数、実行時間等、測定結果をプログラムの最後に出力する。