C++の配列とvectorの速度比較

vectorって遅くない? <a name='more'></a> 配列に比べて高機能なので仕方ないが, 遅いのが気になったので確認. 検証方法は[[1](#jagabeeinitialize)] [[2](#hirlab)]を参考にした. 比較したのは以下の5つの`for`文. 1. vec auto型 ```c++ (auto i : vec) ``` 2. vec iter型 ```c++ for (auto i=vec.begin();i!=vec.end();++i) ``` 3. vec array型 ```c++ for (int i=0;i<MAX_SIZE;++i) //vectorを配列として使う ``` 4. list型 ```c++ for (auto i : int_list) //list ``` 5. array型 ```c++ for (int i=0;i<MAX_SIZE;++i) //配列 ``` 1.はもっとも簡単なvectorの`for`ループ. [[1](#jagabeeinitialize)]によるとvectorのループ文の中で最も速いらしい. 2.はイテレータで指すループ. イテレータを探すので遅いはず. 3.はvectorを配列と同じようにして使う場合. ここで ```c++ for (int i=0;i<vec.size();i++) ``` とすると, いちいちvectorのサイズを調べるので遅くなる. 実際に[[1](#jagabeeinitialize)]ではその結果がみれる. 4.はvectorではなく, listを使った場合. おそらく同じようになるはずなのでlistはこれだけ. 5.は比較対象の配列. 具体的なソースコードは以下のような感じ. [[2](#hirlab)]を参考にした. 総和を取る`for`文のみの時間を計測している. 中の`for`だけが異なる. ```c++ #include <iostream> #include <vector> #include <chrono> int main() { const int MAX_SIZE = 1000*1000; std::vector<int> vec; vec.reserve(MAX_SIZE); for (int i=1;i<=MAX_SIZE;i++) { vec.push_back(i); } long sum = 0; std::chrono::system_clock::time_point start, end; double time = 0.0; int trial = 100; for (int t=0;t<trial;t++) { start = std::chrono::system_clock::now(); for (auto i : vec) { sum += i; } end = std::chrono::system_clock::now(); time += std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); } std::cout << time / static_cast<double>(trial) << "ms" << "\n"; } ``` ## 環境 実行環境はGoogle Colaboratoryを使用した（そんなことに使うな）. 実際に作ったもののリンクは以下. https://colab.research.google.com/drive/1dWhBg6p0agVs4mk4cu8A-9wN4IqFJu8Y?usp=sharing - CPU: Intel(R) Xeon(R) CPU @ 2.30GHz - gcc version 7.5.0（C++17を指定） ## 結果 | 項 | 型 | 時間[ms] | | ---- | --------- | -------- | | 1 | vec auto | 11.14 | | 2 | vec iter | 16.2 | | 3 | vec array | 3.01 | | 4 | list | 36.48 | | 5 | array | 3.17 | なぜかlistがめちゃめちゃ遅いが, それ以外は予想通り. 配列（またはvectorを配列として使ったもの）が速く, それ以外の方法はそれより遅くなる. それでもvec auto型ではarray型に比べて3倍強しか違わない. またvec auto型とvec iterも1.5倍程度しか違いがない. C++を使う状況はハードに近い領域だったり, 制約が大きい状況が多いだろう. 配列かvectorかは速度と安全性のトレードオフだが, 速度面でどれだけ差があるかを知っておくと天秤にもかけやすいと思う. ## 参考 [1]<a name="jagabeeinitialize"></a> [一番効率のいいループ文はどれ？(std::vector) - レベルアップ！](http://jagabeeinitialize.hatenablog.com/entry/2018/01/24/001016) [2]<a name="hirlab"></a> [C++速度実験その２！vector配列の扱いについて | HIRO LAB BLOG](https://hirlab.net/nblog/category/programming/art_316/)