エンジニアなら知っておくべき探索アルゴリズムの種類

こんにちは、しょうぞうです。

今回は、アルゴリズムに関して記事を書いていきたいと思います。

アルゴリズムには種類がいくつかあって代表的なアルゴリズムをそれぞれ紹介していきたいとおもいます。

アルゴリズムとは

アルゴリズムとは、「どのように処理をさせると機能を満たすだろうか」や「どのような手順を踏めばより効率的になるだろうか」などをもとに考えられた手順のことを意味します。

アルゴリズムさえ考えれば、あとはそれをプログラミング言語で置き換えて書いていけばいいので、最も重要な部分だと考えられています。

一連の流れを図で表したものをフローチャートで書いたりします。

アルゴリズムの中でも代表的なものを紹介していきたいと思います。

線形探索法

線形探索法とは、先頭から順番に探す値を見つかるまで探すアルゴリズムです。

データが見つかるか配列の数の範囲を超えるまでループで検索し続けるというものです。

コードで書くと以下のようになります。

線形探索法では、「目的のデータかどうか」と「配列の数の範囲を超えたかどうか」の２つの判定が毎回行われるため処理が効率的でないとされています。

それを解消したのが番兵法というものです

番兵法というのは、配列の最後に探そうとしている目的の値を追加することで配列の中に目的の値が必ずある状態を作り、「配列の数の範囲を超えたかどうか」という判定を省略するというものです。

コードで書くと以下のようになります。

二分探索法とは、あらかじめ探索対象のデータ群が「昇順にならんでいる」「降順に並んでいる」というようにソートされていて規則性を持っている場合により効率的な方法で探索できる方法です。

やり方としては、データの集合をざっくり2つに分けながら対象を絞り込んでいくといった形になります。

コードで表すと以下のような感じです。

ハッシュ法とは、対象となるデータから一定の手順で算出したハッシュ値を用いてデータ本体の代わりに比較に用いる方式です。
対象とするデータが長い場合に処理を高速化することができます。

例えば、5桁の数a₁a₂a₃a₄a₅をmod(a₁+a₂+a₃+a₄+a₅, 13)というハッシュ関数を用いて位置を決め、配列に格納するとします。

ここでmod(x,13)は、余りを求める関数とします。xを13で割った時の余りが返ってきます。
54321というデータがあるとして、このデータの格納位置はどこにあるのかを探索するときに簡単に見つけることができます。

54321→mod(5+4+3+2+1, 13) = mod(15,13) = 2が答えになります。

問題としては、仮に「12345」というデータがあったとしたら、格納位置が同じ「2」という結果になってしまい衝突してしまいます。

この現象を「シノニム」といいます。

シノニムが発生した場合は、さらに別の計算を行なって新しい格納先を求める必要があります。

アルゴリズムの基本的な内容をアウトプットとして書いてみました。

実際に文字で見ていても、コードに起こすとややこしくてまとめるのが大変でした。

ただ理解が深まったのでよかったです。

以上！