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

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

sortアルゴリズムの時間を決定する最初の試み

STL―標準テンプレートライブラリによるC++プログラミング 第2版
無駄に boost::shared_array を使ってみた。

// P277 ex19-01.cpp
#include<iostream>
#include<boost/shared_array.hpp>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<algorithm>
#include<iterator>
unsigned long InputArraySize(){
 unsigned long size = 0;
 std::cin >> size;
 return size;
}
unsigned InputRepetition(){
 unsigned repeat = 0;
 std::cin >> repeat;
 return repeat;
}
struct Rand{
 Rand(){std::srand(static_cast<unsigned>(std::time(0)));}
 void operator()(double& d){d = std::rand();}
};
// REPEAT 回
// time(0) の値が変わる1秒間に何回sortできるか調べる。
// ソートできた回数にはむらがあるので,メディアンをとる。
int main(){
 using std::cout;
 using std::endl;
 using boost::shared_array;
 using std::for_each;
 using std::vector;
 using std::copy;
 using std::sort;
 cout << "First attempt at timing the sort algorithm.\n"
  "Input array size and repetitions: ";
 const unsigned long SIZE = InputArraySize();
 const unsigned REPEAT = InputRepetition();
 // 同じ条件でsortできるように src から dst へコピーする
 shared_array<double> src(new double[SIZE]);
 shared_array<double> dst(new double[SIZE]);
 
 for_each(src.get(), src.get() + SIZE, Rand());
 vector<long> iterations;
 iterations.reserve(REPEAT);

 time_t start = time(0), finish;
 while(iterations.size() < REPEAT){
  int count = 0;
  do{
   ++count;
   copy(src.get(), src.get() + SIZE, dst.get());
   sort(dst.get(), dst.get() + SIZE);
   finish = time(0);
  }while(finish == start);
  iterations.push_back(count);
  start = finish;
 }

 cout << "Iteration counts: " << endl;
 std::ostream_iterator<double> o(cout, " ");
 copy(iterations.begin(), iterations.end(), o); cout << endl;

 cout << "Sorted iteration counts: " << endl;
 sort(iterations.begin(), iterations.end());
 copy(iterations.begin(), iterations.end(), o); cout << endl;

 cout << "Selected value: " << iterations[REPEAT / 2] << endl;
 cout << "Time: " << 1000. / iterations[REPEAT/ 2] << " ms" << endl;
}

出力例:

First attempt at timing the sort algorithm.
Input array size and repetitions: 10000 10
Iteration counts:
6 16 18 17 17 17 14 16 17 17
Sorted iteration counts:
6 14 16 16 17 17 17 17 17 18
Selected value: 17
Time: 58.8235 ms