From: jigaboophelps@...
Date: 2006-11-15T10:35:06+09:00
Subject: first ruby program, how do I make it faster?

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, :parent, :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[i] != long[i])
				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 (!@already.has_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