仕事をやり遂げるために必要な時間を見立てることが出来たら、次はその時間をいかに短縮するかを考えます。同じ仕事が短時間で出来るなら、それにこしたことはありません。余った時間で間違いがないかどうかの確認や、より品質を高めることが出来ます。
前回は、計算量O (n )のアルゴリズムの例としてリニアサーチを取り上げました。要素の数nの大きさに比例して、最悪検索時間が長くなります。今回は、リニアサーチよりも高速なバイナリサーチの計算量を求め、実際にコードを動かして速さの違いを実感しましょう。本当に同じ仕事を、より短い時間で実行できるのでしょうか。
計算量:バイナリサーチの場合O (log2(n))
バイナリサーチ[1]とは、データの真ん中の値、すなわち中央値[2]を「とりあえず」チェックする方法です。データは整列済みで、小さい値から大きい値の順に並んでいます。目的の値が中央値だろう、と当たりを付けるのです。もちろん、一発で目的の値になることは少ないでしょう。でも、この「当たりを付ける」ということがとても有効なんです。図75.2を用いて解説します。
- [Step 1]
図75.2の①のように、5個の整数を格納した配列vals
から値「5」を格納した位置(添え字の値)を検索する場合(target=5
)を紹介します。
先ず検索範囲を設定します。最初ですから左端は配列の先頭要素ですので、変数left=0
、右端は配列の末尾要素ですから変数right=vals.length-1=4
となります。中央値の位置は(left+right)/2=2
です。
もし、中央値が目的の値ならば、めでたく検索は終了です。しかし、違っていれば、中央値と目的の値の大小を比較します。もし、中央値よりも目的の値が小さければ、中央値以降のデータは捨ててしまいます。今回は、中央値より目的の値が大きいので、中央値より前のデータを捨てます。
- [Step 2]
図の②のように、Step1の操作によって、注目する配列の範囲はn/2 になりました。話を簡単にするために、nの偶奇は考えません。実際にコードを組む際には、n/2 を整数変数の除算として取り扱えば、小数部分が発生せず、都合良く範囲が決まります。
新しい配列の中央の値と目的の値を比較します。等しければ検索は終了。
等しくなければ大小を比較します。中央値よりも目的の値が大きいので、現在注目しているデータ以前を捨ててしまいます。
- [Step 3]
図の③のように、Step2の操作によって、残った配列のサイズは(n/2)/2になりました。今回の場合では残りのデータは1つだけになりました。ここで探す値target=5
と配列の値vals[4]=5
が等しいので、めでたく検索は成功し終了です。もし、vals[4]
の値が5でなければ、探す値は配列内に存在しなかった、ということで、検索は失敗し終了します。検索に失敗した場合には、-1などの、配列の添え字としてあり得ない値を返して、検索に失敗したことを表明しましょう。
- [Step a、最悪の場合]
最悪の場合、配列のサイズが1になるまでこのアルゴリズムが実行されます。繰り返しの回数aは次のような式で表されます。
y=log2(x) のグラフとy=x のグラフを並べて描くと、x が大きくなるほどバイナリサーチが有効なことがよく分かります。
問題 バイナリサーチのプログラムを作りましょう。
前回の問題で作成したリニアサーチのコードを変更してバイナリサーチのコードを作成しましょう。最低限、クラス名が変わることと、exec
メソッドの挙動を変更することで対応できます。前回同様実行時間を計測し、リニアサーチの場合と比較してください。
解説
問題 バイナリサーチのプログラムを作りましょう。
以下にバイナリサーチのコードを示します。お手元の環境での実行時間を計測してみてください。
以下はその実行結果です。
私の環境[3]ではたったの16ミリ秒でした。0.016秒です。リニアサーチの約300倍早く終了しました!これって、すごい高速化ですね。リニアサーチなんて、使うべきじゃないね、と言ったっていいでしょう。
今回はここまで
次回は、バイナリサーチよりも小さい計算量の検索アルゴリズムを紹介します。そして実際のコードで試してみましょう。果たして、理屈通りに高速なのか?お楽しみに。