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

On Thu, 28 Dec 2000, Joseph McDonald wrote:

> 
> Yup.  Sorry about posting inaccurate benchmarks.
> Here is the whole test:

[...]

>  head -20000 /usr/share/dict/words | ./anagrams2.rb
>                       user     system      total        real
> keys              5.109375   0.062500   5.171875 (  5.226218)
> each_byte         1.835938   0.023438   1.859375 (  1.888366)
> keys              3.367188   0.000000   3.367188 (  3.421602)
> each_byte         1.835938   0.000000   1.835938 (  1.908974)
> keys              3.343750   0.007812   3.351562 (  3.444110)
> each_byte         1.820312   0.015625   1.835938 (  1.846535)        


OK, to make up for my earlier complete waste of electrons (Joe,
you think *you* posted inaccurate results!), here is something
which I really and truly believe speeds things up.  Most
recent joe() first, followed by devel()....

   require "benchmark"

   def joe(words, out = STDOUT)
     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
       out.puts anagrams[key].join(' ')
     end
   end

# *** Note that some words may actually contain uppercase
# letters -- so word.downcase! is a bad idea.  (Hence I'd used key =
# word.dup and then operated on key.)

   def devel(words, out = STDOUT)
     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
       out.puts anagrams[key].join(' ')
     end
   end

   WORDS = STDIN.read

   Benchmark::bm(16) do |job|
     GC.start
     job.report("joe")    {joe(WORDS, open('/dev/null', 'w'))}
     GC.start
     job.report("devel")    {devel(WORDS, open('/dev/null', 'w'))}
     GC.start
     job.report("joe")    {joe(WORDS, open('/dev/null', 'w'))}
     GC.start
     job.report("devel")    {devel(WORDS, open('/dev/null', 'w'))}
   end

__END__

   % head -10000 /usr/dict/words  | ruby anagrams.rb
			 user     system      total        real
   joe               3.550000   0.050000   3.600000 (  3.599468)
   devel             2.420000   0.010000   2.430000 (  2.430312)
   joe               3.140000   0.000000   3.140000 (  3.145125)
   devel             2.410000   0.000000   2.410000 (  2.406263)


This time around, using 'join' on the array slowed things down,
so I took it out.


David

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