From: Jeremy Hinegardner <jeremy@...>
Date: 2007-05-10T15:12:26+09:00
Subject: Re: What's the most ruby-ish way to write this python code?

--u3/rZRmxL6MmkK24
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

Well this was find diversion for the evening :-)

Original python
> >[word[0:i]+c+word[i+1:] for i in range(len(word)) for c in letters]


2007/5/9, Drew Olson <olsonas@gmail.com>:
> >(0...word.size).inject([]) do |words,i|
> >  letters.split('').each do |c|
> >    words << word[0...i]+c+word[i+1..-1]
> >  end
> >  words
> >end

On Thu, May 10, 2007 at 06:38:12AM +0900, Raf Coremans wrote:
> The fastest executing algorithm that I could find was:
> ar = []
> (0...word.size).each do |i|
>  letters.split(//).each do |c|
>    ar << word.dup
>    ar[-1][i] = c
>  end
> end

I managed to get a few on my machine that were as fast or faster than
what was given so far.  One thing that would work in all of the above
code would be to precompute 'letters' into an array before entering any
of the loops.  Since that's a known nconstant we can generate that with:

    LETTERS = ('a'..'z').to_a

and then use it in everywhere. Replacing the above in Raf and Drew's
solution cut some good time off.  I did play with using a Range instead
of an Array for LETTERS, but the array turned out to be more efficient.

The two solutions I came up with that were as fast or faster than what
was already give were:

1) speed up using concat instead of append (fastest I found)

    word = "ruby"
    ar = [] 
    word.size.times do |x|
        ar = ar.concat LETTERS.collect { |l| z = word.dup ; z[x] = l ; z } 
    end

2) speed up with pre computing the result set, this one is very close to
   the time of Raf's using the LETTERS array, but slower than (1)
  
   In this one we generate an array holding the original word and then a
   parallel one holding the replacement letter for the first.  We then
   use integer math to calculate the appropriate index of the letter in
   the word in the first array to replace with the letter from the
   second array.

    word         = "ruby"
    lsize        = LETTERS.size 
    words        = Array.new(word.size * lsize) { word.dup }
    replacements = LETTERS * word.size
    words.size.times { |i| words[i][i/lsize] = replacements[i] }

Both of these generate duplicates, and so I played with using a Set
instead of an Array, but in my testing using a Set was more expensive
than using an Array and then calling .uniq! on the result.

Of the two I think (1) is the more rubyesque of what I put together.

I've attached the benchmark script I was playing with to find out what
was the fastest method for folks to have fun with. 

enjoy,

-jeremy

-- 
========================================================================
 Jeremy Hinegardner                              jeremy@hinegardner.org 


--u3/rZRmxL6MmkK24
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="gen-words.rb"

#!/usr/bin/env ruby

require 'benchmark'
include Benchmark
LETTERS = ('a'..'z').to_a
LETTERS_S = LETTERS.join("")
WORD    = "ruby"


def drew_inject_split
    (0...WORD.size).inject([]) do |words,i|
        LETTERS_S.split('').each do |c|
            words << WORD[0...i]+c+WORD[i+1..-1]
        end
        words
    end
end

def drew_inject_array
    (0...WORD.size).inject([]) do |words,i|
        LETTERS.each do |c|
            words << WORD[0...i]+c+WORD[i+1..-1]
        end
        words
    end
end


def drew_map_split
    (0...WORD.size).map do |i|
        LETTERS_S.split('').map do |c|
            WORD[0..i]+c+WORD[i+1..-1]
        end
    end.flatten
end

def drew_map_array
    (0...WORD.size).map do |i|
        LETTERS.map do |c|
            WORD[0..i]+c+WORD[i+1..-1]
        end
    end.flatten
end

def raf_split
    ar = []
    (0...WORD.size).each do |i|
        LETTERS_S.split(//).each do |c|
            ar << WORD.dup
            ar[-1][i] = c
        end
    end
    ar
end

def raf_array
    ar = []
    (0...WORD.size).each do |i|
        LETTERS.each do |c|
            ar << WORD.dup
            ar[-1][i] = c
        end
    end
    ar
end

def jeremy_1
    ar = []
    WORD.size.times do |x|
        ar = ar.concat LETTERS.collect { |l| z = WORD.dup ; z[x] = l ; z }
    end
    ar
end

require 'set'
def jeremy_1_set
    set = Set.new
    WORD.size.times do |x|
        set.merge(LETTERS.collect { |l| z = WORD.dup ; z[x] = l ; z })
    end
    set
end

def jeremy_2
    ar = Array.new(WORD.size * LETTERS.size) { WORD.dup }
    ar.size.times do |i|
        ar[i][i / LETTERS.size] = LETTERS[i % LETTERS.size]
    end
    ar
end

def jeremy_3
    ar = Array.new(WORD.size * LETTERS.size) { WORD.dup }
    lsize = LETTERS.size
    ar.size.times do |i|
        ar[i][i / lsize] = LETTERS[i % lsize]
    end
    ar
end

def jeremy_4
    ar = Array.new(WORD.size * LETTERS.size) { WORD.dup }
    lsize = LETTERS.size
    replacements = LETTERS * WORD.size

    ar.size.times do |i|
        ar[i][i / lsize] = replacements[i]
    end
    ar
end

def jeremy_5
    ar = []
    w_index = (0...WORD.size).to_a
    LETTERS.each do |l|
        ar = ar.concat w_index.collect { |i| z = WORD.dup ; z[i] = l ; z } 
    end
    ar
end

def run_benchmark
    Benchmark.bmbm(20) do |x|
        x.report("Drew 1 - inject/split") { 1000.times { drew_inject_split } }
        x.report("Drew 1 - inject/array") { 1000.times { drew_inject_array} }
        x.report("Drew 2 - map/split"   ) { 1000.times { drew_map_split } }
        x.report("Drew 2 - map/array"   ) { 1000.times { drew_map_array} }
        x.report("Raf    - split"       ) { 1000.times { raf_split } }
        x.report("Raf    - array"       ) { 1000.times { raf_array} }
        x.report("jeremy - 1"           ) { 1000.times { jeremy_1 } }
        x.report("jeremy - 1 - set "    ) { 1000.times { jeremy_1_set } }
        x.report("jeremy - 1 - uniq!"    ) { 1000.times { jeremy_1.uniq! } }
        x.report("jeremy - 2"           ) { 1000.times { jeremy_2 } }
        x.report("jeremy - 3"           ) { 1000.times { jeremy_3 } }
        x.report("jeremy - 4"           ) { 1000.times { jeremy_4 } }
        x.report("jeremy - 4 - uniq!"    ) { 1000.times { jeremy_4.uniq! } }
        x.report("jeremy - 5"           ) { 1000.times { jeremy_5} }
    end
end

if __FILE__ == $0
    valid = drew_inject_split
    [:jeremy_1, :jeremy_1_set, :jeremy_2, :jeremy_3, :jeremy_4, :jeremy_5].each do |m|
        j = send(m)
        puts "result of #{m} => #{(j - valid).size}"
    end
    run_benchmark
end


--u3/rZRmxL6MmkK24--