2019.02.01 プログラミング

C++速度実験その２！vector配列の扱いについて

コンテンツ

はじめに

C++は比較的機械寄りな言語で敷居が高いともいわれていますが，その分実行速度が速いことも大きな特徴であり，メリットです．

しかし！

書き方を少し間違えると，「あれ？遅くない？C++使えんな～」という状況に陥ってしまうこともしばしば...

そこで，C++速度実験その2ということで，今回は皆大好きvector配列に関する実験を行っていきます．

ちなみにその他のC++速度実験は↓

【NEW!! 関連記事】C++速度実験：vectorのpush_back()とemplace_back()について
【関連記事】C++速度実験！メンバ変数とGetterはどっちが速い？

実行環境

IDE	CLion 2018.3.3 © Jetbrains
CPU	Intel(R) Core(TM) i7-5500U CPU @2.40GHz(4 CPUs)
メモリ	8GB

vector配列

C++ではたくさんの配列があります．その中で最も速いと言われているのがvector配列です．しかし扱い方を間違えるとプログラムの遅い原因に繋がります．

実験！

今回比較するのは以下の2つのコード

vector<int> array;

for( int i = 0; i < 100000000; ++i )
    array.push_back( i );

vector<int> array;

for( int i = 0; i < 100000000; ++i )

array.push_back( i );

vector<int> array;
array.reserve( 100000000 );

for( int i = 0; i < 100000000; ++i )
    array.push_back( i );

vector<int> array;

array.reserve( 100000000 );

for( int i = 0; i < 100000000; ++i )

array.push_back( i );

どちらも100000000(1億)個のデータを格納するvector配列を生成するコードです．

違いは reserve() の有無のみです．

reserve() はvector配列のメモリを引数分だけ確保する関数です．

実験コード

実験には最終的には以下のコードを使いました．時間計測は chrono を使っています．

試行回数は10回で，計測時間の平均を結果とします．

#include <iostream>
#include <vector>
#include <chrono>

using namespace std;

/**
 * 実験1: 最初にメモリ確保しない
 */
void ex1(){
    vector<int> array;
    for( int i = 0; i < 100000000; ++i )
        array.push_back( i );
}
/**
 * 実験2: 最初にメモリ確保をする
 */
void ex2(){
    vector<int> array;
    array.reserve( 100000000 );
    for( int i = 0; i < 100000000; ++i )
        array.push_back( i );
}

int main() {
    int trial = 10; //! 試行回数
    double time = 0;
    chrono::system_clock::time_point start, end;
    for( int t = 0; t < trial; ++t ) {
        start = chrono::system_clock::now();

        //ex1();
        //ex2();

        end = chrono::system_clock::now();
        time += chrono::duration_cast<chrono::milliseconds>( end - start ).count() / 1000.0;
    }

    cout << time / static_cast<double>(trial) << endl;
    return 0;

}

#include <iostream>

#include <vector>

#include <chrono>

using namespace std;

/**

* 実験1: 最初にメモリ確保しない

void ex1(){

vector<int> array;

for( int i = 0; i < 100000000; ++i )

array.push_back( i );

}

/**

* 実験2: 最初にメモリ確保をする

void ex2(){

vector<int> array;

array.reserve( 100000000 );

for( int i = 0; i < 100000000; ++i )

array.push_back( i );

}

int main() {

int trial = 10; //! 試行回数

double time = 0;

chrono::system_clock::time_point start, end;

for( int t = 0; t < trial; ++t ) {

start = chrono::system_clock::now();

//ex1();

//ex2();

end = chrono::system_clock::now();

time += chrono::duration_cast<chrono::milliseconds>( end - start ).count() / 1000.0;

}

cout << time / static_cast<double>(trial) << endl;

return 0;

}

実験結果

実験	結果(秒)
実験1(初回メモリ確保なし)	1.9561秒
実験2(初回メモリ確保あり)	1.5239秒

あれ？そんなに差はないけど，少しだけ reserve() ありの方が速いという結果でした．個人的にはもう少し差がでるかな，と思ったんだけどなあ．

ちなみになんで差が出るかというと，vectorに要素を push_back() するときに，もしメモリ量が足りていない場合，現在確保しているメモリ分だけ新しく確保するからである．

つまり，5000個分メモリ確保をしていて，5001個目の要素を入れるときは5000個分のメモリを新たに確保するということ．

そう，無駄！

そして，都度メモリ確保していたら時間もそれなりにかかるわけです．
なので，今回のような結果になったということですね！

おまけの追実験

おまけで，型をintからdoubleに変えてみました．4バイトのintに比べて2倍の8バイトサイズのdoubleではどのくらい差が出るのか...

追実験(double)	結果(秒)
実験1(初回メモリ確保なし)	3.4731秒
実験2(初回メモリ確保あり)	2.8093秒

全体的に遅くなったけど，差はあまり広がりませんでした．

まとめ

vectorの最大要素数が決まっているときは最初にメモリ確保を行うようにしましょう！そうすると無駄なメモリ消費を抑え，大きな処理時間短縮につながるかもしれません！

またいつか第3弾やります．

[bfcc id="cpp_ex_2"]

タグ：
C++
vector
実験

C++速度実験その２！vector配列の扱いについて

はじめに

実行環境

vector配列

実験！

実験コード

実験結果

おまけの追実験

まとめ

おすすめの関連記事