From: Joseph McDonald <joe@...>
Date: 2000-12-28T19:12:55+09:00
Subject: [ruby-talk:8163] Re: speedup of anagram finder


> 
> Next!
> 

That's gotta be me.  Well, I had a feeling that the
bottleneck was in the call to split (why it's a bottleneck
I don't know).  So short of writing a "sort" routine for
String (which would probably make this thing fly), I tried
the only thing I knew of to get around calling split.
That was to call each_byte.  It sure made a difference
(don't ask me why, I don't know). 

def fa7(words, out = STDOUT)
  anagrams = {}
  keys = {}
  word, key = nil
  total = 0
  
  for word in words do
    word.chomp!
    word.downcase!
    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
    out.puts anagrams[key].join(' ')
    total = total + 1 
  end
 # puts "total: #{total}"
end

% head -20000 /usr/share/dict/words | ./anagrams2.rb
                      user     system      total        real
keys              5.148438   0.023438   5.171875 (  5.219981)
each_byte         1.835938   0.015625   1.851562 (  1.862386)    

I wonder if a String.sort would be useful?  I can't think
of a reason off the top of my head (except for anagrams
of course. :-) )

thanks,
-joe