#include
#include
#include
#include
#include
#include
#include
#include
#include
#include "timsort.hpp"
using namespace gfx;
enum state_t {
sorted, randomized, reversed
};
template
static void bench(int const size, state_t const state) {
std::cerr << "size\t" << size << std::endl;
std::vector a;
for(int i = 0; i < size; ++i) {
a.push_back((i+1) * 10);
}
switch(state) {
case randomized:
std::random_shuffle(a.begin(), a.end());
break;
case reversed:
std::stable_sort(a.begin(), a.end());
std::reverse(a.begin(), a.end());
break;
case sorted:
std::stable_sort(a.begin(), a.end());
break;
default:
assert(!"not reached");
}
{
std::vector b(a);
boost::timer t;
for(int i = 0; i < 100; ++i) {
std::copy(a.begin(), a.end(), b.begin());
std::sort(b.begin(), b.end());
}
std::cerr << "std::sort " << t.elapsed() << std::endl;
}
{
std::vector b(a);
boost::timer t;
for(int i = 0; i < 100; ++i) {
std::copy(a.begin(), a.end(), b.begin());
std::stable_sort(b.begin(), b.end());
}
std::cerr << "std::stable_sort " << t.elapsed() << std::endl;
}
{
std::vector b(a);
boost::timer t;
for(int i = 0; i < 100; ++i) {
std::copy(a.begin(), a.end(), b.begin());
timsort(b.begin(), b.end());
}
std::cerr << "timsort " << t.elapsed() << std::endl;
}
}
static void doit(int const n, state_t const state) {
std::cerr << "[int]" << std::endl;
bench(n, state);
std::cerr << "[boost::rational]" << std::endl;
bench< boost::rational >(n, state);
}
int main(int argc, const char *argv[]) {
const int N = argc > 1
? boost::lexical_cast(argv[1])
: 100 * 1000;
std::cerr << std::setprecision(6) << std::setiosflags(std::ios::fixed);
std::srand(0);
std::cerr << "RANDOMIZED SEQUENCE" << std::endl;
doit(N, randomized);
std::cerr << "REVERSED SEQUENCE" << std::endl;
doit(N, reversed);
std::cerr << "SORTED SEQUENCE" << std::endl;
doit(N, sorted);
}