C++高速化のよくある手法まとめ【備忘録】
C++
C++言語はオブジェクト指向型言語と呼ばれ，今人気のPythonやRubyのような言語と比べ，コードはずっと複雑です．しかし高速なプログラムを書くことに長けています．
それでも何全行もの長いコードを書いたり，同じ処理をたくさん繰り返すような処理を書くと，やはり処理に時間がかかってきます．
でも，その遅い原因はコードの書き方にあることが多いです．
この記事ではよくやりがちな実行処理の遅いコードと，修正例を紹介していきます．
vector配列
C++では様々な配列を扱えます．その配列にも適役があります．
基本的にvectorを使っている人が多いと思うので，vectorについて書いていきます．
優秀な動的配列vectorは，「C++でとりあえず配列を作るならこれ使っておけば安心」という立ち位置．
メモリ確保は出来るだけ最初にする
vectorは，push_back()で基本的に要素を追加していきますが，もしpush_back()時にメモリが足りなければ都度確保する，という性質があります．なのでもし最大要素数が分かっているのであれば，最初にreserve()でメモリを確保してしまいましょう．
これだけで意外と速くなります（経験談）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #include <iostream> #include <vector> using namespace std; int main(){ // 要素数100000の配列を作る vector<int> v; for( int i = 0; i < 100000; ++i ){ v.push_back( i ) ; } return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include <iostream> #include <vector> using namespace std; int main(){ // 要素数100000の配列を作る vector<int> v; //初めにメモリ確保！ v.reserve( 100000 ); for( int i = 0; i < 100000; ++i ){ v.push_back( i ) ; } return 0; } |
また，上の例では違う要素を配列に格納したいときを例にしたが，もし同じものを配列に格納したければ以下のようなコードでOKである．
1 2 3 4 5 | // 要素数100000,初期値0の配列を作る vector<int> v1( 100000 ); // 要素数100000, 初期値5の配列を作る vector<int> v1( 100000 , 5 ); |
追記(2019.02.03)：
速度実験を行ってみました！↓
補足
メモリを最初に確保したとして，その後要素を削除したいときにclear()を使うと要素は削除されるが確保したメモリは解法されないので注意が必要．
clear()の後にshrink_to_fit()を使いようにしましょう．
またreserve()はメモリを確保しただけなので要素数は確保時点では0です．
inline展開
関数のinline展開は，簡単に言えば「コンパイル時に，関数を呼び出している部分に内容を展開してしまう」ことを指す．
処理の中で関数を呼び出すだけでも，実はそれなりに時間がかかる．それを実際にあたかもべた書きしているかのように展開することをinline展開という．
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | inline int sum( int x , int y ){ return x + y; } int main(){ int a = sum( 3 , 5 ); int b = sum( 2 , 3 ); cout << a * b << endl; return 0; } |
と書けば，
1 2 3 4 5 6 7 8 9 | int main(){ int a = 3 + 5; int b = 2 + 3; cout << a * b << endl; return 0; } |
と同義である，ということ．
補足
ただし，複雑な関数を至るところでinline展開すれば，コンパイルは遅くなるし，実際の実行ファイルは大きくなるので注意が必要．
ループ処理
for文における低速化要因
例えば以下のようなコードがあったとする．
1 2 3 4 5 6 7 8 9 | int main(){ // 1000のサイズのvector配列を0で初期化 vector<int> v( 1000 ); for( int i = 0; i < v.size(); i++ ){ v[i] = i; } } |
そんなにおかしくないコードに見えるかもしれないが，2か所高速化できる点がある．
一つ目は「ループ条件式のv.size()」部分である．
ループ条件式は実は，ループするたびに都度参照される．なのでそのときに毎回v.size()でサイズを取得してたら，関数アクセス分の時間が余計にかかっていしまう．
二つ目は「インクリメント処理」
インクリメントは i++ と ++i があるが，実は前者の方が少しだけ遅いようだ．
（前者は一度もとの値を保持するため）
ということで上記二つの修正箇所を直すと以下のようになる．
1 2 3 4 5 6 7 8 9 10 11 | int main(){ // 1000のサイズのvector配列を0で初期化 vector<int> v( 1000 ); // 最初に変数としてサイズを保存 for( int i = 0, size = v.size(); i < size; ++i ){ v[i] = i; } } |
おわりに
以上，よくある高速化の例を上げました．これらは実際僕の経験済みの話で，これだけでかなり研究が捗るようになりました．
僕の場合はvectorのreserve()と関数のinline展開をしっかり導入したおかげでバカにならないほど高速になりました．
他にも高速化手法はあるので，いろいろ調べてみてください．
[bfcc id="fastercpp"]
