From: リスキルテクノロジー 松田航
新宿本校にて、、、
世の中には
さまざまな情報が溢れています。
情報を効率よく管理して活用するために
コンピューターシステムが作られますが...
膨大なデータ量になるほど
特定のデータを探し出すのに時間がかかります。
今回はデータを探すアルゴリズムである、
「サーチ」
についてお話しします。
目次
インターネットでも業務システムでも広く使われています
インターネットでは、
何か知りたいことがある時、
Yahoo!やGoogleなどの
検索サイトで情報を調べることは多いですよね。
検索サイトでキーワードを入力すれば、
キーワードに関連するサイトが
検索結果として表示されます。
業務系のシステムであれば、
顧客情報や売上情報、経理情報など、
さまざまなデータがデータベースで管理されています。
例えば、ある顧客の情報を見たい時には、
顧客の名前や電話番号をキーワードにして検索すれば
顧客の情報を知ることができます。
このように、
キーワードを指定して
特定の情報を探索することを...
「サーチ」
...と言い、ソートと共によく使われるアルゴリズムです。
サーチアルゴリズムには
さまざまな種類がありますが、
その中でも基本的なものをご紹介しましょう。
リニアサーチ（線形探索法）
～データをひとつずつチェックして探索～
リニアサーチは線形探索法とも言われる、
サーチアルゴリズムの中では
最も単純な探索アルゴリズムです。
一直線に並んだ箱の中を
順番に空けて中身をチェックしていくのに似ています。
リニアサーチのイメージを見てみましょう。
3,2,5,4,1と並んだ
5つの値を持つ配列があり、
この配列から4という値を探し出します。
リニアサーチは
順番に値をチェックしてゆくアルゴリズムです。
探索値と1番目の値を比べ、
探索値と2番目の値を比べ、
探索値と3番目の値を比べ...
と、順番に比べていって、
値が一致したらサーチ終了となります。
もし、どの値とも一致しなければ、
探索結果は無しとなります。
インターネットで検索する時でも
でたらめなキーワードで検索すると...
「一致する情報はみつかりませんでした」
と表示されますが、あれと同じですね。
リニアサーチは1つずつ値を比較するので、
とても時間がかかってしまいます。
少量のデータ探索には使えますが、
膨大なデータ量になると時間がかかりすぎて
実用的ではありません。
そこで、リニアサーチよりも
探索速度の速いアルゴリズムが必要とされます。
バイナリサーチ（二分探索法）
～データを2つに分けて効率よく探索～
バイナリサーチは二分探索法とも言われる
探索速度の速いアルゴリズムです。
ただ、リニアサーチをするには、
ひとつだけ条件があります。
その条件とは、
探索する配列の値が
あらかじめソート（並べ替え）されていることです。
それでは、
リニアサーチのイメージを見てみましょう。
バイナリサーチよりもややこしいので、
イメージだけつかんでください。
1,2,4,5,6,8,9と
値が昇順に並んだ配列があり、
この配列から4という値を探し出します。
バイナリサーチでは、
まず配列の中間にある値をチェックします。
配列の中間の値は5なので、
探索値は中間よりも右側の
小さいグループにあることがわかりますね。
次に、小さいグループの中から
中間にある値をチェックします。
中間の値は2なので、
探索値は小さいグループの中間よりも
右側にあることがわかります。
そして、小さいグループの中間より
右側の値をチェックします。
ここで探索値が見つかったので、
サーチ終了となります。
バイナリサーチでは
ソートされたデータの特徴を活かして、
中間点の値を比べ続けることにより
高速に探索することができます。
リニアサーチだと
全ての値をチェックするか、
探索値が見つかるまでサーチを続けますが...
リニアサーチの場合は
必要ないチェックを行わずに探索できるのです。
ただ、リニアサーチを行う前には
必ずソートしなければいけないので、
ソートのための処理時間がかかるのが難点ですね。
サーチは常に使われる重要なアルゴリズム
このほかにも
さまざまな種類のサーチがありますが、
必要に応じて覚えていってください。
実際の現場では、
どのアルゴリズムを使うなどというのは、
あまり考えません。
データベースの性能に頼ってしまった方が、
いいからです。
しかし、考え方という意味で、
いろいろな場面で役立つのがアルゴリズムというやつです。
さまざまなアルゴリズムを習得して、
他のプログラムに利用できるような
応用力を目指すべきでしょう。
リスキルテクノロジー
松田
PS
アルゴリズムの範囲は広がっています。
ロボット掃除機の物体認識アルゴリズムや
テレビのCM音量を自動的に抑えるアルゴリズムなど、
ITの活用シーンが増えるにつれて
そのバリエーションは幅広くなっています。
あなたがエンジニアとして
最新のアルゴリズムを使うこともあるでしょう。
その日のために基本をしっかりとおさえて、
準備を整えておきましょう。
