5. C言語版の高速化あれこれ |
ペントミノをプログラムで解くことに興味を持たれている方からメールを頂き、久しぶりに高速化に取り組んでみました。いくつかのアイデアは、2001年1月にdaichonさんが主催されたヘキソミノプロジェクトのときに試してみたものです。なお、過去の高速化の経緯はこちらにあります。
高速化は不要な探索枝を早い段階で、かつ少ない計算量で刈り込むかにかかっています。枝刈りができたとしても、その処理に時間がかかってしまったのでは、全体の処理時間は長くなります。
今回、改めて処理時間を検証してみたら有効だと思っていた、ピースを置いた後に残る連続した空きスペースが5の倍数でない置き方のチェックは効果がでていませんでした。チェックにより探索枝は大幅に削減できますが、枝刈りの処理に時間がかかり処理時間短縮には効果がでていません。下表の1版と3版の比較が5の倍数チェックの有無の差です。
高速化の方法について色々と試してみた方法と結果を以下にあげます。なお、この表の処理時間には、解をファイル出力するための処理時間は含まれていません。ファイル出力時間は6×10の場合で0.2秒弱でした。
アルゴリズムの都合で6*10、8*8以外の解は、2倍の解を計算しています。
データの上段は処理時間(秒)、下段はピースはめ込み探索回数(回)
版数 高速化の試み 6×10 5×12 4×15 3×20 8×8 備考 1 1. ピースは短辺に沿って置く
2. 次に置く場所の孤立(1,2個)チェック
3. 5の倍数の空きチェック
4. Xピースによる解の重複排除2.46 1.70 1.65 0.01 0.45 2001.2月版 11,396,840 8,126,528 8,595,294 64,868 1,971,568 2 上記の2,3(空きスペースチェック)なし 2.14 1.32 1.55 0.02 0.57 探索回数は3倍近いが
時間は少し短縮31,117,470 21,676,124 27,562,686 304,284 8,657,920 3 2. 次に置く場所の孤立(1,2個)チェックのみ 1.75 1.09 1.18 0.01 0.46 探索回数が大幅減、時間も大幅減 18,979,676 11,925,054 15,372,952 153,536 5,176,692 4 5. 置けるピースと方向を事前計算 1.37 0.85 0.87 0.01 0.34 探索回数が5の倍数空き
チェックとほぼ同じ11,071,787 6,576,052 7,713,381 54,474 2,608,258 5 6. ピース配置の事前計算にXピース考慮 1.36 0.84 0.81 0.01 0.34 探索回数が若干減、
処理時間は微減10,736,046 6,224,790 6,052,860 44,203 2,526,680 6 7. 置ける方向の事前計算時に5の倍数のスペースチェック 1.19 0.77 0.51 0.02 0.20 探索回数減、
処理時間も短縮8,676,620 4,905,670 3,040,876 7,691 1,052,822 7 8. 置ける方向の事前計算時に次に置く場所の座標を計算 1.15 0.75 0.50 0.03 0.19 探索回数は同一、
処理時間が若干削減8,676,620 4,905,670 3,040,876 7,691 1,052,822 8 9. 残りピース管理をリスト化 0.98 0.65 0.44 0.03 0.17 探索回数は同一、
処理時間が若干削減8,676,620 4,905,670 3,040,876 7,691 1,052,822 9 10. 次に置く場所の孤立(1,2個)チェックのパターン限定 0.91 0.56 0.39 0.02 0.18 探索回数は増加、
処理時間が若干削減9,303,097 5,281,379 3,312,575 8,010 1,537,498 10 11. 配置方向を途中で切り替える 0.84 0.62 0.43 0.03 0.09 探索回数が減少(6*10,8*8のみ)、
処理時間も若干削減8,753,219 5,316,242 3,312,575 8,010 415,366
- 測定環境
- プラットホーム
- PentiumIII 800MHz, Windows 2000, DOSプロンプト
- コンパイラ
- Borland C++ Compiler 5.5 (コンパイルオプションは-O2 -5)
※もう少し探索数を絞り込むアイデアがあるので(ちょっと面倒なので高速化に繋がるか不明)、そのうち(また1年後かな?)試してみようかと思っています。
Copyright (C) Nakamura 2002 |