配列なめる順序とその方法&実験

ちょっと試してみる。sum取るところはどうでもいいんだが、配列なめる順序によってどれくらい速さが違うのか、iterator使うと速度どうなるのか、accumulateとか使うと早くなるのかなどを試したかった。実験に使ったのは以下のコードで、処理XXXを実験するときにはそれ以外はコメントアウトした。10回とかの平均取ろうかと思ったけど、傾向は変わらない感じだったので、とりあえず1回で。

# 色々と改善点があるので、追記のところを読んでください。

プログラム

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main(int argc, char **argv) {
  const int N = 10000;

  vector<vector<int> > A(N);
  for (int i = 0; i < N; i++) {
	A[i].resize(N);
	for (int j = 0; j < N; j++) {
	  A[i][j] = i * j;
	}
  }
  
  // 処理A
  for (int i = 0; i < N; i++) {
	int sum = 0;
	for (int j = 0; j < N; j++) {
	  sum += A[i][j];
	}
  }

  // 処理B
  for(vector<vector<int> >::iterator it = A.begin(); it != A.end(); it++) {
	int sum = 0;
	for(vector<int>::iterator jt = it->begin(); jt != it->end(); jt++) {
	  sum += *jt;
	}
  }

  // 処理C
  for (int j = 0; j < N; j++) {
	int sum = 0;
	for (int i = 0; i < N; i++) {
	  sum += A[i][j];
	}
  }

  // 処理D
  for (int i = 0; i < N; i++) {
	accumulate(A[i].begin(), A[i].end(), 0);
  }
};

実験結果

処理A。

/Users/yasuhisa/cpp% g++ accumulate.cpp; time ./a.out
./a.out  2.76s user 0.61s system 38% cpu 8.707 total

処理B。

/Users/yasuhisa/cpp% g++ accumulate.cpp; time ./a.out
./a.out  5.04s user 0.64s system 42% cpu 13.443 total

処理C。

/Users/yasuhisa/cpp% g++ accumulate.cpp; time ./a.out
./a.out  10.57s user 0.70s system 40% cpu 27.769 total

処理D。

/Users/yasuhisa/cpp% g++ accumulate.cpp; time ./a.out
./a.out  3.52s user 0.62s system 43% cpu 9.504 total

考察

処理Dが一番早いと思ったらindexをそのまま書いていくやつが一番早かった。...あれ?iterator使ったやつも割りと遅くなってしまっている。。。

処理Cが一番遅くなるのは予想通りで、そんなもんかという感じ。

追記

結果が直感に合わん...と思ったら使い方が悪いところが多々あった。基本的にはindex指定してほげほげするよりiterator使ったりaccumulate使ったほうが早いんだが、今回の場合は以下の付近がまずかった。

毎回endを呼ばない

この辺。

  for(vector<vector<int> >::iterator it = A.begin(); it != A.end(); it++) {

毎回endを呼ぶのであれ。最初に一度だけ呼ぶようにしましょう。ループの回数が多いと効いてくるときもある。

for(vector<vector<int> >::iterator it = A.begin(), it_end = A.end(); it != it_end; ++it) {

特別な理由がなければ後置インクリメントではなく前置インクリメントを使う

後置インクリメントは一時オブジェクトを生成するので、特別な理由がなければ前置インクリメントを使用するようにすること。詳細は以下の本のp22のコラムに載っている。

Exceptional C++―47のクイズ形式によるプログラム問題と解法 (C++ in‐Depth Series)

operator[]とiterator

operator[]も内部でiteratorを使っているとのことらしく、直でiteratorを使ったほうが早いらしい(operator[n]経由で一時的にiteratorを作ったり)。

結論

追記に書いたことをきちんとやったらaccumulateを使ったやつが一番早く、iteratorを使ったものが2番、index指定するのが3番という結果になりましたとさ。id:mickey24++。