From: "SHULTZ,BARRY (HP-Israel,ex1)" <barry_shultz@...>
Date: 2000-12-31T05:04:31+09:00
Subject: [ruby-talk:8370] Re: speedup of anagram finder

Hi David,
 I saw your post about checking the benchmarks. Could my wordlist.txt
somehow favor my 
implementation? 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.
 
 And in general, I do not understand how calls to dup, downcase!, pack,
sort! and unpack
can be faster than multiplying array ( was 'hash' ) entries during an
each_byte iteration. 
It just seems that they're heavier calculations. That's my intuition, but
can any of the more 
experienced Rubyists comment on that?
 
Stay warm,

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

require 'benchmark'
include Benchmark
     
    def prime2(words)
        asc2prime = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                     0,0,0,0,0,2,3,5,7,11,13,17,19,23,29,31,37,
                     41,43,47,53,59,61,67,71,73,79,83,89,97,101,
                     0,0,0,0,0,0,2,3,5,7,11,13,17,19,23,29,31,37,
                     41,43,47,53,59,61,67,71,73,79,83,89,97,101
                     ]
             
   
        anagrams = {}
        keys = {}
        word = nil
        key = 0
        total = 0
   
        for word in words do
          word.chomp!
          key = 1
          word.each_byte {|s| key *= asc2prime[s]}
          if anagrams[key]
   	 anagrams[key] << (keys[key] = word)
   	 #keys[key] = 1
          else
   	 anagrams[key] = [ word ]
          end
        end
#       for key in keys.keys
#         puts anagrams[key].join(' ')
#       end
      end

   
   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
 
 
bm(10) do |x|
  GC.start
  x.report("prime2"){prime2(wordlist)  }
  GC.start
  x.report("primes"){barry(wordlist)}
  GC.start
  x.report("unpack"){unpack(wordlist)  }
  GC.start
  x.report("prime2"){prime2(wordlist)  }
  GC.start
  x.report("primes"){barry(wordlist)}
  GC.start
  x.report("unpack"){unpack(wordlist)  }
end

******************************************************
                user     system      total        real
prime2      1.873000   0.000000   1.873000 (  1.873000)
primes      1.722000   0.000000   1.722000 (  1.723000)
unpack      1.953000   0.000000   1.953000 (  1.952000)
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)