From: Kristof Bastiaensen <kristof@...>
Date: 2006-08-03T00:55:10+09:00
Subject: Re: For performance, write it in C - Part 3, Source code now available

On Tue, 01 Aug 2006 17:48:41 +0900, Peter Hickman wrote:

> The source code is available from 
> http://peterhi.dyndns.org/write_it_in_c/index.html

Here is another version in Ruby.  It uses a more clever algorithm.
It makes use of the fact that permuting the rows or the columns of
a latin square still gives a latin square.  It also passes a constraint
on the columns that the given number can be in, to reduce the backtracking
even more.

It runs in 15 seconds on my machine, which I find quite acceptable.

I am sure that this algorithm coded in a compiled functional or logic
language would be about as fast, or faster than your C code, but with the
advantages of a higher level language.

I still think you benchmark is flawed, because 
  1) the C program works only for squares of size 5
  2) It shows totally no relevance to the kind of problems that you 
     would use Ruby for.  If you want raw speed for numerical applications,
     then I would suggest to use a functional language (i.e. ocaml).
  3) If your application runs slowly, it is probably better to think first
     about why it is slow, if you can improve the code with faster
     algorithms or removing bottlenecks.

Kristof Bastiaensen

---------------- latin2.rb --------------------
require 'permutation'

$size = (ARGV.shift || 5).to_i
MaxVal = $size-1

RowPermutations = Permutation.new($size).map{|p| p.value}
BaseStr = (2..$size).to_a.join
StrPermutations = Permutation.new($size-1).map{|p| p.project(BaseStr)}

StartColumns = (1..MaxVal).to_a
def init_columns(el)
   a = StartColumns.dup
   a.delete_at(el-1)
   return a
end

def insert(sqr, num, row, columns)
   insert(sqr, num, row+1, columns) if (row == num)
   columns.each do |col|
      next if sqr[row][col] != ?.
      sqr[row][col] = num + ?1
      if (row == MaxVal)
         insert(sqr, num+1, 1, init_columns(num+1))
      elsif (num == MaxVal && row == MaxVal - 1)
         print_solution(sqr)
      else
         insert(sqr, num, row+1, columns - [col])
      end
      sqr[row][col] = ?.
   end
end

def print_solution(sqr)
   RowPermutations.each do |rp|
      StrPermutations.each do |sp|
         0.upto(MaxVal) do |r| 
            print sqr[rp[r]].tr(BaseStr, sp)
            print ":"
         end
         puts
      end
   end
end

$square = [("1" + BaseStr)] +
   Array.new($size-1) { |i| (i+2).to_s + "." * ($size - 1) }

insert($square, 0, 1, StartColumns)