前提
以下、過去の開発で実際にあった例です。
stations = [{id: 1, name: station1}, {id: 2, name: station2}, ...]
facility_counts_by_station = [{id: 1, count: 10}, {id: 3, count: 20}, ...]
idはどちらもstation_idを指す。
のような配列がそれぞれあり、stationsに同一idのcountをmergeしたい。
これを処理するうえで、線形探索、ハッシュ探索、バイナリ探索それぞれのアルゴリズムで処理速度がどれくらい違うのか比較してみた。
補足
ある施設の数を駅ごとに表示するため用意しているデータです。
1つ目の配列はActiveRecordから取得、2つ目の配列はElasticSearchのaggregationから取得しているため、それを突合させる必要がありました。
なお、stationに属するfacilityが0件のケースはfacility_counts_by_stationに要素が作られないため、stationsに比べて1/3のデータ量にしています。
今見るとElasticSearch側のレスポンスにnameも含めてcountが0でも要素を返してもらうようにすればいい気がしますが、そうできない事情があったのかもしれません・・・
実装
def main
[1500, 15000, 150000].each do |size|
stations, facility_counts_by_station = init(size)
start_time = Time.now
linear_result = merge_by_linear_search(stations, facility_counts_by_station)
p "線形探索処理時間 (size=#{size}): #{Time.now - start_time}s"
start_time = Time.now
hash_result = merge_by_hash_search(stations, facility_counts_by_station)
p "ハッシュ探索処理時間 (size=#{size}): #{Time.now - start_time}s"
start_time = Time.now
binary_result = merge_by_binary_search(stations, facility_counts_by_station)
p "バイナリ探索処理時間 (size=#{size}): #{Time.now - start_time}s"
if linear_result == hash_result && linear_result == binary_result
p '正常'
elsif linear_result != hash_result
p 'linear_result != hash_result'
elsif linear_result != binary_result
p 'linear_result != binary_result'
end
end
end
def init(size)
stations = []
facility_counts_by_station = []
size.times do |i|
id = i + 1
stations << { id: id, name: "station#{id}"}
if i % 3 == 0
facility_counts_by_station << { id: id, count: rand(100) }
end
end
return stations, facility_counts_by_station
end
def merge_by_linear_search(stations, facility_counts_by_station)
stations.map do |station|
target = facility_counts_by_station.find{|h| h[:id] == station[:id]}
station.merge({count: target&.[](:count) || 0})
end
end
def merge_by_hash_search(stations, facility_counts_by_station)
facility_counts_hash = {}
facility_counts_by_station.each do |facility_count|
facility_counts_hash[facility_count[:id]] = facility_count[:count]
end
stations.map do |station|
station.merge({count: facility_counts_hash[station[:id]] || 0})
end
end
def bsearch_original(sorted_arr, target_id)
head = 0
tail = sorted_arr.length - 1
while head <= tail
center = (tail + head) / 2
if sorted_arr[center][:id] == target_id
return sorted_arr[center]
elsif sorted_arr[center][:id] > target_id
tail = center - 1
elsif sorted_arr[center][:id] < target_id
head = center + 1
end
end
return {}
end
def merge_by_binary_search(stations, facility_counts_by_station)
stations.map do |station|
target = bsearch_original(facility_counts_by_station, station[:id])
station.merge({count: target&.[](:count) || 0})
end
end
main
測定結果
"線形探索処理時間 (size=1500): 0.054236214s"
"ハッシュ探索処理時間 (size=1500): 0.00072462s"
"バイナリ探索処理時間 (size=1500): 0.002575072s"
"線形探索処理時間 (size=15000): 5.983366226s"
"ハッシュ探索処理時間 (size=15000): 0.011276715s"
"バイナリ探索処理時間 (size=15000): 0.03400995s"
"線形探索処理時間 (size=150000): 958.449376416s"
"ハッシュ探索処理時間 (size=150000): 0.141020173s"
"バイナリ探索処理時間 (size=150000): 0.353612058s"
このコードにおいて、
N1 = stations.length (= 1,500 or 15,000 or 150,000)
N2 = facility_counts_by_station.length (= 500 or 5,000 or 50,000)
線形探索: O(N1 * N2)
ハッシュ探索(ハッシュ変換込み): O(N1 + N2)
バイナリ探索: O(N1 * LogN2)
となるので、やはりハッシュが一番早かった。
おまけ
バイナリ探索のほうが早い場合はないのかと考えたところ、オーダーの式的にN2の数がN1に比べて圧倒的に多いときそうなりそうだと思ったので、N1とN2を逆にして(facility_counts_by_station.each内でstationsに対して探索)かつ、N1 : N2 = 1 : 100 にして計測してみた。
N1 = facility_counts_by_station.length (= 15 or 15)
N2 = stations.length (= 1,500 or 15,000)
"線形探索処理時間 (size=1500): 0.000868799s"
"ハッシュ探索処理時間 (size=1500): 0.0002049s"
"バイナリ探索処理時間 (size=1500): 2.16e-05s"
"線形探索処理時間 (size=15000): 0.099216185s"
"ハッシュ探索処理時間 (size=15000): 0.0035582s"
"バイナリ探索処理時間 (size=15000): 0.0003478s"
その通りになった。つまり、N2>>>N1
ならバイナリ探索が速い。