From: Joseph McDonald <joe@...>
Date: 2000-12-28T20:08:24+09:00
Subject: [ruby-talk:8167] Re: speedup of anagram finder


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

#!/usr/local/bin/ruby

require "benchmark"

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


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


WORDS = STDIN.read
#fa7(words);

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

and the output:
 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)        

Here's one strange thing... notice that each_byte didn't get
*hit* on it's first run.  Now, if I switch the top 2 tests
I get:

 head -20000 /usr/share/dict/words | ./anagrams2.rb
                      user     system      total        real
each_byte         2.531250   0.054688   2.585938 (  2.673936)
keys              4.312500   0.000000   4.312500 (  4.380338)
keys              3.414062   0.000000   3.414062 (  3.477650)
each_byte         1.812500   0.023438   1.835938 (  1.868376)
keys              3.375000   0.015625   3.390625 (  3.473766)
each_byte         1.843750   0.000000   1.843750 (  1.868625)      

each_byte got bytten ;-)  but so did keys on it's first run.

Well, I'll defintly be throwing out first runs from now on unless
Gotoken says he's found a work-around or I find out what I'm
doing wrong.

thanks,
-joe


> -----Original Message-----
> From: ts [mailto:decoux@moulon.inra.fr]
> Sent: Thursday, December 28, 2000 2:53 AM
> To: ruby-talk ML
> Cc: ruby-talk@netlab.co.jp
> Subject: [ruby-talk:8164] Re: speedup of anagram finder
> 
> 
> >>>>> "J" == Joseph McDonald <joe@vpop.net> writes:
> 
> J> % head -20000 /usr/share/dict/words | ./anagrams2.rb
> J>                       user     system      total        real
> J> keys              5.148438   0.023438   5.171875 (  5.219981)
> J> each_byte         1.835938   0.015625   1.851562 (  1.862386)    
> 
>  I was very surprised by this result, so I've asked Joseph 
> McDonald to send
> me, in a private email, its test.
> 
>  If you take its source and run multiple times "keys" and "each_byte",
> you'll see something like this :
> 
> pigeon% head -20000 words | /usr/bin/ruby anagrams2.rb
>                       user     system      total        real
> keys              3.900000   0.020000   3.920000 (  3.922335)
> each_byte         1.600000   0.000000   1.600000 (  1.599187)
> keys              2.550000   0.000000   2.550000 (  2.550042)
> each_byte         1.600000   0.000000   1.600000 (  1.597049)
> keys              2.550000   0.000000   2.550000 (  2.550949)
> each_byte         1.590000   0.000000   1.590000 (  1.595726)
> pigeon% 
> 
>  See the unusual result 3.900000 for the first run of "keys" (I think that
>  it's the result of the allocation of memory, after ruby can 
> re-use the memory
>  previously allocated)
> 
>  Be carefull with benchmark, especially for the first result.
> 
>  Someone can send me a script where it's possible to see a difference
>  *significative* between an #each and a #for ?
> 
> 
> 
> 
> Guy Decoux
>