From: Boris Glawe <boris@...>
Date: 2004-08-27T19:45:41+09:00
Subject: Re: performance comparison

Olivier D. wrote:
> On 2004-08-26, Boris Glawe <boris@boris-glawe.de> wrote:
> 
>>Fastest is C: 4.1 seconds
>>then C++: 4.5 seconds
>>
>>  Now I tried ruby: 16 minutes !!
> 
> 
> I have 74ms on my P3-450MHz, that must be a mistake in my implementation
> but: could you give us the output of './springer.rb 7 4 4' you were
> expecting. I have: (4, 4) (6, 5) ... with 44 recursions.
> 
> 
> 


44 recursions is impossible, since it needs at least 49 recursions to finish (a 
7x7 board has 49 fields). Here is the output of my  C++ version, since I don't 
want to wait another 16 minutes. The output of my ruby version was the same though.

(0,0);
(2,1);
(0,2);
(1,0);
(3,1);
(4,3);
(6,2);
(5,0);
(4,2);
(6,3);
(5,1);
(3,0);
(2,2);
(0,3);
(1,1);
(3,2);
(5,3);
(6,1);
(4,0);
(5,2);
(6,0);
(4,1);
(2,0);
(0,1);
(1,3);
(0,5);
(2,6);
(3,4);
(5,5);
(3,6);
(1,5);
(2,3);
(0,4);
(1,6);
(2,4);
(1,2);
(3,3);
(5,4);
(6,6);
(4,5);
(6,4);
(5,6);
(3,5);
(1,4);
(0,6);
(2,5);
(4,6);
(6,5);
(4,4);
number of recursions 115583274


 >>	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
 >>...
 >>			end
 >>		end
 >>	end
 >
 >
 > 'unless !' is called 'if' in Ruby ;) and I have a small optimisation:
 >
 >     KNIGHT_MOVES = [ [2, 1], [-1, 2], [-2, -1], [-2, 1] ]
 >
 >     def search_neighbours
 >         @fields.each do |line|
 >             line.each do |current_field|
 >                 KNIGHT_MOVES.each do |move|
 >                     tmp = field( current_field.x + move[0],
 >                       current_field.y + move[1] )
 >                     current_field.neighbours << tmp if tmp
 >                     tmp = field( current_field.x + move[1],
 >                       current_field.y + move[0] )
 >                     current_field.neighbours << tmp if tmp
 >                 end
 >             end
 >         end
 >     end

thanks, this is more elegant. But doesn't help with the performance, since 
search_neighbours is called only once, by the board's constructor. thanks anyway 
! greets Boris