From: Jesse Merriman <jesse.d.merriman@...>
Date: 2007-04-26T11:52:06+09:00
Subject: Re: [QUIZ][SOLUTION] Morse Code (#121)

Here's a slight optimization to the each_translation method in my original
submission:

class String
  # Yield once for each translation of this (Morse code) string.
  def each_translation
    split(//).each_grouping(MinCodeLength, MaxCodeLength) do |group|
      valid = true
      group.map! do |char_arr|
        # Convert arrays of individual dots & dashes to strings, then translate.
        letter = Decode[char_arr.join]
        letter.nil? ? (valid = false; break) : letter
      end
      # Join all the translated letters into one string.
      yield group.join if valid
    end
  end
end

Originally, I would translate every letter in a word, and then throw it out if
any failed to translate. This version breaks out of the map! as soon as any
letter fails, at the expense of two more variables and a few more LOC. I
expected this to speed it up quite a bit, but this test data shows only a
minor improvement for short code strings:

# (All times in seconds)
# Length, Original Time, New Time
0          0.112          0.113
1          0.110          0.109
2          0.106          0.108
3          0.106          0.106
4          0.106          0.106
5          0.108          0.107
6          0.121          0.119
7          0.123          0.121
8          0.125          0.124
9          0.132          0.130
10         0.146          0.145
11         0.188          0.187
12         0.259          0.253
13         0.403          0.390
14         0.713          0.668
15         1.313          1.221
16         2.513          2.342
17         4.959          4.597
18         9.885          9.146
19        19.671         18.208
20        38.729         35.972
21        78.767         71.431
22       159.931        145.794
23       319.763        294.711
24       636.660        590.360
25      1273.474       1169.021

These were all run with prefixes of '...---..-....--.--.-...-.'
The percentage improvement increases as the length of the code to translate
increases, as can be seen in this (noisy) plot:

http://www.jessemerriman.com/images/ruby_quiz/121_morse_code/new_vs_old.png

How far it goes down after that, I don't know, but my guess would be that
eventually it'd approach zero.

-- 
Jesse Merriman
jessemerriman@warpmail.net
http://www.jessemerriman.com/