こんにちは、kaageです。
今回は、C++で競技プログラミングの問題を解くとき、定数倍が重くて通らないコードを高速化し、ACを取るためにできるテクニックを紹介します。
思いつくことをひたすら書くので、リファレンス的に使ってください。
ゴミ定数倍高速化 by @thistleprogram,競プロで使える高速化テクニック by Joeを参考にしました。Thistleさん、Joeさん、ありがとうございます。
初級編
いつでも使えるものからいきます。
QCFium法のpragma
いわゆる「QCFium法のpragma」です。QCFium法の由来についてはこちらをどうぞ。
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
この3行を追加するだけで、高速なバイナリが生成されます。
ただし、TopCoderなどのクラスを提出する形式の場合には当然使えません。
上の行から説明していきます。
1行目では、コンパイラの自動ベクトル化をサポートします。所謂SIMDです。これでループなどは基本的にベクトル化され、高速になります。
ただし、AtCoderなど一部のオンラインジャッジではavx2をサポートしていないので、CPUが実行できないバイナリが生成されることがあります。
この場合、avxに置き換えることで同じような効果が得られます。
2行目では、最適化オプションをO3に設定し、高い最適化効果を得ています。
もっと最適化のレベルが高いOfastもありますが、これは厳密に仕様を守らないおそれがあります。
使うことに問題はないですが、危険性があるということは理解しておきましょう。また、O3と結果があまり変わらなかったり、むしろ悪化することも多いです。
3行目では、ループを部分的に展開して、内部でまとめて行う（たとえば、100回のループを20回にして、中に5回分のコードを貼る）ことにより、ループ変数の処理などにかかる時間を短縮できます。
しかし、これによってレジスタで変数を操作する回数が増える恐れもあります。
また、当然展開したことによりバイナリのサイズは増大します。これが問題となる場合もありますが、オンラインジャッジに提出する分には何も問題はありません。
これだけで実行時間が2割削れる場合もあります。
浮動小数点の計算が絡むときにも、次のpragmaでSIMDを有効化できます。
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
一つ注意したいのは、どのpragmaも貼っておけば必ず速くなるとは限らないことです。
特にSIMDやunroll-loopsなどは、余分な処理が入って遅くなることもあります。
入出力の高速化
std::cinやstd::coutは遅いですが、次のコードを最初に実行することでだいぶ高速化できます。
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
これでscanf/printfとほぼ同じ速度の実行が期待できます。
しかし、scanfやprintfを使うほうが有効な場合ももちろんあります。
また、std::endlは低速なので、改行文字"\n"で置き換えるのもかなり有効です。
インタラクティブ問題などで出力のflushが必要な場合は、改行文字では行えないので別に行いましょう。
これよりも高速化したい場合は、最終手段、「自分で入出力ライブラリを書く」という方法があります。
具体的には、UNIXの非常に高速な環境依存関数、getchar_unlocked/getc_unlockedやputchar_unlocked/putc_unlockedを使うという方法があります。
これで1文字ずつ入力を受け取り、整数に直すなどの処理をすれば、比べ物にならないレベルで高速になります。
vector関連
無駄な要素の再構築やメモリの再確保をなくすのが基本です。
まずは、std::vector::push_backを、std::vector::emplace_backに置き換えることから始めましょう。
push_backでは、引数になるまでに要素が構築され、それがコピーされてvector内に要素が入りますが、emplace_backでは、コンストラクタ引数を取るので、余分な構築が減ります。
リテラルではあまり関係ないですが、pair型やクラスの構築ならこれで高速になります。
また、vectorのメモリ確保は2冪状に行われ、途中で足りなくなるとメモリの再確保を行います。このとき大きなコストがかかるため、先に確保しておくのが有効です。
vectorのサイズ自体は変えずに確保する場合はreserve関数、サイズも変える場合はresize関数が使えます。
コンパイラの変更
clangはシンプルな処理に強いですが、GCCのほうが基本的には優秀、というイメージです。
また、clangは入出力が怖いほど遅いので、そもそも定数倍高速化が求められるような場面では高速な入出力が必須です。
なるべくintを使う
当たり前ですが、long longでなくても済む場所ではintを使えば、SIMDも効きやすくなり、メモリ使用量も減り、たくさんの値がキャッシュに載るのでメモリアクセスも速くなります。これはかなり有効なので、某未定義動作(#define int long long)を多用している人などは気を付けましょう。
定数にはconstexprをつける
modを取る時のmodなどの定数や、mod付き整数クラスのコンストラクタなどにはconstexprをつけておくと、コンパイル時に決定する部分を前計算してバイナリに埋め込んでくれます。
ただ、DPなどをするときにconstexprを乱用すると、コンパイル時にDPが行われるせいでバイナリサイズが巨大になり、実行できなくなったりすることがあります。気を付けましょう。
中級編
二分探索の誤差テクニック
これは前に挙げた @thistleprogram の記事を参考にしてください。
小数で出力する問題のとき、答えの値が大きくなれば、許される相対誤差の値も大きくなることを利用したテクニックです。
徹底的前計算
サイズ $N$ の数列 $X$ を座標圧縮することを考えます。基本的には、次のようにすることが多いでしょう。
std::vector<int> Y(N);
for(int i = 0; i < N; i++)Y[i] = X[i];
std::sort(Y.begin(), Y.end());
Y.erase(std::unique(Y.begin(), Y.end()), Y.end());
// このあと二分探索を用いて X[i] の値から圧縮後の値を求める
ここで、X[i]の値は高々 $N$ 個なので、$O(N\log N)$ で座標圧縮後の値を前計算できます。つまり、
std::vector<int> Z(N);
for(int i = 0; i < N; i++){
Z[i] = std::upper_bound(Z.begin(), Z.end(), X[i]) - Z.begin();
}
こうすることで、毎回二分探索をする必要がなくなり、アクセスが多ければ非常に高速になります。
このように、計算に時間がかかる、量が少ない値は前計算しておくのは基本ですが、忘れがちなことも多いです。
たとえば、ローリングハッシュでの部分文字列のハッシュの計算で使われるmodつきの逆元なども前計算しておくと、とても高速です。
割り算を減らす
有名だと思いますが、割り算の実行コストは高く、足し算や引き算の40～60倍かかります。
ここで、割り算のプログラム中での回数を減らすことにより、高速化が期待できます。
セグ木の非再帰化
セグ木を非再帰にすることで高速化が期待できます。
GCCのビルトイン関数を使って、$O(\log\log N)$ かけて枝刈りをし、さらに高速化することもできますが、他の環境で使えないのは困るので自分は使っていません。
セグ木の区間全体取得
当然ですが、セグ木で区間全体の値を取得したいときは、区間全体を包含するノードを参照するだけでよいです。
上からの遅延伝播も起こらないのでできる操作です。
これで $O(\log N)$ かかるところが $O(1)$ になります。
fillの代わりにmemset
fill関数の代わりにmemset関数が使える状況なら、この方が早いです。
memset関数はunsigned charの範囲で値を取り、メモリを埋めるので、好きな値でメモリを埋めるには適していませんが、全ビットが立っている $-1$ や、全ビットが立っていない $0$ のような値には使えます。
また、競技プログラミングにはほとんど関係ありませんが、memset関数は最適化により削除され得るので、パスワードを保存した領域の洗浄などには向いていません。
そのBITはいりますか、その遅延セグ木はいりますか
多分kaageだけだと思いますが、累積和で済むところになぜかBITを使い、そのBITを参照しながら演算を行うセグ木（つまり $\log$ ふたつ）を書いて、定数倍で落ちたことがあります。
区間加算セグ木を書こうと思ったら、BITで済まないか一度立ち止まって考えましょう。BITを書こうと思ったら、累積和で済まないか一度立ち止まって考えましょう。
上級編
メモリアクセスを考える
メモリにアクセスする順序はなるべく連続させたほうがよいです。
最も分かりやすい例としては、行列の乗算があります。
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
for(int k = 0; k < N; k++){
C[i][j] += A[i][k] * B[k][j];
}
}
}
よりも、
for(int i = 0; i < N; i++){
for(int k = 0; k < N; k++){
for(int j = 0; j < N; j++){
C[i][j] += A[i][k] * B[k][j];
}
}
}
のほうが高速です。
$A$,$B$ へのアクセスがメモリの並ぶ順になり、データがキャッシュに載っている確率が高くなります。
おわりに
他にも思いついたものがあったら加筆します。
こんな記事を書いておいてなんですが、メモリアクセスまで考え始めるときりがないし、初級編や、中級編のうち効果が高いものを試して通らなかったらその解法は諦めたほうが良いと思います。