ITA word puzzle: optimization and wrap-up

At 1.4 seconds, the ITA puzzle solution I dreamed up while on codeine was already fast enough. Since the pain has subsided and I stopped taking the damned pain-killers, I thought I should go back, optimize and clean up. The code is now shorter, and runs about 10 times faster.

The new version is also on refactormycode, where you can critique and suggest changes.

If you want to see different approaches, there are other solutions and discussions of this puzzle in various places.

The optimizations I made were guided by ruby’s own profiler (invoking ruby with the -r profile flag ). The first time it ran, I felt a tinge of embarrassment, seeing that format_units was called 248,440 times, accounting for over 43% of the computation time.

$ruby -r profile ita.rb

  %   cumulative   self              self     total

 time   seconds   seconds    calls  ms/call  ms/call  name

 43.87    84.78     84.78   248440     0.34     0.50  NumberWriter#format_units

 17.99   119.55     34.77   134583     0.26     1.29  NumberWriter#write

...

Caching the 1,000 potential return values for that function in an array immediately brought the execution time down under a second. Optimization can really be that easy sometimes.

Most optimizations were done iteratively, taking whatever operation was taking the most time and trying to find ways to reduce its footprint. When code started getting messy and verbose, I re-factored and got another speed boost. Overall, the exercise was amazingly easy, taking less than 2 hours of total time without involving any complex code.

What astonishes me is that there is still low-hanging fruit for anyone that would want to make this even faster. Half the time is now spent sorting. A better profiler would definitely help, as the one available out of the box only breaks things down by function. However it’s clear that the profiler’s top 5 results could be mostly avoided if string representations of numbers and ranges didn’t have to be created to sort them alphabetically:

$ time ruby -r profile ita.rb

  %   cumulative   self              self     total

 time   seconds   seconds    calls  ms/call  ms/call  name

 31.13     4.84      4.84    64521     0.08     0.15  ITA::Number#<=>

  8.49     6.16      1.32        3   440.00  3676.67  Array#sort

  8.10     7.42      1.26    68831     0.02     0.03  ITA::Number#to_s

  6.43     8.42      1.00    61704     0.02     0.03  ITA::Range#to_s

  6.30     9.40      0.98     6178     0.16     0.33  ITA::NumberWriter#write

  5.14    10.20      0.80        4   200.00  2850.00  Array#each

  4.63    10.92      0.72    64521     0.01     0.01  String#<=>

I don’t feel the need to push this puzzle any further. If you do, go for it, and please share on refactormycode.