rpn_benchmark_test.md

Testing the speed of different RPN Calculator approaches

The following table shows the speed results of six different approaches to creating a reverse polish notation calculator with Ruby. The code was written by five different incoming Dev Bootcamp students and one instructor.

Approach	Time (ms)
First	119.2
Second	295.6
Third	264.7
Fourth	274.3
Fifth	131.6
Sixth	320.6

The main takeaway here is that the shortest program, in this case the sixth one which contains only 7 lines, performs the slowest. Its heavy dependence on regular expressions seems to be this solution's main difference, which may imply that regular expressions are slower than array manipulations. I will come back to this once I have more experience under the Ruby hood and try to form a better conclusion then.

require 'benchmark'

# First approach
def approach1(expr)
  tokenize(expr).inject([]) do |stack, token|
    if is_operator? token
      a,b = stack.pop(2)

      stack.push a.method(token).call(b)
    else
      stack.push token.to_i
    end
  end.pop
end

def tokenize(expr)
  expr.split(' ')
end

def is_operator?(token)
  ['+', '-', '*'].include? token
end

# Second approach
def approach2(str)
  arr = str.split(' ')
  result = []
  arr.each do |x|
    if ['+', '-' , '*'].include? x
      b = result.pop
      a = result.pop
       d = eval(a + x + b).to_s
      result << d
    else
      result << x
    end
  end
  return result[0].to_i
end

# Third approach
def approach3(expression)
  array = expression.split(' ')
  until array.length == 1
    array.each_index do |i|
      case array[i]
        when '+', '-', '*'
          array[i] = eval(array[i-2] + array[i] + array[i-1]).to_s
          array.delete_at(i-1)
          array.delete_at(i-2)
          array
      end
    end
  end
  return array[0].to_i
end

# Fourth approach
def approach4(string)
  array = string.split(" ")
  new_array = []
  array.each do |i|
    if i != '+' and i!= '-' and i!= '*'
        new_array << i
    else
      x = new_array.pop
      y = new_array.pop
      new_array << eval(y+i+x).to_s
    end
  end
  new_array[0].to_f
end

# Fifth approach
def approach5(expression)
  # turn expression into an array
  array = expression.split(' ')
  if array.length < 3
    return array[0].to_i
  end
  new_array = []
  array.each do |element|
    #look for digits
    if element =~ /\d+/
      #load digits into new array
      new_array.push(element)
    #look for operators  
    elsif element =~ /\S/
      #when you find an operator, pull off the last two digits,
      value_two = new_array.pop
      value_one = new_array.pop
    #apply the operator to them, and push the result back onto the array
      new_array.push(value_one.to_i.send($&, value_two.to_i))
    end     
  end
  #when finished return the last element in the array
  new_array.pop  
end

# Sixth approach
def approach6(string)
  return string.to_i unless string.include?(' ')
  string.match /(-?\d+) (-?\d+) ([-+*\/])(?!\d)/
  result = ($1.to_i).send($3,$2.to_i)
  string.gsub!($1 + ' ' + $2 + ' ' + $3, result.to_s)
  approach6(string)
end


# ------------------ #
# Testing for speed! #
# ------------------ #

Benchmark.bmbm do |x|
  x.report("First") do
    10_000.times do
      approach1('5 4 -9 6 * - +')
    end
  end

  x.report("Second") do
    10_000.times do
      approach2('5 4 -9 6 * - +')
    end
  end

  x.report("Third") do
    10_000.times do
      approach3('5 4 -9 6 * - +')
    end
  end

  x.report("Fourth") do
    10_000.times do
      approach4('5 4 -9 6 * - +')
    end
  end

  x.report("Fifth") do
    10_000.times do
      approach5('5 4 -9 6 * - +')
    end
  end

  x.report("Sixth") do
    10_000.times do
      approach6('5 4 -9 6 * - +')
    end
  end
end

Fantastic investigation, and loved the analogy on the blog post. Looking forward to that 'under the hood' understanding as well.