競プロで使える謎高速化テクニックを集めた記事ほしいな
— Joe@社会 (@xuzijian629) March 31, 2019
ということで自分で書きます。ここでいう高速化とは真に計算量を落とすようなかっこいいものではなく、定数倍高速化のことを指します。
まあこういうのは無限にあると思うんですが、自分が過去に使用したものをいくつか紹介します。 良さそうなのがあれば追記していきたいのでコメントなりで教えてください。
言語はC++です。普段から高速化意識してコード書いてる人には当たり前のことしか書いていないかもしれません。
いつでもできるような高速化
コンパイルオプション
コンパイルオプションをこちらが指定できる環境ならばだいぶ強いです。具体的にはAtCoderやCodeforcesが可能で、TopCoderなどクラスで提出するような環境ではダメな気がします。ソースはありません。
プログラムの最初に
#pragma GCC optimize("Ofast")
と書くだけです。たいていのジャッジサーバは標準でO2でコンパイルすると思うので体感わずかに速くなります。50msぐらい速くしたい、みたいな状況で使えそうです。
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
を書くとかなり速くなります(知らんけど100ms以上の改善はありそう?)
入出力
cinが遅いとかendlが遅いという話です。自分の場合
ios::sync_with_stdio(false); cin.tie(nullptr);
で困ったことがないのでたいていこれを使っています。1e5行入出力する問題だとこうするだけで100msぐらい速くなる印象です。endlはこれよりずっと遅いので複数行出力するときは'\n'
使いましょう。
reserve
vectorやunordered_mapなどで使います。これは、要素数が増えるに従ってメモリ確保が動的に内部で行われるので、事前に確保してあげると速くなります。
emplace, emplace_back
primitive型ではない型をvectorやstack, queueに格納するとき、普通にpush, push_backすると要素のコピーが行われてから格納されるので、emplace, emplace_backをしたほうが速いです。
コンパイラを変える
ええええええええええええええええええええええええええええええええええええええええええええええええコンパイラをGCCからCLANGに変えるだけでスコアが346909466から354547346(20位)に上がったけど
— Joe@社会 (@xuzijian629) March 24, 2019
高速化前のチェックリスト
大抵の問題の場合、そもそもTLE解法はwriterによって落とされる前提なので本当にその解法が高速化によって通る見込みがあるのかしっかり考察すべきです。とくに本気で高速化しようとすると30分や1時間経ってしまうこともあり、普通に考え直したほうが早かったなんてことも多いと思います。
しかし、(ほぼ)想定解だったにもかかわらずACを逃してしまうということもあるかと思います。そういうときのチェックリスト的な感じでまとめていきます。
そのmap, unordered_mapは配列ではダメですか
配列にするとさすがにだいぶ高速です。
そのvector毎回宣言しないとダメですか
たとえば要素数が高々2, 3のvectorを1000000回宣言するのとすでに宣言したvectorを使い回したり、primitive型で宣言するのでは時間が二倍以上違うと思います(測ってないけどもっと違う気がする)
modをとりすぎていませんか?
a + bのmod mでの足し算なら
a += b;
if (a >= m) a -= m;
と書くほうが
a = (a + b) % m;
より高速です。
限界編
正直↑に書いたことを全部守れているなら、制限時間が2秒だったとして、0.1秒縮めるのも相当困難だと思います。大抵の高速化は プログラムの命令数を少しでも少なくしたり、メモリアクセスや投機的実行をしやすくしたりすることを考えるよりも、コアな部分の処理を軽量化するほうがずっと楽だしずっと速くなります。
ただ、それをやってもあと20ms縮めたい、とかが極稀にあるかと思います。
random系は自作のxorshiftを使う
たとえばunordered_mapやrandom_deviceを使ったりするときです。
struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; int main() { unordered_set<long long, custom_hash> ss; }
みたいな感じです。
ループを分割する
たとえば、かなり人工的ですが
for (int i = 0; i < (k & 1 ? 100 : 200); k & 1 ? i++ : i += 2);
のようなループがあった場合、毎回ループ内で第2項や第3項をチェックされると遅いので、kが奇数の場合と偶数の場合にわけてループを書き直します。
メモリアクセスを考える
多次元配列の場合、これはわりと効果のある改善になると思います。
ループのブロック化
これはだいぶ限界な話ですが、メモリアクセスの高速化を考えると
for (int i = 0; i < 2 * n; i++) for (int j = 0; j < 2 * m; j++)
のループを一度回すよりも
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {} for (int i = n; i < 2 * n; i++) for (int j = 0; j < m; j++) {} for (int i = 0; i < n; i++) for (int j = m; j < 2 * m; j++) {} for (int i = 0; i < 2 * n; i++) for (int j = m; j < 2 * m; j++) {}
の4回を回すほうが(n, m)の値によっては高速です。
このスライドがわかりやすいです。
最後に
異常高速化をしていないで正攻法でさっさと通しましょう