C++で大規模な配列追記のパフォーマンス
はじめに
@__boronium による
「じゃあC++はどうなの？」
という疑問にお答えするコーナー。元のPython版はhttp://d.hatena.ne.jp/ponkotuy/20111216/1324021461
でどうぞ。
はじめる前に補足
微妙に間違った参考のされ方してたので補足しておくと、こいつはどういう訳か「データの入力が圧倒的に多いのにその殆どは参照すらされずに捨てられる場合」に一番早いコンテナ、という極めて稀なパターンに特化した測定なので、そゆ場合にしかアテになりません。
Vector
#include <vector> int main() { const int size = 10000000; std::vector<int> v = {1,2,3}; for(int i=0; i<size; ++i) v.push_back(i); }
0.23秒、200MB。
しかしご存知の通りvector型は逐次でpush_backするのは頭悪いこととされているので、resizeで一気に確保すると…
#include <vector> int main() { const int size = 10000003; std::vector<int> v = {1,2,3}; v.resize(size); for(int i=3; i<size; ++i) v[i] = i; }
0.11秒、159MB。このメモリ使用量が減った理由はのちほど。
とはいうものの、本来の動作とはちょっと違ったものになってるので、元と同じ形にしてみる。
#include <vector> int main() { const int size = 10000003; std::vector<int> v = {1,2,3}; v.reserve(size); for(int i=3; i<size; ++i) v.push_back(i); }
0.14秒、159MB。push_backに若干のオーバヘッドがあるらしい。
なお、最初のコードでv.capacity()を吐かせて調べてみると、12582912と余計な領域が確保されているのが分かる。
vectorはランダムアクセスを許可する為に、連続したメモリ領域を確保する必要がある。従って不足した場合は別の場所に確保し直す処理が入る。
この為、push_backで毎度領域を再確保するにはコストが高すぎる。一方、一気に広い領域を確保するのは、小さなvectorにはメモリの無駄が多い。
この微妙なバランスの為、vectorはcapacityが不足する度に、現在の領域の2倍のサイズを確保し直す。従って、3×2^22という先程のcapacityが出てくる。
ちなみにresizeとreserveの違いは以下が詳しい。
Array
C++11で導入されたstd::arrayを使ってみると
#include <array> #include <memory> int main() { const int size = 10000003; typedef std::array<int, size> iarray; std::unique_ptr<iarray> a(new iarray); (*a)[0] = 1; (*a)[1] = 2; (*a)[2] = 3; for(int i=3; i<size; ++i) (*a)[i] = i; }
0.09秒、159MB。早い。とはいうものの値がそもそも小さ過ぎて誤差な感もある。
配列
Cにもあるoldな配列
#include <memory> int main() { const int size = 10000003; std::unique_ptr<int[]> a(new int[size]); a[0] = 1; a[1] = 2; a[2] = 3; for(int i=3; i<size; ++i) a[i] = i; }
0.08秒、159MB。誤差なのかちょっぴり早くなってるのかは理解に苦しむ所ではある。
list
#include <list> int main() { int size = 10000003; std::list<int> l = {1,2,3}; for(int i=3; i<size; ++i) l.push_back(i); }
1.64秒、1.25GB。push_backは定数時間な割にちょっと遅過ぎる気がするんだが…。
実はlistにresizeがある。という訳でこんなコードを書いてみる。
#include <list> int main() { int size = 10000003; std::list<int> l = {1,2,3}; l.resize(size); for(auto it=++++++l.begin(); it!=l.end(); ++it) *it = 1; }
1.82秒、1.25GB。寧ろパフォーマンス落ちてる。
定数で初期化する時以外はresizeしない方が良さげ…って書こうと思いこんなコードを書いてみる。
#include <list> int main() { int size = 10000003; std::list<int> l = {1,2,3}; l.resize(size, 1); }
1.63秒、1.25GB。最初と速度変わらん…。list.resizeとか忘れていい。
あとlistはコンストラクタでイテレータ渡せるからこんなことをしてみる。
#include <vector> #include <list> int main() { int size = 10000003; std::vector<int> v = {1,2,3}; v.reserve(size); for(int i=3; i<size; ++i) v.push_back(i); std::list<int> l(v.begin(), v.end()); }
1.74秒、1.4GB。時間的にvectorの初期化とlistの初期化を足したぐらいの時間が掛かってる模様。こちらも忘れていい。
deque
#include <deque> int main() { const int size = 10000003; std::deque<int> dq = {1,2,3}; for(int i=3; i<size; ++i) dq.push_back(i); }
0.15秒、167MB。最初のVectorよりちょっぴり早くて謎い。
push_frontに変えると0.16秒、167MB。誤差でしょう。
dequeにもresizeあるよ！という訳で調べてみる。
#include <deque> int main() { const int size = 10000003; std::deque<int> dq = {1,2,3}; dq.resize(size); for(auto it=++++++dq.begin(); it!=dq.begin(); ++it) *it = 1; }
0.14秒、167MB。まぁ誤差か。resize無かったことにしてもいい。
priority_queue
ソート済みコンテナですね。
#include <queue> int main() { const int size = 10000003; std::priority_queue<int> pq; pq.push(1); pq.push(2); pq.push(3); for(int i=3; i<size; ++i) pq.push(i); }
1.37秒、266MB。ちなみに内部ではvectorが標準で使われているので、次のように、vectorに後でソートを掛けたものが、
#include <vector> #include <algorithm> int main() { const int size = 10000003; std::vector<int> pq = {1,2,3}; pq.reserve(size); for(int i=3; i<size; ++i) pq.push_back(i); std::sort(pq.begin(), pq.end()); }
0.68秒、159MBと、こちらの方が早いのは有名な話。
なので、priority_queueを使いたい場合は、上記で生成したvector型をコンストラクタに渡す。
#include <vector> #include <queue> int main() { const int size = 10000003; std::vector<int> v = {1,2,3}; v.reserve(size); for(int i=3; i<size; ++i) v.push_back(i); std::priority_queue<int> pq(v.begin(), v.end()); }
0.38秒、316MB。vectorをそのままソートするよりも、priority_queueに未ソートを渡した方が早いという驚愕の結果に。
（一応初期化データを変えて、ワザとソートされてないvector渡してみたが、priority_queueの中身はちゃんとソートされていた）
set
そろそろ疲れてきた。
#include <set> int main() { int size = 10000003; std::set<int> s = {0,1,2}; for(int i=3; i<size; ++i) s.insert(i); }
27.27秒、1.88GB。setの追加はlog時間掛かるので遅い。従ってinsertに次のように挿入先のヒントを与えてやると、
#include <set> int main() { int size = 10000003; std::set<int> s = {0,1,2}; for(int i=3; i<size; ++i) s.insert(s.end(), i); }
2.84秒、1.88GBと、かなり早くなる。挿入場所を正しい場合に指定した場合に限り、定数時間が保証される。
ちなみに間違ったヒントを与えてやると…
#include <set> int main() { int size = 10000003; std::set<int> s = {0,1,2}; for(int i=3; i<size; ++i) s.insert(s.begin(), i); }
25.0秒、1.88GBと遅く…あれ、最初より早いんだがこれどういうことなん？とりあえず何でもいいから適当にヒント入れておけばいいんじゃね？w
定番のイテレータ渡しの初期化
#include <vector> #include <set> int main() { int size = 10000003; std::vector<int> v = {1,2,3}; v.reserve(size); for(int i=3; i<size; ++i) v.push_back(i); std::set<int> s(v.begin(), v.end()); }
2.93秒、2.03GB。やはりvector + 正しいヒントを与えたsetとなっている。
