find_sum_benchmark.rb

require 'benchmark'

module BenchmarkTest
  def self.find_pair_naive(list, sum)
    list.each_with_index do |first, index_1|
      list.each_with_index do |second, index_2|
        next if index_1.eql? index_2 
        
        if first + second == sum
          return [index_1, index_2]
        end
      end
    end
    
    return [-1, -1]
  end
  
  def self.find_pair_sort_first(list, sum)
    list.sort!
    
    low = 0
    high = list.length - 1
    while low < high do
      current_sum = list[low] + list[high]
      if current_sum.eql?(sum)
        return [low, high]
      elsif current_sum < sum
        low += 1
      else
        high -= 1
      end
    end
    
    return [-1, -1]
  end
  
  def self.find_pair_hash(list, sum)
    lookup = {}
    list.each_with_index do |item, index|
      diff = sum - item
      if lookup.key?(diff)
        return [lookup[diff], index]
      else
        lookup[item] = index
      end
    end
    
    return [-1, -1]
  end
end

# arr = [8, 7, 2, 5, 3, 1]
arr = (1..1000).to_a
sum = 1999
iter = 1_000

Benchmark.bm do |bm|
  bm.report('naiv') do
    iter.times { BenchmarkTest.find_pair_naive(arr, sum) }
  end
  
  bm.report('sort') do
    iter.times { BenchmarkTest.find_pair_sort_first(arr, sum) }
  end
  
  bm.report('hash') do
    iter.times { BenchmarkTest.find_pair_hash(arr, sum) }
  end
end