From: David Alan Black <dblack@...>
Date: 2000-12-30T21:57:58+09:00
Subject: [ruby-talk:8352] Re: speedup of anagram finder

Hello --

On Sat, 30 Dec 2000, SHULTZ,BARRY (HP-Israel,ex1) wrote:

>   I spent some time today working on a solution to this that seems
> faster ( please check the benchmarks if you're interested ). It uses
> most of the same code David and several other people used, but it
> also makes use of some high school math for improving the speed.

High school was a long time ago :-)  I'm not sure whether we learned
that thing about primes... but anyway, I found your reimplementation
very intereresting.

>  Advantages: 1) no word.downcase! call needed; 2) no word.sort! call
> needed; 3) no key.push call needed ( in my solution, key is an
> integer, not an array )
> 
> Disadvantages: my solution includes an ugly hash called asc2prime

Disadvantage #2: it choked on "Bhagavad-Gita".  Hmmmm.... we never did
establish guidelines for things like non-alphabetical characters (not
a *huge* problem, but hey, I didn't write /usr/dict/words :-)  And
hard-coding the ASCII set could be regarded as a further disadvantage,
if one ever wanted to internationalize the code.

Anyway -- the following slightly tweaked version of the unpack-based
implementation:

   def unpack(words)
     anagrams, keys, word, key = {}, {}
     for word in words do
       word.chomp!
       key = word.dup
       key.downcase!
       chars = key.unpack('c*')
       chars.sort!
       key = chars.pack('c*')
       if anagrams[key]
	 anagrams[key] << (keys[key] = word)
       else
	 anagrams[key] = [ word ]
       end
     end
   end

benchmarks faster than the primes version.  Note: I have removed the
final output loop, as it's identical in both cases.  (I've also
removed the first runs, to compensate for First Report Time-Distension
Syndrome.)

		   user     system      total        real
   primes      3.520000   0.000000   3.520000 (  3.789767)
   unpack      2.490000   0.000000   2.490000 (  2.485712)

I keep thinking there must be a way to make that if clause more
concise, but I have been unable to do it without slowing the thing
down.


David

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