読者です 読者をやめる 読者になる 読者になる

タイトルって難しい。

学力も体力もない人間の雑記帳。

【C++】配列とVectorとArrayで比較

C++

きっかけ

以前、C++で実装した際に、コードを読まれた方からなんでVectorにしないの?と聞かれたことがありました。
機能面での違いはたしかにありますが、固定サイズならば別に配列でもOKではと思っていたのですが、ふと気になったので調べてみました。

比較対象

比較した方法は次の4通りです。

  • 配列(一番最初に習うであろうもの)
  • Vector(配列っぽく)
  • Vector(push_back)
  • Array(C++11から追加されたもの)

Vector同士で比較しているのは、配列っぽく使うパターンと、push_backで代入させた場合のものの2種類です。
push_backは遅いと書いていらっしゃる方もいたので、比較として入れてみようと思い、含めました。

コード

ダメダメながらも書いたコードは次に続きます。
やったことはすごく単純で、10万のデータを作って、そのデータから総和を求めるという操作です。
もっと良いベンチマークがあるかもしれませんが…。

配列(一番最初に習うであろうもの)

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <chrono>

int main(int argc, char const *argv[]) {
  std::chrono::system_clock::time_point start, end;
  double elapsed;
  const long int MAX = 100000;
  long int a[MAX+1];
  // Array
  start = std::chrono::system_clock::now();
  for (long int i = 0; i <= MAX; i++) {
    a[i] = i;
  }
  long int sum1 = 0;
  for (long int i = 0; i <= MAX; i++) {
    sum1 += a[i];
  }
  end = std::chrono::system_clock::now();
  elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count();
  std::cout << elapsed << "μs" << std::endl;
  return 0;
}

↑の修正版

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <chrono>

int main(int argc, char const *argv[]) {
  std::chrono::system_clock::time_point start, end;
  double elapsed;
  const long int MAX = 100000;
  long int a[MAX+1] ={};
  // Array
  start = std::chrono::system_clock::now();
  for (long int i = 0; i <= MAX; i++) {
    a[i] = i;
  }
  long int sum1 = 0;
  for (long int i = 0; i <= MAX; i++) {
    sum1 += a[i];
  }
  end = std::chrono::system_clock::now();
  elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count();
  std::cout << elapsed << "μs" << std::endl;
  return 0;
}

Vector(配列っぽく)

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <chrono>

int main(int argc, char const *argv[]) {
  std::chrono::system_clock::time_point start, end;
  double elapsed;
  const long int MAX = 100000;
  std::vector<long int> b1(MAX);

  // vector(like Array)
  start = std::chrono::system_clock::now();
  for (long int i = 0; i <= MAX; i++) {
    b1[i] = i;
  }
  long int sum2 = 0;
  for (long int i = 0; i <= MAX; i++) {
    sum2 += b1[i];
  }
  end = std::chrono::system_clock::now();
  elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count();
  std::cout << elapsed << "μs" << std::endl;
  return 0;
}

Vector(push_back)

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <chrono>

int main(int argc, char const *argv[]) {
  std::chrono::system_clock::time_point start, end;
  double elapsed;
  const long int MAX = 100000;
  std::vector<long int> b2;
  // vector(push_back)
  start = std::chrono::system_clock::now();
  for (long int i = 0; i <= MAX; i++) {
    b2.push_back(i);
  }
  long int sum3 = 0;
  for (long int i = 0; i <= MAX; i++) {
    sum3 += b2[i];
  }
  end = std::chrono::system_clock::now();
  elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count();
  std::cout << elapsed << "μs" << std::endl;
  return 0;
}

Array(C++11から追加されたもの)

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <chrono>

int main(int argc, char const *argv[]) {
  std::chrono::system_clock::time_point start, end;
  double elapsed;
  const long int MAX = 100000;
  std::array<long int, MAX> c;
  // C++11's Array
  start = std::chrono::system_clock::now();
  for (long int i = 0; i <= MAX; i++) {
    c[i] = i;
  }
  long int sum4 = 0;
  for (long int i = 0; i <= MAX; i++) {
    sum4 += c[i];
  }
  end = std::chrono::system_clock::now();
  elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count();
  std::cout << elapsed << "μs" << std::endl;
  return 0;
}

↑の修正版

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <chrono>

int main(int argc, char const *argv[]) {
  std::chrono::system_clock::time_point start, end;
  double elapsed;
  const long int MAX = 100000;
  std::array<long int, MAX> c = {};
  // C++11's Array
  start = std::chrono::system_clock::now();
  for (long int i = 0; i <= MAX; i++) {
    c[i] = i;
  }
  long int sum4 = 0;
  for (long int i = 0; i <= MAX; i++) {
    sum4 += c[i];
  }
  end = std::chrono::system_clock::now();
  elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count();
  std::cout << elapsed << "μs" << std::endl;
  return 0;
}

結果

単位はすべて、μsことマイクロ秒(100万分の1秒)
rev2とついてるものは修正版です。

Ruby@Kotori-no-MacBook-Pro ~/Desktop $ ./array.out
792μs
Ruby@Kotori-no-MacBook-Pro ~/Desktop $ ./array_rev2.out
489μs
Ruby@Kotori-no-MacBook-Pro ~/Desktop $ ./vector_like_array.out
603μs
Ruby@Kotori-no-MacBook-Pro ~/Desktop $ ./vector_push_back.out
2962μs
Ruby@Kotori-no-MacBook-Pro ~/Desktop $ ./array_cpp11.out
827μs
Ruby@Kotori-no-MacBook-Pro ~/Desktop $ ./array_cpp11_rev2.out
528μs

やっぱりpush_backは遅いですね。
Vectorを配列っぽく使うと配列と変わらない速度みたいです。
あと意外にもC++11から追加されたArrayはわずかながら配列より遅いみたいです。なぜでしょうか。
と思っていましたが、初期化を行ったうえで再実験行ってみたら配列が一番高速でした。次に、Array(C++11以降)が速いという結果となりました。

まとめ

今後はVectorを配列っぽく使います。
いや、修正した結果、配列が速かったのでやっぱり配列が一番ですね。

追記1(2016.07.09 0:27 UTC+9)

一部のコードを修正前のものを記載していました。修正しました。
なお、結果は修正後のものを記載しているため、変化ありません。

追記2(2016.07.09 0:52 UTC+9)

研究室の先輩(id:togatogah)から、「配列とArray(C++11以降)の初期化されていない可能性があるのに対し、Vectorは構築時に必ず初期化を行うので、配列とArrayを初期化してみてはどうか」という提案がありました。
そこで試してみたところ、大きく結果が変わりました。 id:togatogahさんありがとうございました。

プログラミング言語C++第4版

プログラミング言語C++第4版