感謝のプログラミング 10000時間

たどり着いた結果(さき)は、感謝でした。

番兵を使えば、力ずくのリニアサーチより約1割強のスピードアップ!

スポンサーリンク

番兵って何?

配列を検索するときに、配列の最後に「探したい数値」を入れる。
それを一番ケツで配列を守るようなイメージから、番兵という。

番兵の何がいいか。
配列を一番先頭から検索する時に、n++みたいに増やしていくわけだけど
そのときにnは配列の末尾より小さいの?範囲は大丈夫なの?
と検査しながらループを回さなければならない。

なぜなら、配列の範囲を突き破ってしまうと、Index Out of rangeエラーになってしまうからだ。
「範囲外」のエラー。

こういうのを避けるために毎度毎度、この添字(n)は配列の大きさの範囲内ですか?と調べるわけだけど、これが意外と計算量が増えるはめになる。

いちいち、サイズチェックしたくない。
だから、番兵を立てようというわけだ。

番兵が入れば、純粋に、配列の中の数値だけを比較することができる。

目的の数字が「95」だとする。

配列にはランダムの数値が並んでいて、95があるかないかわからない。
そこで、とりあえず配列の末尾の値をtmp変数に入れておいて保存し、
末尾にターゲットとなる95を入れる。

で、先頭から順番に数値を比較する。
1番目の配列は、ターゲットと同じ?
2番目の配列はターゲットと同じ?
3番目は・・・

というように。
で、配列の末尾の1個手前まで検査して、最後にtmpの数値を配列の末尾に戻す。

で、ターゲットと配列の末尾の値を比較。

どこにも一致しなかったら、配列の中に目的の数値がないということがわかる。

ここでのポイントは、番兵を立てることで、配列のサイズを気にせず値の比較ができているということだ。
そうすることで、番兵を使わない場合よりも約1割強のスピードアップにつながるらしい。

では、Rubyでサンプルを書いてみたので、見てみよう。

def search_banpei(array, target)
  n = 0
  tmp = array[array.size()]
  #最後の値をtargetに入れ替える
  #これが番兵である
  array[array.size()] = target

  while (array[n] != target) do
    n += 1
  end

  #配列を元に戻す
  array[array.size()] = tmp

  #添字の数は、末尾より小さい?
  #つまり、配列末尾より前に、目的の数値がある?
  if (n < array.size())
    return n
  end

  #末尾の値を比較
  if (target == tmp)
     return n
  end

  #配列に目的の値はなかった・・・
  return -1

end

array = [];
for num in 1..300 do
  array << (rand() * 500).to_i
end

puts "配列のサイズは・・・"
puts array.size()
puts "---------"

target_num = 95
puts "目的の数字は・・・・"
puts target_num
puts "---------"

puts "番兵版リニアサーチを開始します!"
index = search_banpei(array, target_num)

puts "目的のindexは・・・"
puts index

if index != -1
  puts "本当に?array[index]で見てみよう"
  puts array[index]
else
  puts "見つからなかったみたいだね・・・"
end

実行した結果は以下のようになる。

配列のサイズは・・・
300
---------
目的の数字は・・・・
95
---------
番兵版リニアサーチを開始します!
目的のindexは・・・
275
本当に?array[index]で見てみよう
95

勉強した本

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

プログラミングの宝箱 アルゴリズムとデータ構造 第2版


アルゴリズムの勉強をするならこの本、と言えるバイブル的な本。

感謝のプログラミング

今回で感謝のプログラミングは【595時間目】
10000時間まで、あと【9405時間】