RubyとC言語でもペントミノバズルを解いてみる

前回からの続き。

ペントミノパズルを解くPythonコードは、順調に高速化の道を歩んできた。

  • 3時間以上 → 50分 → 20分 → 3分。

ところで、現在はnumpyにほとんど依存しないコードになっている。ならば、他のプログラミング言語でも同じアルゴリズムペントミノパズルを解けるはず。ふと、使い慣れているRubyで書いてみたらどうなるのだろう?と思った。やってみた。

Rubyで解く

  • 完全にPython脳になっていたので、endが必要な書き方に激しく無駄を感じてしまった。
  • いくつかのエラーに悩まされながら、どうにか以下のRubyコードを完成させた。
  • 実行してみると...
# coding: utf-8
BROW, BCOL = 10, 6

# すべてのピース形状をPieceオブジェクトの配列に保存する
class Piece
  attr_accessor :used, :form, :loc_form, :letter

  def initialize(a, m, n, l)
    @used = false
    @form = []
    @loc_form = []
    @letter = l
    for i in (1..m)
      for j in (1..n)
        @form << [a, a.flatten.index(1)]
        a = a.transpose.reverse # rotate L
      end
      a = a.map(&:reverse) # flip LR
    end
  end
end
  
pp = [Piece.new([[0,1,0], [1,1,1], [0,1,0]], 1, 1, :X),
      Piece.new([[1,1,1], [1,0,1]]         , 1, 4, :U),
      Piece.new([[1,1,0], [0,1,1], [0,0,1]], 1, 4, :W),
      Piece.new([[1,1,0], [0,1,1], [0,1,0]], 1, 2, :F),
      Piece.new([[1,1,0], [0,1,0], [0,1,1]], 2, 2, :Z),
      Piece.new([[1,1,1], [1,1,0]],          2, 4, :P),
      Piece.new([[1,1,1,0], [0,0,1,1]],      2, 4, :N),
      Piece.new([[1,1,1,1], [0,1,0,0]],      2, 4, :Y),
      Piece.new([[1,1,1], [0,1,0], [0,1,0]], 1, 4, :T),
      Piece.new([[1,1,1,1], [1,0,0,0]],      2, 4, :L),
      Piece.new([[1,1,1], [1,0,0], [1,0,0]], 1, 4, :V),
      Piece.new([[1,1,1,1,1]],               1, 2, :I)]

pp.each_with_index do |piece, i|
  piece.form.each do |form|
    a = []
    form[0].each_with_index do |row, r|
      row.each_with_index do |col, c|
        a << r * (BCOL + 1) + c - form[1] if col == 1
      end
    end
    piece.loc_form << a
  end
end



# boardの初期化
board = Array.new((BROW + 1) * (BCOL + 1), 0)
board.each_with_index do |b, i|
  board[i] = 100 if ((i + 1) % (BCOL + 1)) == 0 || i >= ((BCOL + 1) * BROW)
end



# パズルの解を求める
def display_board(board, pp)
  $counter += 1
  puts "No. #{$counter}"
  a = []
  board.each_slice(BCOL + 1) do |line|
    a << line.reject {|i| i == 100}.map {|i| pp[i - 1].letter}
  end
  a[0..-2].transpose.each {|line| puts line.join}
  puts
end

def try_piece(board, pp, lvl)
  $try_counter += 1
  x = board.index(0)
  pp.each_with_index do |piece, i|
    next if piece.used
    piece.loc_form.each do |blocks|
      next if board[x + blocks[0]]>0 || board[x + blocks[1]]>0 || board[x + blocks[2]]>0 || board[x + blocks[3]]>0 || board[x + blocks[4]]>0
      # ピースを置く
      blocks.each {|b| board[x + b] = i + 1}
      piece.used = true
      # すべてのピースを置ききったらTrueを返す(recursiveコールの終了)
      if lvl == 11 then
        display_board(board, pp)
        # ピースを戻す
        blocks.each {|b| board[x + b] = 0}
        piece.used = false
        return
      end
      # 次のピースを試す
      try_piece(board, pp, lvl + 1)
      # ピースを戻す
      blocks.each {|b| board[x + b] = 0}
      piece.used = false
    end
  end
end

$counter = 0
$try_counter = 0
try_piece(board, pp, 0)
puts "解合計: #{$counter}"
puts "操作数: #{$try_counter}"

1分切ってる!

$ time ruby pentomino.rb

解合計: 2339
操作数: 10385817

real	0m59.035s
user	0m58.632s
sys	0m0.285s
  • なんと!同じアルゴリズムRubyで書いたら、3倍も高速化されてしまった!
  • 昔からPythonは早くて、Rubyノロマな子、と思い込んでいたので驚いた。
  • ちなみに、各言語のバージョン。
$ python --version
Python 2.7.6

$ ruby --version
ruby 1.9.3p194 (2012-04-20 revision 35410) [x86_64-darwin12.2.0]

C言語で解く

  • 高速化の話はもう終わりと思っていたのに。
  • Rubyで書き直した途端3倍も早くなってしまった!
  • こうなったらC言語で最速を狙いたい気分になる。
  • 完全なスクリプト言語な脳でC言語を触り始めると、もうエラーと警告が嵐のように出まくる。
    • メモリ構造を想像しながら構造体を定義して、
    • 可変長な要素の配列を作ることをあきらめつつ、配列を定義する。
    • 変数や関数は事前にすべて宣言しておかなければならない。
  • いくつもの試練を乗り越えて、ようやく以下のコードが完成する。
#include  <stdio.h>

typedef struct {
  int       pos[5];
} MinoPos;

typedef struct {
  char      name;
  int       used;
  int       formsize;
  MinoPos   form[8];
} Piece;

Piece pieces[] =
{
    {'X', 0, 1, {{0,6,7, 8,14}}},
    {'U', 0, 4, {{0,1,2, 7, 9},{0,1, 7,14,15},{0,2, 7, 8, 9},{0,1, 8,14,15}}},
    {'W', 0, 4, {{0,1,8, 9,16},{0,1, 6, 7,13},{0,7, 8,15,16},{0,6, 7,12,13}}},
    {'F', 0, 2, {{0,1,8, 9,15},{0,6, 7, 8,13}}},
    {'Z', 0, 4, {{0,1,8,15,16},{0,5, 6, 7,12},{0,1, 7,13,14},{0,7, 8, 9,16}}},
    {'P', 0, 8, {{0,1,2, 7, 8},{0,7, 8,14,15},{0,1, 6, 7, 8},{0,1, 7, 8,15},{0,1,2,8, 9},{0,1, 7, 8,14},{0,1,7,8, 9},{0,6, 7,13,14}}},
    {'N', 0, 8, {{0,1,2, 9,10},{0,6, 7,13,20},{0,1, 8, 9,10},{0,7,13,14,20},{0,1,2,6, 7},{0,7,14,15,22},{0,1,5,6, 7},{0,7, 8,15,22}}},
    {'Y', 0, 8, {{0,1,2, 3, 8},{0,7,14,15,21},{0,5, 6, 7, 8},{0,6, 7,14,21},{0,1,2,3, 9},{0,7, 8,14,21},{0,6,7,8, 9},{0,7,13,14,21}}},
    {'T', 0, 4, {{0,1,2, 8,15},{0,7, 8, 9,14},{0,7,13,14,15},{0,5, 6, 7,14}}},
    {'L', 0, 8, {{0,1,2, 3, 7},{0,7,14,21,22},{0,4, 5, 6, 7},{0,1, 8,15,22},{0,1,2,3,10},{0,1, 7,14,21},{0,7,8,9,10},{0,7,14,20,21}}},
    {'V', 0, 4, {{0,1,2, 7,14},{0,7,14,15,16},{0,7,12,13,14},{0,1, 2, 9,16}}},
    {'I', 0, 2, {{0,1,2, 3, 4},{0,7,14,21,28}}},
};

int board[77];
int counter, try_counter;

void init_board(void);
void print_board(void);
void try_piece(int level);
int board_index(int find_num);



void init_board(void)
{
  int i;

  for(i=0; i<77; i++){
    if(((i + 1) % 7) == 0 || i >= 70){
      board[i] = 100;
    }
  }
}

void print_board(void)
{
  int row, col;

  printf("No. %d\n", counter);
  for(row=0; row<6; row++){
    for(col=0; col<70; col += 7){
      printf(" %c", pieces[board[row + col] - 1].name);
    }
    printf("\n");
  }
  printf("\n");
}

int board_index(int find_num)
{
  int i;

  for(i=0; i<77; i++){
    if(board[i] == find_num){
      return i;
    }
  }
  return 0;
}

void try_piece(int level)
{
  int i, j, k, x;

  try_counter++;
  x = board_index(0);
  for(i=0; i<12; i++){
    if(pieces[i].used == 1){continue;}
    for(j=0; j<pieces[i].formsize; j++){
      if(board[x + pieces[i].form[j].pos[0]] ||
         board[x + pieces[i].form[j].pos[1]] ||
         board[x + pieces[i].form[j].pos[2]] ||
         board[x + pieces[i].form[j].pos[3]] ||
         board[x + pieces[i].form[j].pos[4]]){continue;}
      // ピースを置く
      for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k]] = i + 1;}
      pieces[i].used = 1;
      // すべてのピースを置ききったらTrueを返す(recursiveコールの終了)
      if(level == 11){
        counter++;
        print_board();
        // ピースを戻す
        for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k]] = 0;}
        pieces[i].used = 0;
        return;
      }
      // 次のピースを試す
      try_piece(level + 1);
      // ピースを戻す
      for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k]] = 0;}
      pieces[i].used = 0;
    }
  }
}

int main(int argc, char **argv)
{
  init_board();
  try_piece(0);
  printf("解合計: %d\n", counter);
  printf("操作数: %d\n", try_counter);
}

わずか1.2秒で完了した!

  • Rubyの1分からC言語1.2秒へ桁違いの高速化。
$ gcc -O2 pentomino.c
$ time ./a.out
解合計: 2339
操作数: 10385817

real	0m1.256s
user	0m1.237s
sys	0m0.017s
なし real 0m2.789s
-O1 real 0m1.276s
-O2 real 0m1.249s
-O3 real 0m1.292s

-O2が最速だ!

1秒切りたい

  • ここまで来ると、どうしても1秒を切りたくなる。
  • 工夫すべきところは、以下のコード部分だと思う。
...中略...
int board_index(int find_num)
{
  int i;

  for(i=0; i<77; i++){
    if(board[i] == find_num){
      return i;
    }
  }
  return 0;
}

void try_piece(int level)
{
  int i, j, k, x;

  try_counter++;
  x = board_index(0);
  for(i=0; i<12; i++){
    if(pieces[i].used == 1){continue;}
    for(j=0; j<pieces[i].formsize; j++){
      if(board[x + pieces[i].form[j].pos[0]] ||
         board[x + pieces[i].form[j].pos[1]] ||
         board[x + pieces[i].form[j].pos[2]] ||
         board[x + pieces[i].form[j].pos[3]] ||
         board[x + pieces[i].form[j].pos[4]]){continue;}
      // ピースを置く
...中略...
  • この部分はtry_counterが示すとおり1000万回以上も繰り返すのだ。
  • わずかな無駄も1000万回繰り返すと、結構な時間になってしまう...。
board_index()関数の修正
  • まず、board_index()関数の動きに注目してみる。
  • 次にピースを置く場所を決めるために、board配列の先頭から検索して、最初に0が出現するインデックス値を返している。
  • しかし、毎回board配列の先頭から検索するのは無駄である。
  • 少なくとも前回のインデックスxまでは、Pentominoピースで埋まっているはずなので、
  • 次回の検索位置は x+1 から探し始めた方が無駄がないはず。
  • 以下の修正をして、コンパイルして、実行してみると...


@@ -32,8 +32,8 @@ int counter, try_counter;

void init_board(void);
void print_board(void);
-void try_piece(int level);
-int board_index(int find_num);
+void try_piece(int x, int level);
+int board_index(int find_num, int start_pos);



@@ -62,11 +62,11 @@ void print_board(void)
printf("\n");
}

-int board_index(int find_num)
+int board_index(int find_num, int start_pos)
{
int i;

- for(i=0; i<77; i++){
+ for(i=start_pos; i<77; i++){
if(board[i] == find_num){
return i;
}
@@ -74,12 +74,12 @@ int board_index(int find_num)
return 0;
}

-void try_piece(int level)
+void try_piece(int x, int level)
{
- int i, j, k, x;
+ int i, j, k;

try_counter++;
- x = board_index(0);
+ x = board_index(0, x);
for(i=0; i<12; i++){
if(pieces[i].used == 1){continue;}
for(j=0; j<pieces[i].formsize; j++){
@@ -101,7 +101,7 @@ void try_piece(int level)
return;
}
// 次のピースを試す
- try_piece(level + 1);
+ try_piece(x + 1, level + 1);
// ピースを戻す
for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k]] = 0;}
pieces[i].used = 0;
@@ -112,7 +112,7 @@ void try_piece(int level)
int main(int argc, char **argv)
{
init_board();
- try_piece(0);
+ try_piece(0, 0);
printf("解合計: %d\n", counter);
printf("操作数: %d\n", try_counter);
}

ほぼ1秒で完了した!

$ gcc -O2 pentomino.c
$ time ./a.out
解合計: 2339
操作数: 10385817

real	0m1.066s
user	0m1.049s
sys	0m0.016s
ループで回す
  • でもまだ1秒切れてない...。
  • あともう少しなんだけど。
  • board_index()関数を最適化してしまったので、
  • 工夫の余地が残るのは、以下の部分しかない。
  • しかしどう考えても、(A)から(B)まで、これ以上効率的な書き方は想像できない...。
...中略...
void try_piece(int x, int level)
{
  int i, j, k;

  try_counter++; // ......(A)
  x = board_index(0, x);
  for(i=0; i<12; i++){
    if(pieces[i].used == 1){continue;}
    for(j=0; j<pieces[i].formsize; j++){ // ......(B)
      if(board[x + pieces[i].form[j].pos[0]] || // ......(C)
         board[x + pieces[i].form[j].pos[1]] ||
         board[x + pieces[i].form[j].pos[2]] ||
         board[x + pieces[i].form[j].pos[3]] ||
         board[x + pieces[i].form[j].pos[4]]){continue;}
      // ピースを置く
...中略...
  • 残る部分は、(C)の長い条件判定のコード。
  • ピースが置けるかどうかを判定している。
  • 高速化を狙って、あえてループを使わずに展開したのだけど、試しにループで処理してみる。(半分ヤケクソ)
  • 以下の修正をして、コンパイルして、実行してみると...


@@ -77,17 +77,16 @@ int board_index(int find_num, int start_pos)
void try_piece(int x, int level)
{
int i, j, k;
+ int sum;

try_counter++;
x = board_index(0, x);
for(i=0; i<12; i++){
if(pieces[i].used == 1){continue;}
for(j=0; j<pieces[i].formsize; j++){
- if(board[x + pieces[i].form[j].pos[0]] ||
- board[x + pieces[i].form[j].pos[1]] ||
- board[x + pieces[i].form[j].pos[2]] ||
- board[x + pieces[i].form[j].pos[3]] ||
- board[x + pieces[i].form[j].pos[4]]){continue;}
+ sum = 0;
+ for(k=0; k<5; k++){sum += board[x + pieces[i].form[j].pos[k]];}
+ if(sum){continue;}
// ピースを置く
for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k]] = i + 1;}
pieces[i].used = 1;

1秒切った!

$ gcc -O2 pentomino.c
$ time ./a.out
解合計: 2339
操作数: 10385817

real	0m0.974s
user	0m0.958s
sys	0m0.014s
  • 高速化の経過: 3時間以上 → 50分 → 20分(Python) → 3分(Python) → 1分(Ruby) → 1.2秒(C) → 1秒(C) → 0.97秒(C)!
  • 教訓: 場合によっては、コード展開するより、ループ回した方が早い!
    • ループ処理で高速化したわけではなく、条件判定から加算命令に変更した効果であった。
    • その証拠にループを展開した加算命令の方がさらに高速化された。(わずか0.02秒だけど)


- sum = 0;
- for(k=0; k<5; k++){sum += board[x + pieces[i].form[j].pos[k]];}
- if(sum){continue;}
+ if(board[x + pieces[i].form[j].pos[0]] +
+ board[x + pieces[i].form[j].pos[1]] +
+ board[x + pieces[i].form[j].pos[2]] +
+ board[x + pieces[i].form[j].pos[3]] +
+ board[x + pieces[i].form[j].pos[4]]){continue;}

$ gcc -O2 pentomino.c
$ time ./a.out
解合計: 2339
操作数: 10385817

real	0m0.949s
user	0m0.933s
sys	0m0.014s


  • さらなる高速化に気付いた。
  • board[ x + pieces[i].form[j].pos[0] ] が0であることは明白なので、計算を省略できる。


@@ -83,8 +83,7 @@
for(i=0; i<12; i++){
if(pieces[i].used == 1){continue;}
for(j=0; j<pieces[i].formsize; j++){
- if(board[x + pieces[i].form[j].pos[0]] +
- board[x + pieces[i].form[j].pos[1]] +
+ if(board[x + pieces[i].form[j].pos[1]] +
board[x + pieces[i].form[j].pos[2]] +
board[x + pieces[i].form[j].pos[3]] +
board[x + pieces[i].form[j].pos[4]]){continue;}

$ gcc -O2 pentomino.c
$ time ./a.out
解合計: 2339
操作数: 10385817

real	0m0.909s
user	0m0.884s
sys	0m0.014s

最終的なC言語コード

#include  <stdio.h>

typedef struct {
  int       pos[5];
} MinoPos;

typedef struct {
  char      name;
  int       used;
  int       formsize;
  MinoPos   form[8];
} Piece;

Piece pieces[] =
{
    {'X', 0, 1, {{0,6,7, 8,14}}},
    {'U', 0, 4, {{0,1,2, 7, 9},{0,1, 7,14,15},{0,2, 7, 8, 9},{0,1, 8,14,15}}},
    {'W', 0, 4, {{0,1,8, 9,16},{0,1, 6, 7,13},{0,7, 8,15,16},{0,6, 7,12,13}}},
    {'F', 0, 2, {{0,1,8, 9,15},{0,6, 7, 8,13}}},
    {'Z', 0, 4, {{0,1,8,15,16},{0,5, 6, 7,12},{0,1, 7,13,14},{0,7, 8, 9,16}}},
    {'P', 0, 8, {{0,1,2, 7, 8},{0,7, 8,14,15},{0,1, 6, 7, 8},{0,1, 7, 8,15},{0,1,2,8, 9},{0,1, 7, 8,14},{0,1,7,8, 9},{0,6, 7,13,14}}},
    {'N', 0, 8, {{0,1,2, 9,10},{0,6, 7,13,20},{0,1, 8, 9,10},{0,7,13,14,20},{0,1,2,6, 7},{0,7,14,15,22},{0,1,5,6, 7},{0,7, 8,15,22}}},
    {'Y', 0, 8, {{0,1,2, 3, 8},{0,7,14,15,21},{0,5, 6, 7, 8},{0,6, 7,14,21},{0,1,2,3, 9},{0,7, 8,14,21},{0,6,7,8, 9},{0,7,13,14,21}}},
    {'T', 0, 4, {{0,1,2, 8,15},{0,7, 8, 9,14},{0,7,13,14,15},{0,5, 6, 7,14}}},
    {'L', 0, 8, {{0,1,2, 3, 7},{0,7,14,21,22},{0,4, 5, 6, 7},{0,1, 8,15,22},{0,1,2,3,10},{0,1, 7,14,21},{0,7,8,9,10},{0,7,14,20,21}}},
    {'V', 0, 4, {{0,1,2, 7,14},{0,7,14,15,16},{0,7,12,13,14},{0,1, 2, 9,16}}},
    {'I', 0, 2, {{0,1,2, 3, 4},{0,7,14,21,28}}},
};

int board[77];
int counter, try_counter;

void init_board(void);
void print_board(void);
void try_piece(int x, int level);
int board_index(int find_num, int start_pos);



void init_board(void)
{
  int i;

  for(i=0; i<77; i++){
    if(((i + 1) % 7) == 0 || i >= 70){
      board[i] = 100;
    }
  }
}

void print_board(void)
{
  int row, col;

  printf("No. %d\n", counter);
  for(row=0; row<6; row++){
    for(col=0; col<70; col += 7){
      printf(" %c", pieces[board[row + col] - 1].name);
    }
    printf("\n");
  }
  printf("\n");
}

int board_index(int find_num, int start_pos)
{
  int i;

  for(i=start_pos; i<77; i++){
    if(board[i] == find_num){
      return i;
    }
  }
  return 0;
}

void try_piece(int x, int level)
{
  int i, j, k;

  try_counter++;
  x = board_index(0, x);
  for(i=0; i<12; i++){
    if(pieces[i].used == 1){continue;}
    for(j=0; j<pieces[i].formsize; j++){
      if(board[x + pieces[i].form[j].pos[1]] +
         board[x + pieces[i].form[j].pos[2]] +
         board[x + pieces[i].form[j].pos[3]] +
         board[x + pieces[i].form[j].pos[4]]){continue;}
      // ピースを置く
      for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k]] = i + 1;}
      pieces[i].used = 1;
      // すべてのピースを置ききったらTrueを返す(recursiveコールの終了)
      if(level == 11){
        counter++;
        print_board();
        // ピースを戻す
        for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k]] = 0;}
        pieces[i].used = 0;
        return;
      }
      // 次のピースを試す
      try_piece(x + 1, level + 1);
      // ピースを戻す
      for(k=0; k<5; k++){board[x + pieces[i].form[j].pos[k]] = 0;}
      pieces[i].used = 0;
    }
  }
}

int main(int argc, char **argv)
{
  init_board();
  try_piece(0, 0);
  printf("解合計: %d\n", counter);
  printf("操作数: %d\n", try_counter);
}