mislav_contest_benchmarks.rb

# Benchmark of different solutions to mislav's "Find the longest common starting substring in a set of strings" contest
# http://stackoverflow.com/questions/1916218/find-the-longest-common-starting-substring-in-a-set-of-strings

# Solutions:

# mislav
class String
  def &(other)
    difference = other.to_str.each_char.with_index.find { |ch, idx|
      self[idx].nil? or ch != self[idx].chr
    }
    difference ? self[0, difference.last] : self
  end
end

class Array
  def common_substring
    self.inject(nil) { |memo, str| memo.nil? ? str : memo & str }.to_s
  end
end

# AShelly
def oneliner(arr)
  arr.inject{|l,s| l=l.chop while l!=s[0...l.length];l}
end

# Yehuda Katz
def build_regex(string)
  arr = []
  arr << string.dup while string.chop!
  Regexp.new("^(#{arr.join("|")})")
end

def substring(first, *strings)
  strings.inject(first) do |accum, string|
    build_regex(accum).match(string)[0]
  end
end

# tadman
def common_substring(data)
  data.inject { |m, s| s[0,(0..m.length).find { |i| m[i] != s[i] }.to_i] }
end

# Jordan
def f(words)
  first_word = words[0];
  first_word[0, (0..(first_word.size)).find { |num_chars|
    words.any? { |word| word[0, num_chars] != first_word[0, num_chars] }
  } - 1]
end

# Benchmark

require 'benchmark'
n = 10000
# Benchmark arrays
arrays = [
   %w(interspecies interstelar interstate),
   %w[feet feel feeble],
   %w[alpha bravo charlie]
]

# solutions to use
solutions = {
  'mislav'  => lambda { |arr| arr.common_substring },
  'AShelly' => lambda { |arr| oneliner(arr) },
  'Yehuda'  => lambda { |arr| substring(arr) },
  'tadman'  => lambda { |arr| common_substring(arr) },
  'Jordan'  => lambda { |arr| f(arr) }
}

arrays.each do |arr|
  puts "=== Benchmarking: #{arr.join(' ')} ==="
  Benchmark.bm do |x|
    solutions.each_pair do |person, solution|
      puts "#{person}: #{solution.call(arr)}"
      x.report(person) { n.times do solution.call(arr); end }
    end
  end  
end