Jeremy Hinegardner
5/10/2007 6:12:00 AM
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