A Microbenchmark Example
Discover the benchmarking results of linear and binary search algorithms.
We'll cover the following...
Benchmarking linear and binary search algorithms
We will wrap this chapter up by going back to our initial examples with linear search and binary search and demonstrate how they can be benchmarked using a benchmarking framework.
We began this chapter by comparing two ways of searching for an integer in a std::vector. If we knew that the vector was already sorted, we could use a binary search, which outperformed the simple linear search algorithm. We will not repeat the definition of the functions here, but the declaration looked like this:
bool linear_search(const std::vector<int>& v, int key);bool binary_search(const std::vector<int>& v, int key);
The difference in the execution time of these functions is very obvious once the input is sufficiently large, but it will serve as a good enough example for our purpose. We will begin by only measuring linear_search(). Then, when we have a working benchmark in place, we will add binary_search() and compare the two versions.
In order to make a testing program, we first need a way to generate a sorted vector of integers. A simple implementation, as follows, will be sufficient for our needs:
auto gen_vec(int n) {std::vector<int> v;for (int i = 0; i < n; ++i) {v.push_back(i);}return v;}