Skip to content

Instantly share code, notes, and snippets.

@marcinbunsch
Created December 17, 2009 00:13
Show Gist options
  • Save marcinbunsch/258363 to your computer and use it in GitHub Desktop.
Save marcinbunsch/258363 to your computer and use it in GitHub Desktop.
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment