From: David Alan Black <dblack@...>
Date: 2000-12-31T05:39:43+09:00
Subject: [ruby-talk:8372] Re: speedup of anagram finder

Hello --

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

> Hi David,
>
> I saw your post about checking the benchmarks. Could my
> wordlist.txt somehow favor my implementation?

Could be: see below.

> I wonder. Could you try benchmarking prime2 and tell me how
> that compares?
> 
>  Here's prime2. Improvements: 1) ugly array instead of ugly hash asc2prime
>  2) use your trick to eliminate line: keys[key] = 1. I'm still a newbie;
>  it took me a while to figure out what << (keys[key] = word) does.

Funny -- I actually went back to the two-line version (slightly
faster, I think).  But I'll benchmark with the sly, side-effect-based
technique :-)  (I'm just using second-round results, to save space.)

		   user     system      total        real
   prime2      3.170000   0.000000   3.170000 (  3.166510)
   primes      3.190000   0.000000   3.190000 (  3.191548)
   unpack      2.590000   0.000000   2.590000 (  2.594617)

Compared with yours:

> prime2      1.622000   0.000000   1.622000 (  1.622000)
> primes      1.643000   0.000000   1.643000 (  1.642000)
> unpack      1.722000   0.000000   1.722000 (  1.723000)
> 

I think that this may indeed come down to the lengths of the words.
When I use a file of all five-letter words, I get:

		   user     system      total        real
   primes      2.410000   0.000000   2.410000 (  2.406790)
   prime2      2.380000   0.000000   2.380000 (  2.379698)
   unpack      3.280000   0.010000   3.290000 (  3.289801)

So perhaps we should synchronize our word lists and see what happens.

Meanwhile, another thing that might be useful here is generalizing the
creation of the prime number array or hash:

   require 'mathn'

   pr = [*0...26]
   p = Prime.new
   primes = pr.map do p.next end

   $asc2prime = {}
   for n in [65,97] do
     pr.each do |x| $asc2prime[x + n] = primes[x] end
   end

or something.  This is probably best done outside the anagram method
(hence the global $asc2prime).

> Stay warm,
> 
>  Barry, not snowbound ( in fact, my family and I were in a park
> flower-gazing today )

It's letting up a bit.  I can see the rear-view mirror of my car
poking up out of the snow.  The funny part is that my cousins from
Texas are visiting, and are now marooned at a Motel 6.


David

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