therubygame Challenge #4 Benchmark

palindrome.txt

FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth

results-1.9.3.txt

ruby 1.9.3p0 (2011-10-30 revision 33570) [x86_64-linux]
"do the algorithms work?"
:short
search: ypqqpy
search(reverse): ypqqpy
regex: ypqqpy
regex(reverse): ypqqpy
apeacox: ypqqpy
apeacox(reverse): aba
foxycoder: ypqqpy
foxycoder(reverse): aba
:mid
search: ranynar
search(reverse): ranynar
regex: ranynar
regex(reverse): ranynar
apeacox: illli
apeacox(reverse): ranynar
foxycoder: ranynar
foxycoder(reverse): ranynar
"benchmark"
       user     system      total        real
short-palindrome_search(100000)  3.290000   0.020000   3.310000 (  3.456773)
short-palindrome_regex(100000)  1.940000   0.020000   1.960000 (  2.051057)
short-palindrome_apeacox(100000)  0.320000   0.000000   0.320000 (  0.358358)
short-palindrome_foxycoder(100000)  0.330000   0.000000   0.330000 (  0.331866)
mid-palindrome_search(1000)  1.990000   0.030000   2.020000 (  2.055993)
mid-palindrome_regex(1000) 66.750000   0.170000  66.920000 ( 70.062409)
mid-palindrome_apeacox(1000)107.880000   4.630000 112.510000 (115.218074)
mid-palindrome_foxycoder(1000)  1.580000   0.020000   1.600000 (  1.671716)

run.rb

#http://www.therubygame.com/challenges/4/submissions/12873
def palindrome_search(string)
  longest = ''
  l=string.size - 1
  (1..l).each do |i|
    j=i+1
    while 0<=i && j<=l && string[i] == string[j]
      i-=1
      j+=1
    end
    pot = string[i+1..j-1]
    longest = pot if pot.size > longest.size
  end
  (1..l).each do |i|
    j=i+1
    i-=1
    while 0<=i && j<=l && string[i] == string[j]
      i-=1
      j+=1
    end
    pot = string[i+1..j-1]
    longest = pot if pot.size > longest.size
  end
  longest
end

#http://www.therubygame.com/challenges/4/submissions/13206
def palindrome_regex(string)
  string.scan(/(?<palindrome>(?:(?<some_letter>\w)(\g<palindrome>||.)\k<some_letter+0>))/).max_by{|e| e[0].length}[0]
end

#http://www.therubygame.com/challenges/4/submissions/12969
def palindrome_apeacox(string)
  w = string.size
  l = (w / 2)
  l.upto(w-2) do |j|
    i = w-j
    l.upto(w-i+2) do |n|
      s = string[n,i]
      return s if s == s.reverse
    end
  end
end

#http://www.therubygame.com/challenges/4/submissions/12969
def palindrome_foxycoder(string)
  a = string.size
  a-11.downto(2).each { |i|
    (11..a-i+1).each {
      |n| s = string[n,i]
      return s if s == s.reverse
    }
  }
end

require "benchmark"

strings = {
  short: 'abacdfgdcabaypqqpy',
  mid: IO.read('./palindrome.txt'),
 # long: IO.read('./grundgesetz.urversion.txt')
}

ITERATIONS = 1000
p 'do the algorithms work?'
strings.each do |k,v|
  p k
  print "search: #{palindrome_search(v)}\n"
  print "search(reverse): #{palindrome_search(v.reverse)}\n"
  print "regex: #{palindrome_regex(v)}\n"
  print "regex(reverse): #{palindrome_regex(v.reverse)}\n"
  print "apeacox: #{palindrome_apeacox(v)}\n"
  print "apeacox(reverse): #{palindrome_apeacox(v.reverse)}\n"
  print "foxycoder: #{palindrome_foxycoder(v)}\n"
  print "foxycoder(reverse): #{palindrome_foxycoder(v.reverse)}\n"
end

p 'benchmark'
Benchmark.bm do |bench|
  strings.each do |k,string|
    if k == :short
      iterations = 100000
    else
      iterations = 1000
    end
    bench.report("#{k}-palindrome_search(#{iterations})") do
      iterations.times do
        palindrome_search(string)
      end
    end
    bench.report("#{k}-palindrome_regex(#{iterations})") do
      iterations.times do
        palindrome_regex(string)
      end
    end
    bench.report("#{k}-palindrome_apeacox(#{iterations})") do
      iterations.times do
        palindrome_apeacox(string)
      end
    end
    bench.report("#{k}-palindrome_foxycoder(#{iterations})") do
      iterations.times do
        palindrome_foxycoder(string)
      end
    end
  end
end