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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
#if 0
import <chrono>;
import <vector>;
import <iostream>;
import <algorithm>;
import <string>;
import <thread>;
#else
#include <chrono>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <thread>
#include <random>
#endif
class Measure
{
public:
Measure()
: start(std::chrono::high_resolution_clock::now())
{
}
~Measure()
{
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> delta = end - start;
std::cout << " " << delta.count() * 1000 << " ms passed" << std::endl;
}
std::chrono::time_point<std::chrono::high_resolution_clock> start{};
};
template<typename Callable>
void measure(const std::string& text, Callable c)
{
std::cout << text << ":\n";
for(int i = 0; i < 3; ++i)
{ // RAII timed scoped
Measure m;
c();
}
}
int main()
{
using namespace std::chrono_literals;
// Sanity check measurement mechanism
measure("Sanity check (sleep 100ms):",
[]()
{
std::this_thread::sleep_for(100ms);
});
// std::find() on a vector<int>:
// Use a vector large enough to get meaningful values on your machine
// (1,000,000 elements are likely not enough). Measure the time needed to
// * Find the 7 in the middle of a vector<int> where all other elements are
// not 7.
{
std::vector<int> v(1'000'000, 42); // one million items with the int 42
v[v.size() / 2] = 7; // set middle item to 7
measure("std::find 7 in the middle",
[&v]()
{
std::find(v.begin(), v.end(), 7);
});
}
// * Try to find a 7 in a vector<int> where no element is 7
{
std::vector<int> v(1'000'000, 42); // one million items with the int 42
measure("std::find 7 not there",
[&v]()
{
std::find(v.begin(), v.end(), 7);
});
}
// std::find_if() on a vector<int>:
// Use a vector large enough to get meaningful values on your machine.
// Measure the time needed to
// * Find the x < 7 in the middle of a vector<int> where all other elements
// are >= 7.
{
std::vector<int> v(1'000'000, 42); // one million items with the int 42
v[v.size() / 2] = 5; // set middle item to 5
measure("std::find_if x < 7 in the middle",
[&v]()
{
std::find_if(v.begin(), v.end(), [](int x){ return x < 7;});
});
}
// * Try to find an x < 7 in a vector<int> where all elements are >= 7.
{
std::vector<int> v(1'000'000, 42); // one million items with the int 42
measure("std::find_if x < 7 not there",
[&v]()
{
std::find_if(v.begin(), v.end(), [](int x){ return x < 7;});
});
}
// std::find() on a vector<std::string>:
// Generate a vector<string> containing 1,000,000 random 20-letter strings
// (don't bother timing this).
{
std::default_random_engine generator;
// Randomly generate characters from the range [A;Z]
std::uniform_int_distribution<char> distrib('A', 'Z');
std::vector<std::string> vs;
vs.resize(1'000'000);
for(auto &str: vs)
{
str.reserve(20);
for(auto i = 0u; i < str.capacity(); ++i)
{
str += distrib(generator);
}
}
std::string needle(20, 'X');
// Measure the time needed to
// * Try to find XXXXXXXXXXXXXXXXXXXX (20 Xs) in that vector using
// std::find().
measure("Find " + needle + " (not there)",
[&]()
{
if(std::find(vs.begin(), vs.end(), needle) != std::end(vs))
{
std::cout << "That was unexpected!\n";
}
});
// * Was it there? Unlikely, but if so, try with another value.
// Alternatively (optional), ensure you never generate
// XXXXXXXXXXXXXXXXXXXX in the first place.
//
// * Place XXXXXXXXXXXXXXXXXXXX (or whatever value is not present) in the
// middle and find it using std::find().
vs[vs.size() / 2] = needle;
measure("Find " + needle + " (in the middle)",
[&]()
{
if(std::find(vs.begin(), vs.end(), needle) == std::end(vs))
{
std::cout << "That was unexpected!\n";
}
});
}
}
|
