first ruby program, how do I make it faster?

[jigaboophelps]

I wrote my first ruby program recently, a word-chain finder, and I
would like some hints on how to speed it up. When I looked for a
priority queue to use in the a-star search, I found that this problem
was also a ruby quiz last year. Anyway, I profiled my application with
require 'profile' and it says most of the time is spent in Array.each.
I'm looking mostly for ruby tips, not really algorithm tips, to the
extent that they can be separated. I use a regular a-star search where
the heuristic is number of characters different. I don't do any
preprocessing, except store the dictionary entries in an array along
with other words of the same length. Anyway, the code is below and
also at:

http://www.people.virginia.edu/~kjl3d/dict.rb
http://www.people.virginia.edu/~kjl3d/PQ.rb

Thanks so much in advance!

--------dict.rb:
#!/usr/bin/ruby -w

require 'PQ'

$apos = /\'/
$cap = /^[A-Z]/

class Dictionary
def initialize
@dicts = Hash.new { |h, v| h[v] = [] }
IO.foreach("american-english") do |line|
line.chomp!
line.downcase!
if (!$apos.match(line) && !$cap.match(line) && line.length > 0)
@dicts[line.length] << line
end
end
end
def neighbors(word)
nbrs_same = []
for i in 0 ... word.length
regex = Regexp.new(word[0...i] + "." + word[(i+1)..-1])
nbrs_same << @dicts[word.length].find_all { |dword| regex =~ dword }
end
return nbrs_same.flatten!
end
end

class Node
attr_reader :value, arent, :so_far, :estDist
def initialize(parent, estDistance, value, so_far)
@parent = parent
@estDist = estDistance
@value = value
@so_far = so_far
end
def getTotalH
return @so_far + @estDist
end
def getChain
return prependToChain("").chop!
end
def prependToChain(str)
str = value + " " + str
if (nil != parent)
return parent.prependToChain(str);
else
return str
end
end
end

class Finder
def initialize(dict)
@dict = dict;
@q = PQ.new { |obj| obj.getTotalH }
@already = Hash.new
end
def Finder.calcH(word1, goal)
sum = 0
if (word1.length < goal.length)
short = word1
long = goal
else
short = goal
long = word1
end
for i in 0 ... short.length do
if (short != long)
sum += 1
end
end
return sum + (long.length - short.length)
end
def getNeighbors(n, goal)
word_neighbors = @dict.neighbors(n.value)
arr = []
word_neighbors.each do |w|
if ([email protected]_key?(w))
@already[w] = 1
arr << Node.new(n, Finder.calcH(w,goal), w, n.so_far + 1)
end
end
return arr
end
def findNode(word1, goal)
val = Finder.calcH(word1,goal)
init = Node.new(nil, val, word1, 0)
@q.add(init)
while ((n = @q.get_smallest) != nil)
puts "checking #{n.getChain} t = #{n.getTotalH} h = #{n.estDist}"
return n if (n.value == goal)
neighbors = getNeighbors(n, goal)
neighbors.each do |nbr|
# puts "\t" + nbr.value + " " + nbr.getTotalH.to_s
@q.add(nbr)
end
end
return nil
end
def findPath(word1, goal)
n = findNode(word1, goal)
# trace ancestors of n
if (n == nil)
puts "got nothing!"
else
puts n.getChain
end
end
end


if ($0 == __FILE__)
if (ARGV.length > 1)
dictionary = Dictionary.new
finder = Finder.new(dictionary)
finder.findPath(ARGV[0], ARGV[1])
else
puts "pass in 2 strings"
end
end

----------------PQ.rb:

class PQ
def initialize(&getMin)
puts "pass a block to PQ" if (getMin == nil)
@getMin = getMin
@storage = Hash.new { |hash, key| hash[key] = [] }
end
def add(node)
@storage[@getMin.call(node)].unshift(node)
end
def get_smallest
return nil if @storage.empty?
key, val = *@storage.min
result = val.shift
@storage.delete(key) if val.empty?
return result
end
end

 

[greg]

each will normally profile high because it will be called in multiple
places and it will execute a block of code. You need to figure out
which actual chunk of code, or as may be the case, which each block is
actually profiling the highest.

One tip- it seems that you are checking to see if a string is
capatalized after already using downcase!