sequential access
listにランダムアクセスはできないので、
これの速度を調べる。
const int m = 1000; // コンテナの大きさ
const int n = (int)(1e10 / m); // 繰り返し回数void procVector() {
vectorv;
for(int k = 0; k < m; k++)
v.push_back(k);
int sum = 0;
typedef vector::const_iterator CIT;
for(int i = 0; i < n; i++) {
for(CIT p = v.begin(); p != v.end(); ++p)
sum += *p;
}
cerr << sum << endl;
}void procList() {
listl;
for(int k = 0; k < m; k++)
l.push_back(k);
int sum = 0;
typedef list::const_iterator CIT;
for(int i = 0; i < n; i++) {
for(CIT p = l.begin(); p != l.end(); ++p)
sum += *p;
}
cerr << sum << endl;
}
2桁多く繰り返して、ひたすら足す。
オーバーフローは気にしない。
これで、
vector : 6.645s、list : 36.436s
とにかくvectorのほうが圧倒的に速い。
ところで、単純な足し算と比べてみると、
void pureSum() {
int sum = 0;
for(int i = 0; i < n; i++) {
for(int k = 0; k < m; k++)
sum += k;
}
cerr << sum << endl;
}
これで、6.942s
と何回やってもこちらのほうがvectorより遅くなる。
どういう仕組みになっているのだろう。