実験で確認すべきこと

実験１で確認し，考察すべき内容
＜理論に関する補足＞
線形探索アルゴリズムの計算量は O(nm)であるが，テキスト p35 で説明されているよう
に，文字列長 m の上限を 32 に固定しているのでこの場合の計算量は現実には O(n) で
ある．したがって，データ数 n に比例した時間がかかると考えられる．
＜具体的に実験で行うべきこと＞

実験では 4 種類の長さの異なるデータファイルが用意されているので，これらを使っ
て探索時間が O(n) になっていることを確認する．

ただし，1 回の探索ではすぐに終わってしまって時間の測定が難しい．そこで同じ探索
を何度も繰り返して元の時間を推定する．

実験の Web サイト（ヒントのページ）では 1000 回繰り返すよう指示してあるが，こ
の回数（1000）は時間を比較しやすいよう自分で自由に決めてよい．
＜レポートに書くべきこと＞

測定実験の結果（探索にかかった時間）を「ソーティングアルゴリズム」の時と同様
に表と図（グラフ）を描く．（下の例を参照）
表１．線形探索法での探索時間
（文字列 zoozoo を探索）
n
探索時間（秒）※1000 回分
100000
0.970
200000
1.920
300000
2.830
400000
4.120
図１．線形探索法での探索時間
（文字列 zoozoo を探索）

考察では実データを使って O(n)であることの考察を行うこと．例えば，「データ数が
100000 から 200000, 300000, 400000 と 2, 3, 4 倍になると，探索時間は 0.970 秒か
ら 1.920 秒，2.830 秒，4.120 秒となり，それぞれ 1.98 倍，2.92 倍，4.24 倍となって
いる．つまり，探索時間も約 2,3,4 倍となっており，このことから計算量は O(n)であ
ることがうかがえる．」といった具合である．
実験 2 で確認すべき内容
＜理論に関する補足＞
ハッシュ法の場合，ポインタ配列の長さを L とした場合，データのハッシュ値が均等に分
散すれば一つの要素に割り当てられるデータは平均して n/L 個となる．つまり，その個数
分だけ文字列の照合を行えばよいので O(n/L) となる．つまり，L が大きくなるにつれて
O(1)へ近づいていき，逆に L が小さくなるにつれて O(n)へ近づいていくということになる．
＜具体的に実験で行うべきこと．考察すべきこと．＞
実験では各データに対して L を変えていきながら探索時間がどのように変化していくかを
観測し，考察する（以下は例．n=100000, 200000 のみ書いているが，その他も同様）．そ
して，線形探索法との速度の比較も考察で述べる．
表２．ハッシュ法での探索時間
（文字列 zoozoo を探索）
N
100000
20000
L
探索時間（秒）
10
0.140
20
0.070
30
0.060
40
0.040
50
0.030
60
0.030
70
0.030
80
0.020
90
0.020
100
0.010
10
0.610
20
0.130
30
0.100
40
0.080
50
0.070
60
0.060
70
0.050
80
0.040
90
0.040
100
0.030
図２．ハッシュ法での探索時間
（文字列 zoozoo を探索）

Download Report