From: David Alan Black <dblack@...>
Date: 2000-12-31T20:49:15+09:00
Subject: [ruby-talk:8398] Re: speedup of anagram finder

Hi --

On Sun, 31 Dec 2000, SHULTZ,BARRY (HP-Israel,ex1) wrote:

> > -----Original Message-----
> > From: David Alan Black [mailto:dblack@candle.superlink.net]
> > Sent: Saturday, December 30, 2000 10:40 PM
> > To: ruby-talk@netlab.co.jp
> > Subject: [ruby-talk:8372] Re: speedup of anagram finder
> >
> > 
> > So perhaps we should synchronize our word lists and see what happens.
> 

> I'd appreciate it if you'd send me a zipped version of your word list.

Done (under separate cover).

> Along with word size, I thought maybe the length of the word list
> itself might be a factor, that prime2 has heavy initial overhead
> because of the array and then speeds :0) through the actual
> processing.

But don't all the various methods have to deal with the same array?
Actually, I think word length is the thing.  I've benchmarked the
three methods (yours, your new one, my one) using seven separate word
files; each file contains 10000 words of fixed length.  Here are the
results, edited (using the 'total' columns) for compactness:

word length:  4      5      6      7      8      9     10
            ______________________________________________
primes      1.61   1.81   2.06   2.55   3.15   3.66   4.03
prime2      1.62   1.83   2.09   2.66   3.16   3.71   4.17
unpack      2.55   2.60   2.66   2.71   2.78   2.82   2.90


The thing that leaps out at one is that unpack scales dramatically
better than the others.  On the hunt for why, I tried a hybrid
approach:

   def hybrid(words)
     anagrams, keys, word, key = {}, {}
     for word in words do
       word.chomp!
       key = 1
       word.unpack('c*').each do |c|
	 key *= $asc2prime[c]
       end
       [...]
   end

which behaved a lot like the other primes ones (1.95 up to 3.99).
EXCEPT.... when I commented out the multiplication line, it behaved
more like the original unpack (1.43 to 1.71).  

I wonder whether this has something to do with the conversion from
Fixnum to Bignum as the number gets bigger?


David

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