概要
前回の記事の続きです。
あれから様々な工夫をこらすことによって探索を高速化しました。
こつこつ作戦です！
枝刈りで相当速くなったはずなのですが、それでも解けない問題は多いです。そこで、無駄だと思われる計算を徹底的に省くことにしました。
まず、鉢合わせ処理がありえる場合とない場合とで、枝刈りする際の判定が「掃除人の位置から拭きたい位置のマスまでの最短距離＞掃除人が歩ける残り歩数＋2歩」と「掃除人の位置から拭きたい位置のマスまでの最短距離＞掃除人が歩ける残り歩数」に分かれていましたが、**冷静に考えると毎回+2するのは無駄ですよね。**というわけで、最短距離を格納するバッファを2種類に増やし、計算を簡略化しました。
また、周囲にゴミ箱やリサイクル箱があるかどうかも今までは毎回if文を並べていましたが、ゴミ箱やリサイクル箱の位置は盤面読み込み時に決定しますので、そちらも事前に計算することにしました。
他にもビット演算を利用して判定を高速化するなどした結果、1割ほど計算時間が短くなりました。
次は並列化です！
上記までで、思いつく限りの高速化策はネタ切れとなってしまいました。となると、後は演算の並列化ぐらいしかありません。
しかし再帰探索は並列化の苦手分野であり、困難な過程になると予想されました。開発環境(Visual Studio 2015)だとOpenMP2.0までしか使えないのでtask構文が使えず、したがって別のスレッド生成方法を探す他なかったからです。実はこうした探索並列化の経験はあるのですが、その際はBFSも併用する複雑なことをしていたのでもう少し楽したいということもありました。
そこで、目をつけたのは**std::threadおよびstd::future**です。標準的な構文でサクッと並列化できるのですから使わない手はありません。ただ、もちろんスレッドを生成しまくると効率が悪すぎますので、スレッド数を抑えるために次のようなコードを組みました。
/* もちろん概略的なものです */
size_t threads = 1; //現在のスレッド数
size_t max_threads = 8; //最大スレッド数
std::mutex mtx;
void Move(){
if(threads < max_threads){
// スレッド数を増やす処理
動かせる手を列挙
vector<std::future<bool>> result;
std::deque<bool> result_get;
mtx.lock(); g_threads += それぞれの手の数 - 1; mtx.unlock();
for(size_t di = 0; di < それぞれの手の数; ++di){
result[di] = std::async(std::launch::async, [(略)] {
手を動かす
bool flg = Move();
手を戻す
return flg;
});
}
for(size_t di = 0; di < それぞれの手の数; ++di){
result_get[di] = result[di].get();
}
mtx.lock(); g_threads -= それぞれの手の数 - 1; mtx.unlock();
for(size_t di = 0; di < それぞれの手の数; ++di){
if(result_get[di]){
結果を書き戻す
return true;
}
}
return false;
}else{
// 1スレッドで探索する処理
手を動かす
bool flg = Move();
手を戻す
return flg;
}
その他の処理
}
長々と書いてますが、要するに「移動する方向に応じてスレッドを作成する」「最大スレッド数はthreadsで管理する」ということですね。これらの工夫により、CPUを使いきって探索してくれるようになりました。
計算、がんばります！
これだけ工夫したのですから、当然速くなってくれないと困ります。そこで、「No.46 平等に労働する部屋」について、演算時間を比べてみましょう。Core i7-4790K(定格)・64bitWindows10で64bitバイナリを動かしました(どれもPGO適応済み。リリースしているものと同じバイナリ)
| ソフト | 演算時間[ms] | 備考 |
|---|---|---|
| Ver.1.1.1 | 27756 | 前回の記事の最新版 |
| Ver.1.2.0 | 25244 | こつこつ作戦です！ |
| Ver.1.3.0(1スレッド) | 26417 | 次は並列化です！ |
| Ver.1.3.0(2スレッド) | 14949 | - |
| Ver.1.3.0(4スレッド) | 11044 | - |
| Ver.1.3.0(8スレッド) | 6865 | - |
これから分かるように、並列化の威力は絶大であると窺えます。ただ、並列化も完璧ではなく、小さな問題などでむしろ遅くなったケースもありました。ただ、Ver.1.3.0では動作スレッド数を自由に調整できますので、自環境に合わせて最適化できます。
なお、これらの工夫で追加で解けた問題はNo.45ぐらいで、後は並列化して数時間放置しても解けないと完全に沼っています……。なぜかA～Pの追加問題があったのでそちらも解いたのですが、No.N・No.O・No.Pの3つ以外は全て短時間で解けました。