RubyとC言語でもペントミノバズルを解いてみる
前回からの続き。
ペントミノパズルを解くPythonコードは、順調に高速化の道を歩んできた。
- 3時間以上 → 50分 → 20分 → 3分。
ところで、現在はnumpyにほとんど依存しないコードになっている。ならば、他のプログラミング言語でも同じアルゴリズムでペントミノパズルを解けるはず。ふと、使い慣れているRubyで書いてみたらどうなるのだろう?と思った。やってみた。
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
$ python --version Python 2.7.6 $ ruby --version ruby 1.9.3p194 (2012-04-20 revision 35410) [x86_64-darwin12.2.0]
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秒で完了した!
$ gcc -O2 pentomino.c $ time ./a.out 解合計: 2339 操作数: 10385817 real 0m1.256s user 0m1.237s sys 0m0.017s
- -O2オプションは最適化レベルのオプション。
- フリーソフトウェア徹底活用講座(1)(素晴らしい情報に感謝です!)
- 最適化レベルによって、以下の結果となった。
なし | 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); }