記号表の探索のアルゴリズム

記号表の構造による

表の先頭から逐次的に照合していく

表にn件あれば、

登録されている場合は、検索には平均\frac{n+1}{2}かかる

登録されていない場合は、nかかる

効率は悪いが、実装が容易

表の作成時の並べ方は任意

ex. 登録された順

nが小さければそれほど問題にならない

番兵を使うという工夫もある

探すものが x だとして、探す方向から見て一番最後に x を追加してから探す

もともとテーブルに x があろうとなからろうと必ず到達するので、「テーブルを最後まで探したか」を判定する必要がなくなり、その分だけ速くなるらしい

最初に追加するコストが低い前提か

テーブルの作成時に何らかのものでソートする

例えば文字コードとか

探すときは表の真ん中と比較していく

挿入時は、↑探す処理を一通りやって表内にないことを確認したのちに、該当の場所に挿入する

その際に、後ろを全て一つずつずらす必要がある

もしくはツリー構造にしてポインタを管理する

表にn件あれば、検索には\log_2{(n)}+1かかる

関数型スタイルで永続的データ構造に実装する場合はこれが向いている

ハッシュ関数を使う

f :: 変数名を数値化したもの -> 表のindex値 的な

index値はハッシュ値？

そうだけどシンプルなアルゴリズムで生成できる

p.70で紹介されているのは、fの引数を表の大きさに近い素数pで割った剰余をfの戻り値とする

挿入時

記号 x からハッシュ関数でindexを求める

そのindexを見たとき3パターン考えられる

① x がすでに入ってた

上書きする

②何も入っていなかった

普通に登録する

③ x 以外のなにかが入っていた

開番地法や連鎖法を用いてindexを求め直す

探索時

上の挿入時の①の場合のみ探索成功

実用的には記号表とハッシュ表は別に用意したほうが扱いやすい ref p.111

命令形スタイルで刹那的データ構造に実装する場合はこれが向いている

参考

タイガーブック 5章