[基礎]探索アルゴリズム
2007年02月20日（火）18:36｜谷口
谷口です。
前回のソートアルゴリズムと同様基礎編ということで、探索アルゴリズムについてお話します。 探索アルゴリズムを知らないことはプログラマにとって致命的とも言えるくらい重要な知識です。 もちらん、知らず知らずの内に身につけている人も多いことでしょう。
探索とは
ある条件を満たす要素や組合せを発見することです。
例えば、「サイズnの配列の中から最大の要素を見つける」とか、「ある関数が真を返すような変数の組を見つける」といった感じです。
探索アルゴリズムの一例
- 線形探索
- 二分探索
- ハッシュ法
- 深さ優先探索
- 幅優先探索
- 局所探索法
- 分枝限定法
- etc
データ構造やどういう条件のどんなものを見つけたいかによって、 柔軟にアルゴリズムを選択する必要があるのですが、 今回は最も基本的な、「ある条件に一致する要素」の探索について説明します。
線形探索
誰でも容易に思いつく方法ですが、意外とこの壁を破るのが難しかったりします。 1. i = 0をセット 2. 要素列のi番目と目的の値を比較し、一致するかi=nなら終了、そうでなければ3へ。 3. i = i + 1として2へ。
要素列の長さをnとすると、計算量はO(n)となります。 データベースをかじってる人ならお分かりかと思いますが、今もなおO(n)問題と呼ばれるほどこの壁は厚いです。 この方法をベースに、条件・データの傾向などを加味することで効率化を図っているのが、次から紹介する手法となります。
二分探索
線形探索より高速ですが、対象となる要素列がソート済みであることが動作条件となります。以下に手順を示します（データは昇順ソート済み）
- 要素列の中央の値と探したい値を比較し、等しいあるいは要素列の要素数が1つなら終了、そうでなければ2へ
- 探したい値の方が、要素列の中央の値より大きければ後半部分を、小さければ前半部分を要素列として1に戻る。
計算量はO(logn)と高速なため、データベースなどの同じ対象から何度も探索をするようなケースでは、この探索が有効となります。ただし、ソートアルゴリズムの際も触れていますが、ソートの計算量が O(nlogn)であるため、1回の探索のためにソートをするのでは、線形探索に負けてしまいます。
ハッシュ法
ハッシュ関数によってハッシュ値（キー）を生成し、得られたハッシュ値に依存する場所に順次データを格納します。取り出すときは、目的となる値からハッシュ値をハッシュ関数で計算し、その値を元に目的となるデータを取り出すといった手順になります。コンパイラなどで使われる手法です。
ハッシュ値の衝突が起きないという仮定であれば、計算量はO(1)となります（ハッシュ関数に依存）。 実際はハッシュ値の衝突は起きるものです。衝突が起こった際の格納方法の違いで、オープンアドレス法と直接連鎖法（チェーンハッシュ）との2種類があります。
- ハッシュ関数 MD5やSHAなどが有名。基本的には入力となるデータ全体には依存しない方法（計算量：O(1)）で実装します。 また、ハッシュ値が偏らないような関数であれば、衝突が起こった際の探索効率が上がります。 よく用いられるハッシュ関数として、ある素数で剰余を取るなどがあります。
- オープンアドレス法 ハッシュ値衝突したら、隣のアドレスを順次調べていき、空いている場所に格納する方法。 取り出すときはハッシュ値の場所から、隣のアドレスを順次調べます。空いている場所に到達 or ハッシュ表の最後に到達 まで調べ、見つからなければ目的のデータが存在しないことになります。
例えば、次のようなデータが与えられたとします。 また、ハッシュ関数は13の剰余を返すものとし、格納するアドレスは1～12とします。 19 | 4 | 6 | 10 | 11 | 120このように進めていくと、各データの格納されるアドレスが次のようになります。
- 19に対しての操作をします。ハッシュ値は6ですので、アドレス6に19が格納されます。
- 4に対して操作をします。ハッシュ値は4ですので、アドレス4に4が格納されます。
- 6に対して操作をすると、ハッシュ値が6となりますが、アドレス6にはすでに19が入っているため、アドレス7に6が格納されます。
また、データが格納されている各アドレスの値は次のようになります。
データ 19 4 6 10 11 120 アドレス 6 4 7 10 11 3
アドレス 1 2 3 4 5 6 7 8 9 10 11 12 データ NULL NULL 120 4 NULL 19 6 NULL NULL 10 11 NULL
- 直接連鎖法 衝突したら、その場所でリストを作成し、そのリストに順次格納する方法。取り出すときは、作成されたリスト内を探索します。リスト内の探索は線形探索となります。上記の例ですと、各データが格納されている様子は次のようになります。
アドレス 1 2 3 4 5 6 7 8 9 10 11 12 データ NULL NULL 120 4 NULL 19 6 NULL NULL NULL 10 11 NULL
最後に
今回挙げた3手法ですが、データの格納にO(n)かかることを考えると、プログラム内でどれだけ探索を実行するかが選択の決め手になるかと思います。
それほど頻繁に探索しないのであれば、事前準備の要らない線形探索が優れていますが、同じような探索を頻繁に行う場合、二分探索やハッシュ法を用いるのが良いということになります。
