[ruby-talk:8287] Re: speedup of anagram finder

> -----Original Message-----
> From: David Alan Black [mailto:[e-mail]]
> Sent: Thursday, December 28, 2000 1:37 PM
> 
> 
  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. 

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

The idea is this: use the math theorem that upto order of the prime factors,
'every positive integer can be written uniquely as a product of primes'. To
create an integer key for each word, I first setup a hash which maps ascii
codes for a-z and A-Z to the first 26 primes. Then as I each_byte the word,
the key is built of the product of the
primes associated with each letter in the word.

Barry
---------

require 'benchmark'
include Benchmark
  
 def barry(words)
     asc2prime = { 65 => 2 , 66 => 3 , 67 => 5 , 68 => 7 , 69 => 11 ,
               70 => 13, 71 => 17 , 72 => 19 , 73 => 23 , 74 => 29 ,
               75 => 31, 76 => 37 , 77 => 41 , 78 => 43 , 79 => 47 , 80 =>
53 ,
               81 => 59 , 82 => 61 , 83 => 67 , 84 => 71 , 85 => 73 , 86 =>
79 ,
               87 => 83 , 88 => 89 , 89 => 97 , 90 => 101 ,
               97 => 2 , 98 => 3 , 99 => 5 , 100 => 7 , 101 => 11 ,
               102 => 13, 103 => 17 , 104 => 19 , 105 => 23 , 106 => 29 ,
               107 => 31, 108 => 37 , 109 => 41 , 110 => 43 , 111 => 47 ,
112 => 53 ,
               113 => 59 , 114 => 61 , 115 => 67 , 116 => 71 , 117 => 73 ,
118 => 79 ,
               119 => 83 , 120 => 89 , 121 => 97 , 122 => 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] << word
	 keys[key] = 1
       else
	 anagrams[key] = [ word ]
       end
     end
     for key in keys.keys
       puts anagrams[key].join(' ')
     end
   end
   
      def joe(words)
        anagrams = {}
        keys = {}
        word, key = nil
        total = 0
   
        for word in words do
          word.chomp!
          word.downcase!                  # bad -- see *** below (DB)
          key = []
          word.each_byte {|s| key.push(s)}
          key.sort!
          if anagrams[key]
   	 anagrams[key] << word
   	 keys[key] = 1
          else
   	 anagrams[key] = [ word ]
          end
        end
        for key in keys.keys  
          puts anagrams[key].join(' ')
        end
      end

      def devel(words)
        anagrams = {}
        keys = {}
        word, key = nil
        total = 0
   
        for word in words do
          word.chomp!
          key = word.dup
          key.downcase!
          key = key.unpack('c*')      # <= secret weapon :-)
          key.sort!
          if anagrams[key]
   	 anagrams[key] << word
   	 keys[key] = 1
          else
   	 anagrams[key] = [ word ]
          end
        end
        for key in keys.keys
          puts anagrams[key].join(' ')
        end
      end
 
wordlist = File.open("c:/temp/wordlist.txt").read


bm do |x|
  GC.start
  x.report("primes"){barry(wordlist)}
  GC.start
  x.report("joe"){joe(wordlist)  }
  GC.start
  x.report("devel"){devel(wordlist)  }
end

      user     system      total        real
primes  1.923000   0.000000   1.923000 (  1.923000)
joe  2.533000   0.010000   2.543000 (  2.543000)
devel  2.404000   0.010000   2.414000 (  2.413000)