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

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

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

アルゴリズム（リニアサーチ）

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

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

アルゴリズム（バイナリサーチ）

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

サーチプログラムの比較
速度比較
ハッシュ探索法とは
リニアサーチとバイナリサーチの比較をScratch作る
まとめ

サーチプログラムの比較

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

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

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

速度比較

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

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

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

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

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

バイナリサーチの計算量がO(log_2 n)となる理由 - Qiita

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

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

ハッシュ探索法とは

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

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

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

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

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

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

共有プログラムはこちら

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

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

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

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

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