Report for Chap.1

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

■ 実験用データ
　整数集合:　　集合の濃度(要素数): 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個までの要素の探索時間
■同族リンク番地数: 探索時に辿られるリスト内の要素数の総和。例えば、ハッシュ表内に5つのリストあり、それぞれのリストの長さが7, 10, 8, 5, 20のとき、最初の1000回の探索時に、それぞれ4, 3, 5, 3, 10とすると、25となる(当該アドレスにおける、すでに格納されているキーと新たに格納するキーのハッシュ値の重複が発生した場合に張られるリンク先のアドレスの数)。

----------------------------------------------------------------
　　　　　　　同族連鎖法による探索操作
　　探索要素数　同族リンク番地数　　探索時間(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) 探査回数、実行時間等、測定結果をプログラムの最後に出力する。