confidence_search.rb

module ConfidenceSearch
  class << self
    def search(start_num, end_num, &block)
      (start_num..end_num).to_a.reverse.find { |n| block.call(n) }
    end

    def bin_ex_search(start_num, end_num, try_num: 1, last_num: nil, window: 1, &block)
      return nil unless block.call(start_num)

      num = try_num.times.find { |n| block.call(end_num - n + 1) }
      return end_num - num + 1 if num

      bin_search(start_num, end_num, last_num: last_num, window: window, &block)
    end

    def bin_search(start_num, end_num, last_num: nil, window: 1, &block)
      nums = (start_num..end_num).to_a

      if last_num
        res = bin_search(last_num - window, last_num + window, &block)
        if res.nil?
          res = bin_search(start_num, last_num - window, &block)
        elsif res < last_num + window
          res
        else
          res = bin_search(res, end_num, &block)
        end
        return res if res
      end

      num = nil
      while nums.size > 0
        div = (nums.size / 2).floor
        res = block.call(nums[div])
        if res
          num = nums[div]
          nums = nums[div+1..-1]
        else
          break if div < 1
          nums = nums[0..div-1]
        end
      end
      num
    end
  end
end

random_ccc = 10.times.map { 100.times.map { rand(100) } }

c = 50
move_ccc = 10.times.map do
  100.times.map do
    c += (5 - rand(10))
    c = 99 if c > 99
    c = 40 if c < 40
    c
  end
end


Benchmark.bm 30 do |r|
  {
    "random" => random_ccc,
    "move" => move_ccc,
  }.each do |key, ccc|
    r.report "#{key}: Normal" do
      ccc.each do |cc|
        cc.each do |confidence|
          res = ConfidenceSearch.search(50, 99) { |n| 10000.times { 1 + 1 }; n <= confidence }
          raise "#{res} != #{confidence}" if res != confidence && !res.nil?
        end
      end
    end
    r.report "#{key}: Binary" do
      ccc.each do |cc|
        cc.each do |confidence|
          res = ConfidenceSearch.bin_search(50, 99) { |n| 10000.times { 1 + 1 }; n <= confidence }
          raise "#{res} != #{confidence}" if res != confidence && !res.nil?
        end
      end
    end
    r.report "#{key}: BinaryEx" do
      ccc.each do |cc|
        cc.each do |confidence|
          res = ConfidenceSearch.bin_ex_search(50, 99, try_num: 1) { |n| 10000.times { 1 + 1 }; n <= confidence }
          raise "#{res} != #{confidence}" if res != confidence && !res.nil?
        end
      end
    end
    r.report "#{key}: BinaryAndHistory" do
      last_num = nil
      ccc.each do |cc|
        cc.each do |confidence|
          res = ConfidenceSearch.bin_search(50, 99, last_num: last_num, window: 5) { |n| 10000.times { 1 + 1 }; n <= confidence }
          raise "#{res} != #{confidence}" if res != confidence && !res.nil?
          last_num = confidence
        end
      end
    end
    r.report "#{key}: BinaryExAndHistory" do
      last_num = nil
      ccc.each do |cc|
        cc.each do |confidence|
          res = ConfidenceSearch.bin_ex_search(50, 99, try_num: 1, last_num: last_num, window: 5) { |n| 10000.times { 1 + 1 }; n <= confidence }
          raise "#{res} != #{confidence}" if res != confidence && !res.nil?
          last_num = confidence
        end
      end
    end
  end
end