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

Hi,

In message "[ruby-talk:8142] speedup of anagram finder"
    on 00/12/28, "Joseph McDonald" <[e-mail]> writes:

>any ideas how to speed this up?:

General hint: 
   1. Initialize block variables before the block.
   2. Use destructive method!
   3. `x.size > 0' ==> `not x.empty?'
   4. `x.size > n' ==> `x[n]'
   5. `a = x[0]'   ==> `a, = x'

>#!/usr/local/bin/ruby
># Takes a list or words, finds all anagrams in it
>def find_anagrams(words)
>  anagrams = {}
# Insert here,
   word = key = lst = nil
>  words.each do |word|
>    word.chomp!
>    key = word.downcase.to_s.split('').sort
# Change this line to 
     key = word.downcase.split('')
     key.sort!
>    anagrams[key] ||= Array.new
>    anagrams[key].push(word)
>  end
>  anagrams.values.each do |lst|
>    puts lst.join(" ") if lst.length > 1
#Change this line to 
     puts lst.join(' ') if lst[1]
>  end
>end
>
>words = $stdin
# I prefer
 words = STDIN
>find_anagrams(words);

With gradually improving, I got:

                      user     system      total        real
original          3.140625   0.039062   3.179688 (  3.196727)
omit to_s         2.007812   0.000000   2.007812 (  2.013872)
block var         1.851562   0.000000   1.851562 (  1.848976)
lst[1]            1.835938   0.007812   1.843750 (  1.846437)
sort!             1.773438   0.007812   1.781250 (  1.783654)

-- Gotoken

require "benchmark"
def fa0(words, out = STDOUT)
  anagrams = {}
  words.each do |word|
    word.chomp!
    key = word.downcase.to_s.split('').sort
    anagrams[key] ||= Array.new
    anagrams[key].push(word)
  end
  anagrams.values.each do |lst|
    out.puts lst.join(" ") if lst.length > 1
  end
end

def fa1(words, out = STDOUT)
  anagrams = {}
  words.each do |word|
    word.chomp!
    key = word.downcase.split('').sort
    anagrams[key] ||= Array.new
    anagrams[key].push(word)
  end
  anagrams.values.each do |lst|
    out.puts lst.join(" ") if lst.length > 1
  end
end

def fa2(words, out = STDOUT)
  anagrams = {}
  word, key, lst = nil
  words.each do |word|
    word.chomp!
    key = word.downcase.split('').sort
    anagrams[key] ||= Array.new
    anagrams[key].push(word)
  end
  anagrams.values.each do |lst|
    out.puts lst.join(" ") if lst.length > 1
  end
end

def fa3(words, out = STDOUT)
  anagrams = {}
  word, key, lst = nil
  words.each do |word|
    word.chomp!
    key = word.downcase.split('').sort
    anagrams[key] ||= Array.new
    anagrams[key].push(word)
  end
  anagrams.values.each do |lst|
    out.puts lst.join(" ") if lst[1]
  end
end

def fa4(words, out = STDOUT)
  anagrams = {}
  word, key, lst = nil
  words.each do |word|
    word.chomp!
    key = word.downcase.split('')
    key.sort!
    anagrams[key] ||= Array.new
    anagrams[key].push(word)
  end
  anagrams.values.each do |lst|
    out.puts lst.join(" ") if lst[1]
  end
end

WORDS = STDIN.read

Benchmark::bm(16) do |job|
  GC.start
  job.report("original") {fa0(WORDS, open('/dev/null', 'w'))}
  GC.start
  job.report("omit to_s"){fa1(WORDS, open('/dev/null', 'w'))}
  GC.start
  job.report("block var"){fa2(WORDS, open('/dev/null', 'w'))}
  GC.start
  job.report("lst[1]")   {fa3(WORDS, open('/dev/null', 'w'))}
  GC.start
  job.report("sort!")    {fa4(WORDS, open('/dev/null', 'w'))}
end