C++ 高速化テクニック
C++ で競プロをするにあたって、プログラムの実行時間をより高速にするために一般的に使用されているテクニックをまとめてみました。
入出力の高速化
C++ の標準入出力 cin, cout は元から十二分に高速です。
それでも一部の非情なコンテストサイト(主に Codeforces) では標準入出力がネックで TLE を喰らうことが往々にしてあります。他の言語とかどうすんだよ。 C の標準入出力を使う
code:cpp
int main(){
int n;
scanf("%d", &n);
n += 468;
printf("%d", n);
}
C の標準入出力は、型が合わないと暴走するので業プロでは諸悪の根源とされていますが、競プロでは入力の型が合ってなかったら Writer / Tester の責任になるので大丈夫です。何もしてないcin / coutより、scanf / printfの方がちょっと速いっぽいです。ただタイプ量が凄いことになるのでめんどいです。
いつものイディオム
code:cpp
using namespace std;
int main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
}
cin.tie(nullptr)は、cinとcoutの結びつきを解除する効果があります。これを行っていない状態では、cinからの入力を受け取る度にcoutに flush がかかります。
業プロだと、これをすると入力を促すメッセージを表示してもfflush(stdout);しないと表示されないなどの弊害が出ますが、競プロではそんなものは必要なく、入出力を同期する必要はないので外してあげましょう。
2/20 追記
インタラクティブ問題では基本的にこちらからのクエリ出力のたびに flush 操作が必要です！
インタラクティブ問題は入出力の速度を含んでも終われるような軽量なアルゴリズムで解けることが多いので(持論)、諦めて頭を使って考えましょう……。
ios_base::sync_with_stdio(false);は、scanfやprintfと、cincoutの同期を解除する処理です。どうせcinとcoutしか使わないなら解除してあげたほうが良いです。バッファリングとかの面があるので。
endl を使うのをやめる
cout << endl;とすると、実は改行された後に出力の flush が行われます。
標準入出力との同期が必要な業プロではendlを使うことが推奨されている雰囲気がありますが、競プロではただ単にTLEする原因になるので
cout << "\n"
にでも置き換えてあげましょう。
改行するのをやめる
もうここまで来ると標準入出力での高速化は苦肉の策レベルになると思います。
改行を半角スペースに置き換えてもほとんどのジャッジではACになります。なので、改行をせず半角スペースを出力するようにすると極僅かに速くなることがあります。
その他の高速化
標準入出力とは別の面で高速化を図れる手法も結構あります。
QCFium法
code:cpp
#pragma GCC optimize("unroll-loops") これを付けるだけで高速になる、と有名な$ 3行です。
vector::emplace_back, vector::reserve
vector::push_backとvector::emplace_backという$ 2つのメソッドが存在します。
グラフ問題で隣接リストを作る場合など、push_backをemplace_backに変更すると高速になる場合があります。
code:cpp
// sample of getting input of dijkstra problem
vector<vector<pair<int, ll>> g(0);
for(int i = 0, i < m; i++){
int l, r; cin >> l >> r;
ll w; cin >> w;
gl - 1.emplace_back({r - 1, w}); gr - 1.emplace_back({l - 1, w}); }
またvectorに要素を追加する際の拡張についてですが、vectorオブジェクトはそれぞれcapacityという値を持っていて、
当該vectorへの要素追加時に、追加後のsizeがcapacity以下ならメモリの再確保を行わないことが保証されている
という性質があります。これ即ち、追加後にsizeがcapacityを超えるような大きさになる追加処理が行われるとメモリの再確保が行われるのですが、このとき
capacityが$ 2倍になるように再確保をする
という性質があります。これはかなりのコストを喰います。そこでvector::reserveを行うことで、メモリ確保を先に行っておくことが出来て、このコストが低減されます。
code:cpp
// estimated that the size of a will become at most 100000
a.reserve(100000);
インクリメント、デクリメント演算子の場所
a++と++aには
a++はインクリメント前の値をコピーしておき、値をインクリメントした後、コピーしておいたインクリメント前の値を返す
++aは値をインクリメントしてしまい、それを返す
という違いがあります。
前者の方がコピー処理が無い分速いです。
バージョンによっては吐き出されるアセンブリコードに違いはない、という実例がありますが、少なくとも今の AtCoder GCC C++ では差が出てしまいます。++aを使いましょう。
デクリメントも同様です。
C++ の map は異常に遅い
文字通りです。前に座標圧縮で書いた気もしますが、C++はmapやunordered_mapを使うだけの問題などを解かせるとRustやGoなどに大敗を喫します。 めんどくさいからといってmap<char, int>をせずにvector<int> c(26, 0);としましょう。
mod をとったり割り算をする回数を減らす
実は加減算や乗算と比べて滅茶苦茶遅いらしいです。
ループの順番を変えてキャッシュヒット率を上げる
胸に手を当てて、本当に正攻法が思いつかないか考える
ぶっちゃけAtCoderでは異常な高速化をしても一切論外な問題が多いです。