From: David Alan Black <dblack@...>
Date: 2000-12-28T10:21:37+09:00
Subject: [ruby-talk:8152] Re: speedup of anagram finder

Hello --

That was a great lesson.  I have a couple of follow-up questions.

On Thu, 28 Dec 2000, GOTO Kentaro wrote:

> Hi,
> 
> In message "[ruby-talk:8142] speedup of anagram finder"
>     on 00/12/28, "Joseph McDonald" <joe@vpop.net> writes:
> 
> >any ideas how to speed this up?:
> 
> General hint: 
>    1. Initialize block variables before the block.
>    2. Use destructive method!
>    3. `x.size > 0' ==> `not x.empty?'
>    4. `x.size > n' ==> `x[n]'
>    5. `a = x[0]'   ==> `a, = x'

I assume that #2 is because many non-destructive methods call their
destructive equivalents, so for instance Array#flatten makes a copy of
the object and then calls Array#flatten! on it.  Or is there another
reason?  And is this something that can be depended on permanently?

About #4: it breaks on this:

   a = [1,2,false]
   a.size > 2       => true
   a[2]             => false

> def fa4(words, out = STDOUT)
>   anagrams = {}
>   word, key, lst = nil
>   words.each do |word|

I keep finding that "for x in y" benchmarks faster than #each.
I wish it didn't, because I like #each.  Further research
required....

>     word.chomp!
>     key = word.downcase.split('')
>     key.sort!
>     anagrams[key] ||= Array.new
>     anagrams[key].push(word)

Would there be any disadvantage here to using "[]" instead of
Array.new?  It seems to be a lot faster.

Speaking of which....  I found that storing the hash keys as
strings, in the following manner:

      (anagrams[key.join] ||= []) .push word

sped things up quite a bit.  I'm not sure why that would be, exactly,
but it did seem to be the case.  (Combining it into one line is just
to avoid doing two joins or creating a new variable.)  Yet more
further research....

For what it's worth, here's a tweaked/hacked version of your code.
Some of the changes are things mentioned above; others are just little
experiments, some of which didn't seem to matter much for speed.

   def david(words, out = STDOUT)
     anagrams, word, key, lst = {}    # :-)
     words.each do |word|
       word.chomp!
       key = word.dup
       key.downcase!                  # as many ! as possible
       key = key.split('')
       key.sort!
       (anagrams[key.join] ||= []) .push word
     end
     anagrams.values.each do |lst|
       out.puts lst.join(" ") if lst[1]
     end
   end

Here's some benchmarking, where gotoken is your fa4, and david is the
above.  (I've cut-and-pasted a bit, as I was getting weird results
on first runs, so these are actually second runs.)

			 user     system      total        real
   david             4.600000   0.000000   4.600000 (  4.591789)
   gotoken           6.290000   0.030000   6.320000 (  6.329997)


Much of the speed david() picked up seems to be from "key.join".


David

-- 
David Alan Black
home: dblack@candle.superlink.net
work: blackdav@shu.edu
Web:  http://pirate.shu.edu/~blackdav