記号表の探索のアルゴリズム
liner search
表の先頭から逐次的に照合していく
表に$ n件あれば、
登録されている場合は、検索には平均$ \frac{n+1}{2}かかる
登録されていない場合は、$ nかかる
効率は悪いが、実装が容易
表の作成時の並べ方は任意
ex. 登録された順
$ nが小さければそれほど問題にならない
sentinel
探すものがxだとして、探す方向から見て一番最後にxを追加してから探す
もともとテーブルにxがあろうとなからろうと必ず到達するので、「テーブルを最後まで探したか」を判定する必要がなくなり、その分だけ速くなるらしい
最初に追加するコストが低い前提かmrsekut.icon
テーブルの作成時に何らかのものでソートする
探すときは表の真ん中と比較していく
挿入時は、↑探す処理を一通りやって表内にないことを確認したのちに、該当の場所に挿入する
その際に、後ろを全て一つずつずらす必要がある
もしくはツリー構造にしてポインタを管理する
表に$ n件あれば、検索には$ \log_2{(n)}+1かかる
hash method
f :: 変数名を数値化したもの -> 表のindex値的な
index値はハッシュ値？
そうだけどシンプルなアルゴリズムで生成できる
『コンパイラとバーチャルマシン』.icon p.70で紹介されているのは、fの引数を表の大きさに近い素数$ pで割った剰余をfの戻り値とする
code:f
f:: int -> int
f v = v % p
挿入時
そのindexを見たとき3パターン考えられる
①xがすでに入ってた
上書きする
②何も入っていなかった
普通に登録する
③x以外のなにかが入っていた
探索時
上の挿入時の①の場合のみ探索成功
実用的には記号表とハッシュ表は別に用意したほうが扱いやすい ref 『コンパイラ 作りながら学ぶ』.icon p.111 参考