def match_liner(val, array) # >>677と同等 array[0...-1].each_index do |i| if val <= array[i+1] return val-array[i] <= array[i+1]-val ? i : i+1 end end array.size - 1 end
def match_recursive(val, array) case array.size when 0 nil when 1 0 when 2 val-array[0] <= array[1]-val ? 0 : 1 else # ↑↓ 不等号に注意のこと i = array.size / 2 val < array[i] ? match_recursive(val,array[0..i]) : match_recursive(val,array[i..-1]) + i end end
Benchmark.bm do |x| x.report { data.each do |v| match_liner v, lookup end } x.report { data.each do |v| match_recursive v, lookup end } x.report { data.each do |v| match_loop v, lookup end } end user system total real 221.528000 0.040000 221.568000 (237.392000) # 線形検索 0.501000 0.000000 0.501000 ( 0.550000) # 二分検索（再帰） 0.140000 0.000000 0.140000 ( 0.141000) # 二分検索（ループ）
ついでにおまけ。 （>>747続き、 match_なんたらはmatchと定義しておく） def vlookup(val, range, column) # 指定列は0を起点とする val = val.to_f if val < range.first[0] or val > range.last[0] raise ArgumentError, "value out of range" end row = match val, range.map(&:first) # range[row][column] と同じだが、範囲外では例外を起こす。 range[row].fetch column end
pairs = lookup.zip(Array.new(lookup.size) { rand 100000 }) data.take(10).each do |v| puts vlookup(v, pairs, 1) end
