とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

内積を計算 std::vector vs std::map

STL―標準テンプレートライブラリによるC++プログラミング 第2版
map の方が計算回数が少なくなるという説明だけど,処理にかかった時間では vector の方が早かったというw 初期化も含めたところ差が広がりました。

// P174 ex07-05.cpp
// P175 ex07-06.cpp
#include<iostream>
#include<vector>
#include<map>
#include<boost/progress.hpp>
const int N = 600000, S = 10;
template<typename Container>
void Init(Container& a, Container& b){
 for(int i = 0; i * 3 * S < N; ++i)
  a[i * 3 * S] = 1.0;
 for(int i = 0; i * 5 * S < N; ++i)
  b[i * 5 * S] = 1.0;
}
int main(){
 using std::cout;
 using std::flush;
 using std::endl;
 using std::vector;
 using std::map;
 {
  vector<double> x(N), y(N);
  cout << "Computing an inner product of tuples represented as "
   "vectors.\nInitializing..." << endl;
  Init(x, y);
  cout << "Computing inner product by brute force: " << flush;
  boost::progress_timer t;
  double sum = 0;
  for(int i = 0; i < N; ++i)sum += x[i] * y[i];
  cout << sum << endl;
 }
 {
  std::map<long, double> x, y;
  cout << "Computing an inner product of tuples represented as "
   "maps.\nInitializing..." << endl;
  Init(x, y);
  cout << "Computing inner product taking advantage of sparseness: " << flush;
  boost::progress_timer t;
  double sum = 0;
  map<long, double>::const_iterator ix = x.begin(), iy;
  for(; ix != x.end(); ++ix){
   iy = y.find(ix->first);
   if(iy != y.end())sum += ix->second * iy->second;
  }
  cout << sum << endl;
 }
}

出力例:

Computing an inner product of tuples represented as vectors.
Initializing...
Computing inner product by brute force: 4000
0.34 s

Computing an inner product of tuples represented as maps.
Initializing...
Computing inner product taking advantage of sparseness: 4000
0.44 s