There are an infinite number of opportunities to learn and improve your skills as a developer. I like to take some time now and then to do it consciously, so I pick a topic and go at it.
The trigger this time was a Sandi Metz newsletter entry about the Roman Numerals quiz. (That drove me to take interest in Ruby refinements, but I digress).
I remember trying to solve that same problem some years back when first learning ruby. I found it here, as part of ruby quiz blog and the associated book.
This time, a part of the proposed solution got me thinking:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
def roman_table_original return @roman_table if @roman_table roman_map = { 1 => "I", 4 => "IV", 5 => "V", 9 => "IX", 10 => "X", 40 => "XL", 50 => "L", 90 => "XC", 100 => "C", 400 => "CD", 500 => "D", 900 => "CM", 1000 => "M" } @roman_table = Array.new(3999) do |index| target = index + 1 roman_value = roman_map.keys.sort { |a, b| b <=> a }.inject("") do |accumulator, div| times, target = target.divmod(div) accumulator << roman_map[div] * times end roman_value end @roman_table end |
Oh, this can be optimized! In different ways. So I tried.
First question: why is it needed to sort the same array 4000 times? Oh, because the ROMAN_MAP is in ascending order and we need it in descending order. Let’s put the original array in descending order to begin with, and then there is no need for reversing it each iteration:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
def roman_table_inverted return @roman_table if @roman_table roman_map = { 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" } @roman_table = Array.new(3999) do |index| target = index + 1 roman_value = roman_map.keys.inject("") do |accumulator, div| times, target = target.divmod(div) accumulator << roman_map[div] * times end roman_value end @roman_table end |
Is it better? How do I know? By how much? Let’s benchmark it with benchmark-ips (bigger is better :P):
|
original_keys 25.252 (±23.8%) i/s - 112.000 in 5.032620s inverted_keys 37.760 (±37.1%) i/s - 140.000 in 5.056769s |
Ok, what else? roman_map.keys does not change and is called for every iteration. It can be put outside the loop:
|
keys = roman_map.keys @roman_table = Array.new(3999) do |index| target = index + 1 roman_value = keys.inject("") do |accumulator, div| times, target = target.divmod(div) accumulator << roman_map[div] * times end roman_value end |
|
original_keys 23.618 (±25.4%) i/s - 106.000 in 5.017655s inverted_keys 37.309 (±29.5%) i/s - 162.000 in 5.043760s keys_outside_loop 41.393 (±31.4%) i/s - 168.000 in 5.224296s |
Ok, not too big of an improvement. Now take a closer look at the behaviour implemented for each key (called ‘div’ in the code). If the div is greater than the target number, the division is always 0 and the accumulator does not change. We can make the comparison upfront, saving unnecessary division, modulus, multiplication by 0 and trying to add empty strings to the accumulator:
|
keys = roman_map.keys @roman_table = Array.new(3999) do |index| target = index + 1 roman_value = keys.inject("") do |accumulator, div| if div > target next else times, target = target.divmod(div) accumulator << roman_map[div] * times end end roman_value end @roman_table |
|
original_keys 25.419 (±19.7%) i/s - 122.000 in 5.053339s inverted_keys 37.964 (±34.2%) i/s - 150.000 in 5.044594s keys_outside_loop 40.720 (±27.0%) i/s - 180.000 in 5.025812s no_unnecessary_ops 81.137 (±16.0%) i/s - 400.000 in 5.199823s |
Not bad!
Still, a lot of calculations are being repeated over and over. For instance, for the number 324, the “24” part we already calculated when 24 was the target. Also, for 24, we already constructed the 4 part when 4 was the target. We can improve this code by not repeating calculations we already did. This caching should improve the performance significantly:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
|
keys = roman_map.keys @roman_table = [] (0..3998).each do |index| target = index + 1 roman_value = "" keys.each do |div| if div > target next else if @roman_table[target-1] roman_value << @roman_table[target-1] break else times, target = target.divmod(div) roman_value << roman_map[div] * times end end end @roman_table << roman_value end |
|
original_keys 25.419 (±19.7%) i/s - 122.000 in 5.053339s inverted_keys 37.964 (±34.2%) i/s - 150.000 in 5.044594s keys_outside_loop 40.720 (±27.0%) i/s - 180.000 in 5.025812s no_unnecessary_ops 81.137 (±16.0%) i/s - 400.000 in 5.199823s with_memory 228.699 (± 7.9%) i/s - 1.144k in 5.036505s |
And indeed it does speed up things!
The code is available on github.
This is about learning and improving. Not all the code in an needs to be super performant, and surely this method didn’t from the perspective of a beginner rubyist starting to grasp the language.
Learn to pick the right battles. Try to improve the parts that cause the most pain, that are used the most often. And remember that for the most part, performance tuning is a tradeoff between computation, memory and readability/maintainability.