From: Joseph McDonald <joe@...>
Date: 2000-12-28T06:31:27+09:00
Subject: [ruby-talk:8142] speedup of anagram finder


any ideas how to speed this up?:

#!/usr/local/bin/ruby
# Takes a list or words, finds all anagrams in it
def find_anagrams(words)
  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|
    puts lst.join(" ") if lst.length > 1
  end
end

words = $stdin
find_anagrams(words);

% head -10000 /usr/share/dict/words | ./anagrams.rb > junker;

It looks like most of the time is spent in split().

The idea comes from Ben Tilly's version at:
http://www.perlmonks.org/index.pl?node_id=33383&lastnode_id=33390

#! /usr/bin/perl -w
use strict;
my @words = <>;
chomp(@words);
&find_anagrams(@words);

# Takes a list or words, finds all anagrams in it
sub find_anagrams {
  my %anagrams;
  foreach my $word (@_) {
    my $key = join '', sort(split(//, lc($word)));
    push @{$anagrams{$key}}, $word;
  }
  foreach my $lst (values %anagrams) {
    if (1 < @$lst) {
      print "@$lst\n";
    }
  }
}

The perl version runs at least twice as fast.

thanks,
-joe