はじめに
以下の指数探索の記事を見かけ、興味を持ちました。
二分探索よりも速い指数探索の解説
この記事では、上記の記事においてC++で実装されていた指数探索を、Rubyで実装してみました。
ソースコード
exponential_search.rb
class Exponential_search
def initialize(array)
@array = array.sort # 配列は事前にソートしておく
end
def exponential_search(first,last,key)
# 指数探索の開始
len = @array.size
prev = first
cur = prev + 1
dis = 1
while dis < len and @array[cur] < key
prev = cur
cur += dis
dis *= 2
end
exponential_search_last = dis < len ? cur : last
binary_search(prev,exponential_search_last,key)
end
def binary_search(first,last,key)
# 2分探索のメソッド
while first <= last
mid = (first + last) / 2
return @array[mid] if @array[mid] == key
if @array[mid] < key
first = mid + 1
else
last = mid - 1
end
end
end
end
実行速度の評価
実装した指数探索の計算速度を、二分探索と比較してみました。
探索対象として、1〜1000までの整数の中から重複なしでランダムに500個取り出したデータを用意しました。
探索した数 | 指数探索での探索時間(ミリ秒) | 二分探索での探索時間(ミリ秒) |
---|---|---|
10 | 0.1417 | 2.0549 |
500 | 2.5296 | 0.1498 |
900 | 0.1607 | 0.1425 |