From: William James <w_a_x_man@...>
Date: 2006-07-27T14:20:05+09:00
Subject: Re: For performance, write it in C

Kroeger, Simon (ext) wrote:
> Hi Peter!
>
> > Whenever the question of performance comes up with scripting
> > languages
> > such as Ruby, Perl or Python there will be people whose
> > response can be
> > summarised as "Write it in C". I am one such person. Some people take
> > offence at this and label us trolls or heretics of the true
> > programming
> > language (take your pick).
>
> The last (and only) time I called someone a troll for saying
> 'Write it C' it was in response to a rails related question.
> Further the OP asked for configuration items and such, but maybe
> that's a whole other storry. (and of course you can write
> C Extensions for rails... yeah, yadda, yadda :) )
>
> ..snip 52 lines Perl, some hundred lines C ...
>
> > [Latin]$ time ./Latin1.pl 5 > x5
> >
> > real    473m45.370s
> > user    248m59.752s
> > sys     2m54.598s
> >
> > [Latin]$ time ./Latin4.pl 5 > x5
> >
> > real    12m51.178s
> > user    12m14.066s
> > sys     0m7.101s
> >
> > [Latin]$ time ./c_version.sh 5
> >
> > real    0m5.519s
> > user    0m4.585s
> > sys     0m0.691s
>
> Just to show the beauty of ruby:
> -----------------------------------------------------------
> require 'rubygems'
> require 'permutation'
> require 'set'
>
> $size = (ARGV.shift || 5).to_i
>
> $perms = Permutation.new($size).map{|p| p.value}
> $out = $perms.map{|p| p.map{|v| v+1}.join}
> $filter = $perms.map do |p|
>   s = SortedSet.new
>   $perms.each_with_index do |o, i|
>     o.each_with_index {|v, j| s.add(i) if p[j] == v}
>   end && s.to_a
> end
>
> $latins = []
> def search lines, possibs
>   return $latins << lines if lines.size == $size
>   possibs.each do |p|
>     search lines + [p], (possibs -
> $filter[p]).subtract(lines.last.to_i..p)
>   end
> end
>
> search [], SortedSet[*(0...$perms.size)]
>
> $latins.each do |latin|
>   $perms.each do |perm|
>     perm.each{|p| puts $out[latin[p]]}
>     puts
>   end
> end
> -----------------------------------------------------------
> (does someone has a nicer/even faster version?)

Here's a much slower version that has no 'require'.

Wd = ARGV.pop.to_i
$board = []

# Generate all possible valid rows.
Rows = (0...Wd**Wd).map{|n| n.to_s(Wd).rjust(Wd,'0')}.
  reject{|s| s=~/(.).*\1/}.map{|s| s.split(//).map{|n| n.to_i + 1} }

def check( ary, n )
  ary[0,n+1].transpose.all?{|x| x.size == x.uniq.size }
end

def add_a_row( row_num )
  if Wd == row_num
    puts $board.map{|row| row.join}.join(':')
  else
    Rows.size.times { |i|
      $board[row_num] = Rows[i]
      if check( $board, row_num )
        add_a_row( row_num + 1 )
      end
    }
  end
end

add_a_row 0