From: Boris Glawe <boris@...>
Date: 2004-08-27T08:15:35+09:00
Subject: performance comparison

Hi,

I am implementing one and the same algorithm in different programming languages, 
in order to compare their performance. It's a backtracking algorithm, which 
takes over 115mio recursions to terminate, where the recursion depth isn't 
deeper then 49.

This algorithm searches for a trip with the horse on a chess board, which visits 
every fields exactly once. On a 7x7 board starting from field (4,4), the times 
of execution on my Athlon XP 2800 are as follows

Fastest is C: 4.1 seconds
then C++: 4.5 seconds

  Now I tried ruby: 16 minutes !!

I included the code below. Is this performance difference normal ? We are 
talking about the factor 62 !! Maybe I have done something wrong in my 
algorithm, but I don't know what. It's very straight and doesn't use any 
expensive container operations:

The program consists of 3 Files: Board.rb, Field.rb, springer.rb

Simply execute springer.rb with 3 Parameters: dimension of the board, 
startposition_x and startposition_y

The example from above on a unixshell:

../springer 7 4 4


What's the reason for this big performance difference ? Can one increase speed 
in any way?? Maybe the ruby compiler has to recompile things again and again in 
this recursion and I don't know it?

################ Board.rb 
############################################################################

require "Field"



class Board


private

	attr :num_visisted_fields, true
	attr_reader :fields
	attr_reader :num_fields

	def initialize(dimension)
		@dimension = dimension
		@fields = []
		@trip = []
		@num_fields = dimension*dimension
		@num_visited_fields = 0
		@recursion_count = 0
		create_fields
		search_neighbours
	end


	def create_fields
		for i in 0...dimension
			line = []
			for j in 0...dimension
				line.push(Field.new(i,j))
			end
			@fields.push(line)
		end
	end


	def search_neighbours
		fields.each do |line|
			line.each do |current_field|
				tmp_field = field(current_field.pos_x + 2, current_field.pos_y + 1)
				current_field.neighbours.push(tmp_field) unless ! tmp_field

				tmp_field = field(current_field.pos_x + 1, current_field.pos_y + 2)
				current_field.neighbours.push(tmp_field) unless ! tmp_field

				tmp_field = field(current_field.pos_x - 1, current_field.pos_y + 2)
				current_field.neighbours.push(tmp_field) unless ! tmp_field

				tmp_field = field(current_field.pos_x - 2, current_field.pos_y + 1)
				current_field.neighbours.push(tmp_field) unless ! tmp_field

				tmp_field = field(current_field.pos_x - 2, current_field.pos_y - 1)
				current_field.neighbours.push(tmp_field) unless ! tmp_field

				tmp_field = field(current_field.pos_x - 1, current_field.pos_y - 2)
				current_field.neighbours.push(tmp_field) unless ! tmp_field

				tmp_field = field(current_field.pos_x + 1, current_field.pos_y - 2)
				current_field.neighbours.push(tmp_field) unless ! tmp_field

				tmp_field = field(current_field.pos_x + 2, current_field.pos_y - 1)
				current_field.neighbours.push(tmp_field) unless ! tmp_field
			end
		end
	end

public
	attr :dimension, true
	attr_reader :trip
	attr_reader :recursion_count

	def find_trip (current_field)

		@recursion_count += 1

		current_field.visited = true
		@num_visited_fields += 1
		
		if @num_visited_fields >= @num_fields
			trip.unshift(current_field)
			return
		end

		for neighbour in current_field.neighbours
			
			next if neighbour.visited

			find_trip(neighbour)
			if @num_visited_fields >= @num_fields
				trip.unshift(current_field)
				return
			end
		end
	
		current_field.visited = false
		@num_visited_fields -= 1
	end


	def field(x, y)
		if (x >= @dimension || y >= @dimension || x < 0 || y < 0)
			return nil
		end
		@fields[x][y]
	end

	def print_board
		fields.each do |line|
			line.each do |field|
				print field.to_s
			end
			print "\n"
		end
	end
end




################ Field.rb 
############################################################################




class Field


private

	def initialize(x,y)
		@pos_x = x
		@pos_y = y
		@visited = false
		@neighbours = []
	end

public
	attr_reader :pos_x, :pos_y
	attr :visited, true
	attr :neighbours, true

	def to_s
		"(" + @pos_x.to_s + "," + @pos_y.to_s + ")"
	end


end


################ springer.rb 
############################################################################
#!/usr/bin/env ruby

require "Board"

if ARGV.length != 3
	print 	"usage: springer <dimension> <start_x> <start_y>,\n" +
		"where both <start_x> and <start_y> must be smaller then <dimension>\n"
	Kernel.exit
end


begin
	dimension = Integer(ARGV[0])
	raise ArgumentError unless dimension > 0

	start_x = Integer(ARGV[1])
	raise ArgumentError unless start_x < dimension && start_x >= 0

	start_y = Integer(ARGV[2])
	raise ArgumentError unless start_y < dimension && start_y >= 0

rescue ArgumentError

	print "Parameters must be numeric and useful\n"
	Kernel.exit

end

board = Board.new(dimension)

start_field = board.field(start_x, start_y)

board.find_trip(start_field)

board.trip.each do |field|
	print field.to_s, "\n"
end
print "number of recursions: " + board.recursion_count.to_s  + "\n"

############################################################################