patterncppMinor
Measure execution time of sorting algorithms
Viewed 0 times
sortingtimealgorithmsmeasureexecution
Problem
I have to measure execution time of certain sorting algorithms being passed as functions in following program. I also do not have to measure it on random container but also on ascending as well as descending sorted containers.
Header file:
.cpp file:
```
#include "cs-iv-algorithm.h"
unsigned int sortT::findSentinel() {
/*
* Get numeric limit of long long
* normalize it by subtracting remainder
* find out max upperlimit by clean divide of 10
*/
long long sentinel = std::numeric_limits::max();
sentinel = sentinel - (sentinel % 10);
unsigned int k = 0;
while (sentinel != 0) {
sentinel /= 10;
++k;
}
return k;
}
void sortT::seed() {
// reserve upLim amount of sub-vectors
random.reserve(upLim);
asc.reserve(upLim);
desc.reserve(upLim);
for (unsigned int i = 1; i r, a, d;
r.reserve(limit);
a.reserve(limit);
d.reserve(limit);
// random number generation
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<> distr(1, 10000);
for (long long k = 1; k ::iterator,
std::vector::iterator)) {
unsigned int i = 0;
while (i (tp2 - tp1);
tp1 = std::chron
Header file:
#include
#include
#include
#include
#include
#include
class sortT {
private:
std::vector> asc;
std::vector> desc;
std::vector> random;
unsigned int upLim; // Upperlimit 1=10, 2=100...
void seed();
unsigned int findSentinel(); // returns largest upperlimit possible
public:
// default + param constructor -> calls seed()
sortT(unsigned int lim = 3) : upLim(lim) {
if (upLim s) { upLim = 3; }
}
seed();
};
// exposing list in public
std::vector> list;
void testWith(void sortF(std::vector::iterator,
std::vector::iterator));
void printList();
unsigned int getUpLim() { return upLim; }
};.cpp file:
```
#include "cs-iv-algorithm.h"
unsigned int sortT::findSentinel() {
/*
* Get numeric limit of long long
* normalize it by subtracting remainder
* find out max upperlimit by clean divide of 10
*/
long long sentinel = std::numeric_limits::max();
sentinel = sentinel - (sentinel % 10);
unsigned int k = 0;
while (sentinel != 0) {
sentinel /= 10;
++k;
}
return k;
}
void sortT::seed() {
// reserve upLim amount of sub-vectors
random.reserve(upLim);
asc.reserve(upLim);
desc.reserve(upLim);
for (unsigned int i = 1; i r, a, d;
r.reserve(limit);
a.reserve(limit);
d.reserve(limit);
// random number generation
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<> distr(1, 10000);
for (long long k = 1; k ::iterator,
std::vector::iterator)) {
unsigned int i = 0;
while (i (tp2 - tp1);
tp1 = std::chron
Solution
Generally speaking, there isn't much to say and I can't find any obvious flow at first sight. I'll have to comment on small things instead:
-
This signature struck me as begin rather restrictive:
I understand that you only test vector sorting algorithms, but you could have the function type as a template parameter instead:
And still call it like that:
This would allow you to use function objects too and to use generic functions not especially designed to sort vectors, but that can still sort a vector.
-
You could avoid duplication with a dedicated function to time one function at a time:
Then you could reimplement
Note that I also rewrote your algorithm with a
-
By the way, instead of constructing an
-
Also, since you know that your
-
I speak of expanding the code since you probably want to add a pipe organ test case to your tests since some sorting algorithms are known to perform poorly with pipe organ patterns.
-
-
Instead of having a
-
This signature struck me as begin rather restrictive:
void testWith(void sortF(std::vector::iterator,
std::vector::iterator));I understand that you only test vector sorting algorithms, but you could have the function type as a template parameter instead:
template
void testWith(BinaryFunction sortF);And still call it like that:
sortF(random[i].begin(), random[i].end());This would allow you to use function objects too and to use generic functions not especially designed to sort vectors, but that can still sort a vector.
-
You could avoid duplication with a dedicated function to time one function at a time:
template
auto timeIt(Function function)
-> std::chrono::microseconds
{
auto tp1 = std::chrono::high_resolution_clock::now();
function();
auto tp2 = std::chrono::high_resolution_clock::now();
return std::chrono::duration_cast(tp2 - tp1);
}Then you could reimplement
testWith with a few lambdas to simplify things:template
void sortT::testWith(BinaryFunction sortF) {
for (unsigned int i = 0 ; i < upLim ; ++i) {
auto duration1 = timeIt([]{
sortF(random[i].begin(), random[i].end());
});
auto duration2 = timeIt([]{
sortF(asc[i].begin(), asc[i].end());
});
auto duration3 = timeIt([]{
sortF(desc[i].begin(), desc[i].end());
});
list.push_back(std::make_tuple(duration1, duration2, duration3));
}
}Note that I also rewrote your algorithm with a
for loop instead of a while loop. When you have severa tools at hand, try to pick the most suitable one for the job. Actually, it would make sense for most of your while loops to be replaced by for loops.-
By the way, instead of constructing an
std::tuple and pushing it into list, you could directly create it into list with emplace_back:list.emplace_back(duration1, duration2, duration3);-
Also, since you know that your
list will only ever contain instances of std::chrono::microseconds, you might want to use an std::array instead of the more verbose std::tuple. It will make your code easier to expand and to read.-
I speak of expanding the code since you probably want to add a pipe organ test case to your tests since some sorting algorithms are known to perform poorly with pipe organ patterns.
-
const-correctness is important in C++ semantics. If one of your functions does not alter the class members, then mark it const:unsigned int getUpLim() const { return upLim; }-
Instead of having a
printList method, it would be more idiomatic to overload operator
-
When possible, try to use compound assignment operators to make your code shorter and hypothetically more performant. For example, turn this line:
sentinel = sentinel - (sentinel % 10);
into this one:
sentinel -= sentinel % 10;
-
Instead of reinitializing your random number engine everytime you call seed, you could let it live its life once initialized since it should still produce different results everytime seed is invoked:
// random number generation
thread_local std::random_device rd;
thread_local std::mt19937 eng(rd());
thread_local std::uniform_int_distribution<> distr(1, 10000);
Making the instances thread_local make sure there is one instance per thread. It makes generating random numbers inherently thread-safe while not having to initialize the engine again everytime you call seed`.Code Snippets
void testWith(void sortF(std::vector<long long>::iterator,
std::vector<long long>::iterator));template<typename BinaryFunction>
void testWith(BinaryFunction sortF);sortF(random[i].begin(), random[i].end());template<typename Function>
auto timeIt(Function function)
-> std::chrono::microseconds
{
auto tp1 = std::chrono::high_resolution_clock::now();
function();
auto tp2 = std::chrono::high_resolution_clock::now();
return std::chrono::duration_cast<std::chrono::microseconds>(tp2 - tp1);
}template<typename BinaryFunction>
void sortT::testWith(BinaryFunction sortF) {
for (unsigned int i = 0 ; i < upLim ; ++i) {
auto duration1 = timeIt([]{
sortF(random[i].begin(), random[i].end());
});
auto duration2 = timeIt([]{
sortF(asc[i].begin(), asc[i].end());
});
auto duration3 = timeIt([]{
sortF(desc[i].begin(), desc[i].end());
});
list.push_back(std::make_tuple(duration1, duration2, duration3));
}
}Context
StackExchange Code Review Q#97589, answer score: 3
Revisions (0)
No revisions yet.