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

Hi David,

> -----Original Message-----
> From: David Alan Black [mailto:dblack@candle.superlink.net]
> Sent: Saturday, December 30, 2000 2:58 PM

> Disadvantage #2: it choked on "Bhagavad-Gita".  Hmmmm.... we never did
> establish guidelines for things like non-alphabetical characters (not
> a *huge* problem, but hey, I didn't write /usr/dict/words :-)  And

I think that's a minor problem, fixed with the obvious adjustment ( for all
ascii, just use the same 
idea using the first 256 primes instead of the first 26 ). Of course, that
would make the 
hash even uglier!

> hard-coding the ASCII set could be regarded as a further disadvantage,
> if one ever wanted to internationalize the code.
> 

I'll have to think about that one. 

> Anyway -- the following slightly tweaked version of the unpack-based
> implementation:
> 
>    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
> 
> benchmarks faster than the primes version.  Note: I have removed the
> final output loop, as it's identical in both cases.  (I've also
> removed the first runs, to compensate for First Report Time-Distension
> Syndrome.)
> 
> 		   user     system      total        real
>    primes      3.520000   0.000000   3.520000 (  3.789767)
>    unpack      2.490000   0.000000   2.490000 (  2.485712)
> 

My benchmarks are different; they still show primes as faster. Below you'll
find what I've done.
Can someone tell me what's wrong with it?? 
In the meantime, I'll try to make "primes" a little faster still. This is
fun and interesting,
but what's even nicer for me, from the mathematical side, is that I can now
make 
statements like the following ( please excuse the mathematical jargon :-) ):

Let S be the set of all ascii strings, x,y be in S and s(x) =  some
"asc2prime-like" function.
Let [x] be the class of x in S modulo the "anagram" equivalence relation.
Then s(x) = s(y) iff [x] = [y].

Sorry for the digression. It is for gotoken and anyone else who likes this
stuff.

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 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
 
wordlist = File.open("c:/temp/wordlist.txt").read


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


                user     system      total        real
primes      1.943000   0.000000   1.943000 (  1.933000)
unpack      1.952000   0.000000   1.952000 (  1.953000)
primes      1.682000   0.000000   1.682000 (  1.682000)
unpack      1.722000   0.000000   1.722000 (  1.723000)