XSを初めて使ってみるための下準備

とりあえず簡単そうな例で性能に差が出そうなものということで
NQueenを実装してみた. 仕事が忙しいため本日は Perlバージョンのみ.

Mooseを使ったので, それのオーバヘッドもいくらか出ているかもしれない
けど, 時間のかかるプログラムなので考慮する必要はないかなと思います.

package Solver::NQueen::Pure;
use Moose;

has size => (
    is       => 'rw',
    isa      => 'Int',
    required => 1,
);

has answer => (
    is      => 'rw',
    isa     => 'Int',
    default => 0,
);

has board => (
    is  => 'rw',
    isa => 'ArrayRef[Int]',
    default => sub { +[] },
);

__PACKAGE__->meta->make_immutable;

no Moose;

sub solve {
    my $self = shift;
    $self->answer(0);

    $self->_nqueen(0);

    return $self->answer;
}

sub _nqueen {
    my ($self, $now) = @_;

    my $size = $self->size;
    for (my $i = 0; $i < $size; $i++) {
        my $flag = 1;

        for (my $j = 0; $j < $now; $j++) {
            my $pos = $self->board->[$j];

            if ($i == $pos) {
                $flag = 0;
            }

            if ($i - ($now - $j) == $pos) {
                $flag = 0;
            }

            if ($i + ($now - $j) == $pos) {
                $flag = 0;
            }
        }

        if ($flag == 1) {
            if ($now == $self->size - 1) {
                $self->answer( $self->answer + 1 );
            } else {
                $self->board->[$now] = $i;
                $self->_nqueen($now + 1);
            }
        }
    }
}

1;

一応ちゃんと動くかのテストを示す.

#!/usr/bin/perl
use strict;
use warnings;
use Test::More qw(no_plan);

use Solver::NQueen::Pure;

my $nqueen = Solver::NQueen::Pure->new( size => 8 );

ok($nqueen);
isa_ok($nqueen, "Solver::NQueen::Pure");
can_ok("Solver::NQueen::Pure", "solve");

is($nqueen->solve(), 92, "size 8");

$nqueen->size(1);
is($nqueen->solve(), 1, "size 1");

$nqueen->size(10);
is($nqueen->solve(), 724, "size 10");

性能. サイズが 8のものを 10回やって 6.76秒.

timethis 10:  2 wallclock secs ( 1.48 usr +  0.00 sys =  1.48 CPU) @  6.76/s (n=10)

XSは全然わからないので, 参考書籍でも読んで勉強します.

モダンPerl入門 (CodeZine BOOKS)