アルゴリズム(リニアサーチとバイナリサーチの比較)

三色の砂時計プログラム

さて本ブログではサーチプログラムとしてリニアサーチ(線形探索)とバイナリサーチ(二分探索)について説明しました。今回はまとめとして、このあと少しだけ触れるハッシュ探索も含めて3つのサーチプログラムについて比較を行いたいとおもいます。

 

リニアサーチの記事はこちら

アルゴリズム(リニアサーチ)
今回はアルゴリズムの中におけるリニアサーチについて述べたいと思います。なお、この記事を書いた後、もっとよいプログラムの書き方を見つけて追加記事を書いています。 こちら サーチプログラムとは サーチプログラムとは、その名のと...

バイナリサーチの記事はこちら

アルゴリズム(バイナリサーチ)
さて今回はサーチプログラムにおける代表的アルゴリズムのバイナリサーチについて説明します。 バイナリサーチとは バイナリサーチとはサーチプログラムの一種です。 サーチプログラム(探索プログラム)については、前回、リニアサーチについて...

 

サーチプログラムの比較

サーチプログラムは、なぜ複数やり方があるのでしょうか?普通に探すだけなら簡単なプログラム一種類だけ知って入ればいいと思いますよね。

それは、もちろんそれぞれの書き方によってメリットやデメリットがあるからです。以下が各アルゴリズムの特徴を簡単にまとめたものです。

項目リニアサーチバイナリサーチハッシュ探索
特徴シンプルな探索法探し先のデータを二分していきながら探索をしていく探す数をハッシュして、そのハッシュ値でデータ格納先を判定する。
前提条件特になしあらかじめデータは小さい順から、または大きい順からに整理されている必要がある。あらかじめハッシュ値に基づいてデータを整理しておく必要がある
計算速度標準高速超高速

 

速度比較

先の比較表では、標準とか高速とか曖昧な表現としましたが各サーチアルゴリズムの速度は次の計算式で比較されます。

サーチプログラム計算量

グラフではこうなります。

サーチプログラムグラフ

この計算式について、リニアサーチについては単純にデータの先頭から1つ1つ探索していくので、最大の計算量はデータの個数 n と等しくなります。そのため、計算量はO(n) となります。(この表記をO記法というらしい)

一方、後で話すハッシュ探索法は、探す数を一回ハッシュするだけで、どこにデータがあるかがわかるという探索法(データの格納のやり方)なので計算量は1回となりO(1)となります。

最後はバイナリサーチなのですが、これは探索するのに1/2、1/2と計算していきます。その結果がlog2 nとなります。このバイナリサーチがこの式になるかは以下の記事が詳しくかかれています。

バイナリサーチの計算量がO(log_2 n)となる理由 - Qiita
データ個数が$n$の時のバイナリサーチの計算量が$O(log_2n)$となる理由について書いてみました。 $log_an$ とは「$a$を○乗すると$n$になる」の「○」にあたる値です。 (例:$log_28$ は「$を○乗す...

 

といったわけで、リニアサーチにくらべバイナリサーチ、ハッシュ探索が圧倒的に早いのですが、そこは前提条件やアルゴリズムの複雑さを加味しての選択になりますね。

 

ハッシュ探索法とは

さて、ここでハッシュ探索法についても触れたいと思います。なぜハッシュ探索法は1つの記事にしないのかということなのですが、実は・・・ハッシュ探索法はScrathではできないんですよ。ハッシュ探索のデータを格納する辞書型リスト(連想配列)がScratchではないのですよ。

じゃぁPythonで書けばいいじゃんって話でもあるのだけと、このブログってそもそも教育用言語をメインとしているので、ちょっとターゲットからはずれるかなと、ここでは紹介のみにします。(いや、単純にメンドクサイだけないんですけどね)

さて、そのハッシュ探索法は、サーチの方法というよりデータの整理法といった感じなので純粋にサーチプログラムなのかというと、意見が分かれるのかもしれませんが原理としてはこのようなものです。

ハッシュ探索法

あらかじめ探索するデータをハッシュ化して辞書型リスト(連想配列)という形でデータを格納しておきます。そして、探す数をハッシュして出てきた値を元に、その値が書かれた番地に一気に向かうというものです。ここではイメージなので簡単にしていますが、実際のハッシュ値の算出には様々な計算方法があり、またAとBのハッシュ値が同値であった場合は衝突という現象が起きます。この解決にはチェイン法やオープンアドレス法などがあります。ただ、これを説明するのも専門的になりますので、ここでは説明を省きます。

 

リニアサーチとバイナリサーチの比較をScratch作る

さて、このリニアサーチとバイナリサーチについてScratchで速度を比較するプログラムをかいてみました。それがこちらです。

リニアサーチとバイナリサーチのScratch比較

共有プログラムはこちら

https://scratch.mit.edu/projects/339507089

 

このプログラムではスタートボタンを押すと1~200,000の数が格納された配列を自動で作成します。その上でいくつの数を探すと聞いてくるので、探す数をいれるとリニアサーチと担当するリニア犬とバイナリサーチを担当するバイナリ犬が同時に数を探索して、かかった時間を表示します。なお、前回のガウスの足し算のときもそうだったのですが、かかった時間は「いくつの数を探す」と聞いてから探し終わった結果までの時間となります。そのため、いくつの数にしようかと悩んでいる時間もカウントされます。これは、数を入力してから算出にかかったまでの時間だと0秒とかになることがあって、差がわかりづらかったからです。(あまりにも短い時間だと0秒で丸められるみたい)

またScrachは配列は20万までしか作ることができません。本来であればもっと大きな数に対しての比較をおこなかったのですが、これが仕組上、限界でした。

さて、この20万の配列に対して、大体、10を探すというくらいであればリニアサーチが早いですが、30を探すくらいからバイナリサーチが早くなります。厳密にいえば、純粋な探索アルゴリズム以外で結果を表示するところで分岐が一個多かったり少なかったりするので、厳密に正しいの?というところはありますが、大体こんなものというイメージでとらえていただければとおもっています。

 

より正しく測定されている方はこちらにいらっしゃるようです。

配列を高速に探索するアルゴリズムを検証してみる | hellopeople
I'm a Frontend Engineer in Tokyo. I write about Engineering and Design and My Life.

 

まとめ

さて、修正プログラム版を含めて全4回でサーチプログラムについての記事を書きました。アルゴリズムについて書くって、ちょっと気難しい記事になっちゃいますね。また、少し時期をあけて、今度はソートプログラムについて、書くことにして次回からは、しばらく、プログラム本体の話に戻ることにしたいと思います。

 

コメント

タイトルとURLをコピーしました