Arabic to Roman Number in Ruby on Rails

Question

I am making a class method in ruby to convert from roman number to Arabic and vice versa. However the loop is run to match each character and again to match with roman mapper. Can I optimize the same?

class String 
      private

      def roman_mapping
        {
          1000 => "M",
          900 => "CM",
          500 => "D",
          400 => "CD",
          100 => "C",
          90 => "XC",
          50 => "L",
          40 => "XL",
          10 => "X",
          9 => "IX",
          5 => "V",
          4 => "IV",
          1 => "I"
        }
      end
    end

def to_arabic(str = self, result = 0)
  return result if str.empty?
  roman_mapping.values.each do |roman|
    if str.start_with?(roman)
      result += roman_mapping.invert[roman]
      str = str.slice(roman.length, str.length)
      return to_arabic(str, result)
    end
  end
end

Answer 1

The organization of your code seems strange to me: should to_arabic be class or instance method of the String class or maybe neither? The method lies outside of the String class bracket, yet references private hash roman_mapping and self. My JRuby 1.7.18 throws a runtime error while trying to execute it.

Then the code doesn’t properly handle invalid (non-roman) characters, it stops recursion because for the first invalid character the mapping will fail, in this case not the result of the canversion up to that point but the array of the roman_mapping’s values will be returned, which is supposedly not what you want to achieve.

After putting to_arabic within the class frame and adding public before it for the code to execute:

p "MCMPIII".to_arabic2

["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]

Next you have a hash map but do not use it as such, just iterating over values. Even then you could use:

roman_mapping.each_pair do |value, roman|

to spare on the invert call.

At the end I’d suggest reverting the keys and values of the mapping hash (because you start from roman characters), using symbols instead of strings as keys and replacing recursion with a loop: like this:

class String
  private
  ROMAN_MAPPING = 
    { :M => 1000, :CM => 900, :D => 500, :CD => 400,
      :C => 100, :XC => 90, :L => 50, :XL => 40, :X => 10,
      :IX => 9, :V => 5, :IV => 4, :I => 1 }.freeze

  public

  def to_arabic()
    return 0 if empty?

    str = self
    result = 0
    while !str.empty?
      roman = str[0..1]
      value = ROMAN_MAPPING[roman.to_sym]
      if !value.nil?
        result += value
        str = str[roman.length, str.length]
        next
      elsif roman.length == 2
        roman = str[0]
        value = ROMAN_MAPPING[roman.to_sym]
        if !value.nil?
          result += value
          str = str[roman.length..-1]
          next
        end
      end
      raise "Invalid roman character %s in #{self}" % roman
    end
    result
  end

end

Here exemplary outputs:

p "MCMIII".to_arabic

1903

p "MCMPIII".to_arabic

RuntimeError: Invalid roman character P in MCMPIII

I admit it is longer, but behaves better raising error on erroneous input and is faster – on my machine benchmarked against your code was regularely almost 3 times faster.

UPDATE

@200_success Thanks for asking - besides the performance gain there are two more reasons for using symbols instead of strings as keys.

Never use mutable objects as keys in hash tables

This is reason enough - mutable objects as keys are evil, if they change unpredictable things can happen, since values are placed in buckets of a hash table based on hashcode of the keys, now you can imagine that changing the keys of pair after it has been placed into a hash map is never a good idea. And strings in Ruby are mutable!

I admit though, that this will rather not happen in our case, yet it would be a bad practice anyway and should be avoided just to keep the code clean. And it seems that in fact Ruby copies and freezes the strings if used as keys in hash maps in case we forget about this rule :-). Nevertheless we have our performance gain by using symbols.

roman_mapping is in fact an immutable constant

Neither keys nor values would ever change. So it is logical to use an immutable class for the keys - like symbols. Now numbers are immutable, too, but the hash maps are not. So while we are talking this, we should make roman_mapping also immutable using freeze, and while doing this we can also replace the method roman_mapping with a frozen constant.

To make roman_mapping immutable all these steps are necessary - simple freezing the hash map wouldn't be enough. If a reference to its keys leaks into the outside word it still could be changed.

I've just updated the code above. A new benchmark on my machine shows now even more performance gain: the new code is more than 10 times faster than the original:

                user     system      total        real
new to_arabic   0.700000   0.010000   0.710000 (  0.717587)
old to_arabic   9.200000   0.050000   9.250000 (  9.427725)