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

Hello --

On Wed, 3 Jan 2001, Jean Michel wrote:

> I  guess I  got  bitten  by the  ruby  benchmarking  bug. The  following

It happens to the best of us :-)

> version  which sidesteps  unpack  and sort  seems  slighly faster  under
> 'benchmark' that  the unpack-sort  version, although  it is  much slower
> under 'profile'.  It seems 'profile' does  a very bad job  of accurately
> reflecting time  spent in various  places, since  its main effect  is to
> enormously  increase the  interpretive  overhead. I  think  ruby needs a
> better 'profile' (kernel help seems necessary).
> 
> def histogram(words) # assumes lower-case words using only a..z
>   anagrams, keys, word, key = {}, {}
>   for word in words do 
>     word.chomp!
>     hist=Array.new(26,0)
>     word.each_byte{|b| hist[b-?a]+=1}
>     key = hist.pack('c*')
>     if anagrams[key] then anagrams[key] << (keys[key] = word)
>     else anagrams[key] = [ word ]
>     end
>   end
> end

My benchmark results for this, on the first 10K words of /usr/dict/words
(lowercased), are:
			 user     system      total        real
   histogram         5.650000   0.010000   5.660000 (  5.658936)
   unpack            2.270000   0.000000   2.270000 (  2.276009)
   histogram         5.530000   0.000000   5.530000 (  5.523607)
   unpack            2.120000   0.000000   2.120000 (  2.123110)

and similar results on lists of fixed-length words.  I'm not sure
why exactly.... but (chez moi, anyway) it seems slow.  


David

-- 
David Alan Black
home: [e-mail]
work: [e-mail]
Web:  http://pirate.shu.edu/~blackdav