# First ruby program, how do I make it faster?

**URL:** <https://www.ruby-forum.com/t/first-ruby-program-how-do-i-make-it-faster/225930>\
**Category:** Ruby\
**Created:** [November 15, 2006, 2:36am UTC](https://www.ruby-forum.com/t/first-ruby-program-how-do-i-make-it-faster/225930 "2006-11-15T02:36:39Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [November 15, 2006, 2:36am UTC](https://www.ruby-forum.com/t/first-ruby-program-how-do-i-make-it-faster/225930/1 "2006-11-15T02:36:39Z")

</div>

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/dict.rb)  
[http://www.people.virginia.edu/~kjl3d/PQ.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

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [November 15, 2006, 5:20am UTC](https://www.ruby-forum.com/t/first-ruby-program-how-do-i-make-it-faster/225930/2 "2006-11-15T05:20:54Z")

</div>

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!