forked from MichaelAxtmann/cpp-TimSort
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbench.cpp
More file actions
126 lines (102 loc) · 2.98 KB
/
bench.cpp
File metadata and controls
126 lines (102 loc) · 2.98 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/*
* Copyright (c) 2011 Fuji, Goro (gfx) <gfuji@cpan.org>.
* Copyright (c) 2019 Morwenn.
*
* SPDX-License-Identifier: MIT
*/
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <vector>
#include <gfx/timsort.hpp>
using namespace gfx;
enum state_t { sorted, randomized, reversed };
template <typename T>
struct convert_to
{
static T from(int value) {
return T(value);
}
};
template <>
struct convert_to<std::string>
{
static std::string from(int value) {
std::ostringstream ss;
ss << value;
return ss.str();
}
};
template <typename value_t>
static void bench(int size, state_t const state) {
std::cerr << "size\t" << size << std::endl;
std::vector<value_t> a;
for (int i = 0; i < size; ++i) {
a.push_back(convert_to<value_t>::from((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<value_t> b(a);
std::clock_t start = std::clock();
for (int i = 0; i < 100; ++i) {
std::copy(a.begin(), a.end(), b.begin());
std::sort(b.begin(), b.end());
}
std::clock_t stop = std::clock();
std::cerr << "std::sort " << (double(stop - start) / CLOCKS_PER_SEC) << std::endl;
}
{
std::vector<value_t> b(a);
std::clock_t start = std::clock();
for (int i = 0; i < 100; ++i) {
std::copy(a.begin(), a.end(), b.begin());
std::stable_sort(b.begin(), b.end());
}
std::clock_t stop = clock();
std::cerr << "std::stable_sort " << (double(stop - start) / CLOCKS_PER_SEC) << std::endl;
}
{
std::vector<value_t> b(a);
std::clock_t start = std::clock();
for (int i = 0; i < 100; ++i) {
std::copy(a.begin(), a.end(), b.begin());
timsort(b.begin(), b.end());
}
std::clock_t stop = std::clock();
std::cerr << "timsort " << (double(stop - start) / CLOCKS_PER_SEC) << std::endl;
}
}
static void doit(int const n, state_t const state) {
std::cerr << "[int]" << std::endl;
bench<int>(n, state);
std::cerr << "[std::string]" << std::endl;
bench<std::string>(n, state);
}
int main(int argc, const char *argv[]) {
const int N = argc > 1 ? std::atoi(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);
}