From: Christoph Rippel <crippel@...>
Date: 2000-12-30T08:40:02+09:00
Subject: [ruby-talk:8315] Re: speedup of anagram finder


"SHULTZ,BARRY (HP-Israel,ex1)" <barry_shultz@hp.com> wrote in message
news:733CA39D4982D411AD080090278CBE390BCCE8@shalom.israel.hp.com...
> > -----Original Message-----
> > From: David Alan Black [mailto:dblack@candle.superlink.net]
> > 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]}
Hm,

isn't something like

key = 0
word.each_byte do |s|
    key << 5  # multiply by 32
    if  s < 97
          key+= s - 64
    else
          key+= s - 96
    end
end

much simpler (and  faster)?

Christoph