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

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

ランダムベクトルにたいするsortの時間を決定する

STL―標準テンプレートライブラリによるC++プログラミング 第2版
アルゴリズムの実行時間を計るための Timer クラスを作った。データが増えたときに時間がどのように増えるのか確かめることができる。Report の実行結果を見ると sort の場合 O(N log N) であるのがなんとなく分かる。
データサイズが8000を超えてからは表示がおかしい。これは計る基準である 1000ms 以上時間がかかってしまったため。本のソースが悪いんだいw

// P286 ex19-02.cpp
#include<vector>
#include<ctime>
#include<map>
#include<algorithm>
#include<iostream>
#include<iomanip>
class Timer{
 unsigned repeats_;
 std::vector<long> iterations_;
 std::time_t initial_, final_;
 unsigned long count_;
 unsigned problemSize_;
 std::map<unsigned, double> resultMap_;
 bool baseline_;
 double baselineTime_;
public:
 Timer()
  : baseline_(false)
 {}
 void Start(unsigned repeats, unsigned long size)
 {
  repeats_ = repeats;
  problemSize_ = size;
  count_ = 0;
  iterations_.clear();
  iterations_.reserve(repeats);
  initial_ = std::time(0);
 }
 void StartBaseline(unsigned repeats)
 {
  baseline_ = true;
  Start(repeats, 0);
 }
 bool Check()
 {
  ++count_;
  final_ = std::time(0);
  if(initial_ < final_){
   iterations_.push_back(count_);
   initial_ = final_;
   count_ = 0;
  }
  return iterations_.size() < repeats_;
 }
 void Report(bool verbose)
 {
  using namespace std;
  if(verbose){
   for(unsigned i = 0; i < iterations_.size(); ++i){
    cout << iterations_[i] << " ";
    if((i + 1) % 10 == 0)cout << endl;
   }
  }
  std::sort(iterations_.begin(), iterations_.end());
  if(verbose){
   std::cout << "Sorted counts:" << std::endl;
   for(unsigned i = 0; i < iterations_.size(); ++i){
    cout << iterations_[i] << " ";
    if((i + 1) % 10 == 0)cout << endl;
   }
  }
  const int selectedCount = iterations_[repeats_ / 2];
  if(verbose)cout << " Selected count: " << selectedCount << endl;
  if(baseline_){
   baselineTime_ = 1000. / selectedCount;
   cout << "Baseline time: " << baselineTime_ << endl;
   baseline_ = false;
  }else{
   const double calculatedTime = resultMap_[problemSize_] =
    1000. / selectedCount - baselineTime_;
   cout << setiosflags(ios::fixed) << setprecision(4) << setw(35)
    << problemSize_ << setw(12) << calculatedTime << " ms ";
   if(resultMap_.find(problemSize_/2) != resultMap_.end()){
    const double growthFactor = calculatedTime / resultMap_[problemSize_/2];
    cout << setiosflags(ios::fixed) << setprecision(4) << setw(8)
     << growthFactor;
   }
   cout << endl;
  }
 }
 const std::map<unsigned, double>& Results()const
 {
  return resultMap_;
 }
};
template<typename T> T In(){
  T t;
  std::cin >> t;
  return t;
}
int main(){
 using std::cout;
 using std::endl;
 using std::srand;
 using std::time;
 using std::vector;
 using std::rand;
 using std::sort;

 cout << "Timing sort on random vectors.\n"
  "Repetitions, initial size, and final size: ";

 typedef unsigned T;
 const T repeat = In<T>(),
  initSize = In<T>(),
  finalSize = In<T>();
 srand(static_cast<unsigned>(time(0)));
 vector<double> v;
 Timer timer; // 宣言

 for(T size = initSize; size <= finalSize; size *= 2){
  v.clear(), v.reserve(size);
  for(T i = 0; i < size; ++i){
   v.push_back(rand());
  }
  vector<double> tmp = v;

  timer.StartBaseline(repeat); // オーバーヘッド分を計測
  do{
   v = tmp;
  }while(timer.Check()); // 一定時間
  timer.Report(false); // 報告

  timer.Start(repeat, size); // 本番計測
  do{
   v = tmp;
   sort(v.begin(), v.end());
  }while(timer.Check()); // 一定時間
  timer.Report(false); // 報告
 }
}

出力例:

Timing sort on random vectors.
Repetitions, initial size, and final size: 11 1000 64000
Baseline time: 0.00553517
                               1000     62.4945 ms
Baseline time: 0.0082
                               2000    142.8489 ms   2.2858
Baseline time: 0.0151
                               4000    333.3182 ms   2.3334
Baseline time: 0.1276
                               8000    999.8724 ms   2.9998
Baseline time: 0.6689
                              16000    999.3311 ms   0.9995
Baseline time: 1.3369
                              32000    998.6631 ms   0.9993
Baseline time: 2.6316
                              64000    997.3684 ms   0.9987