ハジカラ 〜はじめからでも、プログラミング勉強〜

入門向けに、IT関連(javaやKotlin)をコツコツ書いたり検証したりします。

【IT入門】データ探索のアルゴリズム

calendar

reload

【IT入門】データ探索のアルゴリズム

こんにちは😀

前回は配列などのデータ構造のアルゴリズムをまとめましたが、今回はそのデータを探索する際のアルゴリズムをまとめてみました。

配列やリストに格納したデータを特定の文字列で探索することもあります。
その時に使用するアルゴリズムにはいくつかパターンがあるので、1つ1つみてきます。

スポンサーリンク

線形探索法

一番単純な探索アルゴリズムになります。
先頭から順に探索していく方法を線形探索法と言います。

例えると、目的のデータが見つかるまで配列の添字範囲をループするまたは添字範囲を超えるまでループする処理を行います。

ここで、目的のデータがないことも考慮して、あえてデータ構造の末尾に目的のデータを足す処理を行う場合もあります。
この追加したデータを番兵といい、番兵まで行って処理が終了したら、そのデータ構造の中に目的のデータはなかったと判断できます。

2分探索法

データが昇順・降順に並んでいる場合、2分探索法を使用するとより効率的に探索できます。
2分探索法とは、データの集合をざっくり2つに分けながら対象を絞り込んでいく方法です。

例えば、昇順で並んでいるデータの真ん中のデータを目的のデータと比較します。
目的のデータの方が大きければ、その右側のデータの真ん中のデータと比較します。
このように順にデータの対象を絞っていく方法になります。

ハッシュ法

ハッシュ法は、ハッシュ関数と呼ばれる一定の計算式を用いて、データの格納位置を算出する探索方法です。
データをデータ構造に格納する時に、計算式で求めた位置へと格納します。
データを探索する時も、同じ計算式で位置を求めて参照します。
この一連の流れがハッシュ法になります。

ただし、異なるデータで同じハッシュ値が求められてしまうこともあります。これをコリジョン(衝突)もしくはシノニムの発生と呼びます。
この場合は、別の計算式を行って新しい格納先を求めます。
別の方法は以下の2つがあります。

・オープンアドレス法・・・
シノニム発生時に別のハッシュ関数を用いて新しいハッシュ値を求めます。新しいハッシュ値には一般的に「前回のハッシュ値+1」を用います
・チェイン法・・・
ハッシュ表にデータへのポインタを持たせて起き、シノニム発生時に同じハッシュ値のデータを単方向リストとして連結して格納します。

今回の一言・・・

探索の方法も、状況に応じていくつか方法があるのがわかりました。
効率的に探索も行われるよう工夫がされています。

今回はここまで🤚

では、また次回。

IT入門一覧はこちら】

※今回の内容は、「キタミ式イラストIT塾 応用情報技術者」(株式会社技術評論社)を参考としました。

この記事をシェアする

コメント

コメントはありません。

down コメントを残す