Competitive Programming Advent Calendar 2017 16日目の記事です。
北大日立新概念マラソン、1回目も2回目も、Simulated Annealingの良い近傍を適用できた人が上位になったという結果でした。
僕はこの手の良い近傍を見つけるという問題があまり得意でなく、かわりにナイーブな方法を頑張って高速化して対抗しようとしてしまう悪い癖があり、いろいろな高速化をやりました。その内容について、多少一般化した形にしながら書いていきます。
なお別に高速化のプロではないので、CPUのパイプラインを埋める…とか先のキャッシュラインをプリフェッチ…とかの話はしません（できません）。アルゴリズムのレイヤ中心です。
とにかく動的なメモリ確保は取り除きます。
たとえば、小さな規模のBFSを何回もやるというシチュエーションはよく現れます（今回では、第2回で1ノードを取り除いたとき残った同じ番号のノードが連結かどうかを判定するのに使いました）。
void bfs(int pos) { vector<int> que = {pos} for (int i = 0; i < que.size(); i++) { // queにpush_backしたり } }
毎回vectorを作るのが遅いので、十分なサイズのバッファをはじめに確保しておき、そこを使い回します。
int bfs_buf[2048]; void bfs(int pos) { int que_size = 1; bfs_buf[0] = pos; for (int i = 0; i < que_size; i++) { // bfs_buf[que_size++] = next_pos; とかでキューに追加 } }
「十分なサイズ」がとても大きくて全テストケースでその量のメモリを確保するのが嫌な場合は、グローバル（または関数スコープのstatic）なvectorにしておいて、毎回clearして使うのも可。
除算・剰余算は遅いのでできる限り取り除きます。
その１：焼きなましの受理判定のときに発生する温度での除算は逆数の乗算にする
bool accept(int score_diff) { if (score_diff >= 0) return true; return rnd.next_double() <= exp(score_diff / temperature); }
↓
bool accept(int score_diff) { if (score_diff >= 0) return true; return rnd.next_double() <= exp(score_diff * temperature_inv); }
その２：N点の中から動かす位置を決めるときは、乱数に対してNでmod取るののかわりに、順番に選んでいくようにする
void simulated_annealing() { for (int turn = 0; ;turn++) { int selected_pos = rnd.next_int() % N; // selected_pos を動かしたりする } }
↓
void simulated_annealing() { int selected_pos = 0; for (int turn = 0; ;turn++) { selected_pos++; if (selected_pos == N) selected_pos = 0; // selected_pos を動かしたりする } }
または、候補になる位置をvectorに入れておき、要素を重複して入れることでそのvectorのサイズを2のべき乗にする。
選択される位置に偏りはできてしまうし、メモリアクセスの局所性は悪くなるものの、これで速くなって結果が良くなることもある
void simulated_annealing() { for (int turn = 0; ;turn++) { int selected_pos = cand_pos_list[rnd.next_int() & (cand_pos_list.size() - 1)]; // selected_pos を動かしたりする } }
第1回では、ランダムな2点を交換するという近傍を採用しました。
このとき、スコア変化を調べるため「交換後に得られるスコア - 交換前のスコア」を計算する必要があります。
交換前のスコアは何度も同じ値にアクセスするため、事前に計算して保持しておいた方がよいです。
int calc_score_diff(int pos1, int new_val) { int ret = 0; for (int i = 0; i < 8; ++i) { ret -= graph[node[pos1]][node[pos1 + DIFF_POS[i]]]; ret += graph[new_val][node[pos1 + DIFF_POS[i]]]; } return ret; }
↓
int calc_score_diff(int pos1, int new_val) { int ret = -pos_score[pos1]; for (int i = 0; i < 8; ++i) { ret += graph[new_val][node[pos1 + DIFF_POS[i]]]; } return ret; }
1bitの情報はできるだけbitset的データ構造で持って、64bit分（またはSIMD使って128bit, 256bit分）まとめて処理できるようにします。
たとえば第2回では、元のグラフGでノード間にエッジがあるかどうかと、現在のキンググラフに埋め込んだ盤面上でノード間にエッジがあるかどうかをどちらも（オレオレ）bitsetで保持して、スコア変化を V/64 回のループで計算できるようにしました。
https://beta.atcoder.jp/contests/hokudai-hitachi2017-2/submissions/1867989 の823行目あたり
メモリアクセスは遅いです。
プログラミングにあまり慣れていなかった頃、「exp関数遅いし、細かく離散化してテーブルに入れておけばアクセス1回で値を引けて速くなるんじゃないの」と思ってやってみて、逆に遅くなったという経験をしたことがある人はそこそこいるんじゃないでしょうか（僕はあります）。
できるだけ使っているメモリがキャッシュに乗るよう、でかい配列はデータ型をコンパクトにします。
第1回では、元グラフでの辺の重みを保持する500*500の配列が大きかったので、はじめint32_tで持っていたのをuint8_tにしました。これだけで1割くらい速くなった記憶があります。
ただし何でも詰め込めば良いというわけでもなく、値が最大で15なのをいいことに1要素4bitで詰め込もうとしたら、今度は大幅に遅くなりました。さすがに自前でマスクしてシフトして、という処理があちこちに入るとそのオーバーヘッドの方が重かったようです。
状況によっては、頑張って詰めた方が良い場合もあるとは思います。
普通はフィールドのデータは field[x][y] で持つと思いますが、座標を1次元に潰して field[(x << 6) | y] で扱うと速くなりました。
座標をxy別々に扱わずに済んで、いろいろ簡略化されるからだと思います。
おなじみの
int DX[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; int DY[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
は
int DN[8] = {-65, -64, -63, -1, 1, 63, 64, 65};
になります。
盤面の端をはみ出たかの条件をif文で書く回数を減らせるよう、盤面を64*64分確保して、実際のデータはxyそれぞれ1ずらした位置に置き、外周1周分を番兵として使えるようにしました。
exp関数は遅いので、スコア差分が圧倒的に悪くてほぼ受理されなそうなら、exp関数を呼ばずに棄却します。
bool accept(int score_diff) { if (score_diff >= 0) return true; double v = score_diff * temperature_inv; if (v < -6) return false; // 枝刈り return rnd.next_double() <= exp(v); }
回数が固定されているループで、呼ばれる回数が多い箇所はループ展開します。
for (int i = 0; i < 8; i++) { int next_pos = pos + DN[i]; // next_pos を使って何か }
↓
int next_pos = pos + DN[0]; // next_pos を使って何か next_pos = pos + DN[1]; // next_pos を使って何か （中略） next_pos = pos + DN[7]; // next_pos を使って何か }
また、必ず1回以上実行されることがわかっているループはwhileではなくdo-whileにする、とかもこれに含めて良いかと。
やり過ぎると命令メモリが増えることによりアクセス局所性が悪くなって遅くなっちゃいますが。
上でも書きましたが、第2回で同じ番号のノードの連結性の確認のためにBFSを使いました。
シンプルに書くと、次のようになります。
for (int i = 0; i < que.size(); i++) { int pos = que[i]; for (int j = 0; j < 8; j++) { int next_pos = pos + DN[j]; if (node[next_pos] == n && !visited[next_pos]) { que.push_back(next_pos); visited[next_pos] = true; } } }
まず、各点で隣接するそれぞれのノードが自分と同じ番号かどうかを、1bitずつ計8bitの値で持っておきます。
すると、BFS内での同じ番号のノードかどうかのチェックが削除できて、隣接位置すべてを見るループも削減されて、次のようになります。
for (int i = 0; i < que.size(); i++) { int pos = que[i]; int bits = surround[pos]; while (bits) { int dir = __builtin_ctz(bits); int next_pos = pos + DN[dir]; if (!visited[next_pos]) { que.push_back(next_pos); visited[next_pos] = true; } bits &= bits - 1; // 最下位bitをクリア } }
さらに、BFSでキューにpushしたときに、自分に戻ってくる側の移動は見なくて良いはずなので、それを教えてあげると、さらに少し速くなります。
for (int i = 0; i < que.size(); i++) { int pos = que[i]; // queに入っている値は、上位16bitが探索する方向の候補、下位16bitが位置を表す int bits = pos >> 16; pos &= 0xFF; while (bits) { int dir = __builtin_ctz(bits); int next_pos = pos + DN[dir]; if (!visited[next_pos]) { int next_bits = surround[next_pos] - (1 << (7 - dir)); // 自分にすぐ戻る移動を抑制 que.push_back((next_bits << 16) | next_pos); visited[next_pos] = true; } bits &= bits - 1; // 最下位bitをクリア } }
ナイーブにやると次のようになります。
int v1 = rnd.next_int() % N; int v2 = rnd.next_int() % N; while (v2 == v1) { v2 = rnd.next_int() % N; }
よく知られているテクとして、次のようにすれば乱数呼び出しが確実に2回で済みます。
（ただし分岐予測は効きにくくなるので速くなるかどうかは場合によるかも…）
int v1 = rnd.next_int() % N; int v2 = rnd.next_int() % (N - 1); if (v2 >= v1) v2++;
