Benchmarking the difference in speed w/ 2 different algorithms that search an array for

find_sums.rb

# Side effect is that converting the array to a hash will remove 
# duplicate entries, if they exist
require 'benchmark'

def find_sums_hashed(arr, target)
  hash = Hash[*arr.zip(Array.new(arr.length)).flatten]
  hash.each_key do |key|    
    if hash.has_key?(target-key) && target != target - key
      yield [key, target-key] if block_given? 
    end
  end
  print "done"
end

# Takes advantage of the fact that in ruby 1.9, keys are returned in order of creation
def find_sums_hashed_in_order(arr, target)
  sorted_arr = arr.sort
  hash = Hash[*sorted_arr.zip(Array.new(sorted_arr.length)).flatten]
  hash.each_key do |key|    
    if hash.has_key?(target-key) && target != target - key
      break if key > target-key
      yield [key, target-key] if block_given? 
      yield [target-key, key] if block_given? 
    end
  end
  print "done"
end

def find_sums_slowly(arr, target)
  arr.each_with_index do |val, index|
    arr[index+1..-1].each do |val2|
      if val + val2 == target
        yield [val, val2]
      end
    end
  end
end

arr = 10000.times.collect{rand(-100..100)}
target = rand(-100..100)

Benchmark.measure {find_sums_hashed_in_order(arr, target) {}}
Benchmark.measure {find_sums_hashed(arr, target) {}}
Benchmark.measure {find_sums_slowly(arr, target) {}}

results.txt

# Sorting the array, and then searching half of the array is slower due to the time required to sort the array.
1.9.3-p429 :343 >   Benchmark.measure {find_sums_hashed_in_order(arr, target) {}}
done =>   0.000000   0.000000   0.000000 (  0.005858)

1.9.3-p429 :344 > Benchmark.measure {find_sums_hashed(arr, target) {}}
done =>   0.010000   0.000000   0.010000 (  0.005617)

1.9.3-p429 :345 > Benchmark.measure {find_sums_slowly(arr, target) {}}
 =>   4.110000   0.010000   4.120000 (  4.209591)