SortingBenchmark.h

Go to the documentation of this file.

#ifndef SORTINGBENCHMARK_H
#define SORTINGBENCHMARK_H
 
#include <LineChart.h>
#include <limits>
#include <vector>
#include <chrono>
#include <stdlib.h>
 
namespace bridges {
    namespace benchmark {
        using namespace bridges::datastructure;
 
        class SortingBenchmark {
            private:
                LineChart& plot;
 
                int maxSize;
                int baseSize;
                int increment;
                double geoBase;
                double time_cap;
                std::string generatorType;
 
                void generateRandom(int* arr, int n) {
                    for (int i = 0; i < n; i++) {
                        arr[i] = ((double)rand()) / RAND_MAX * (2 * n);
                    }
                }
 
                void generateInOrder(int* arr, int n) {
                    for (int i = 0; i < n; i++) {
                        arr[i] = i;
                    }
                }
                void generateReverseOrder(int* arr, int n) {
                    for (int i = 0; i < n; i++) {
                        arr[i] = n - i;
                    }
                }
                void generateFewValues(int* arr, int n) {
                    for (int i = 0; i < n; i++) {
                        arr[i] = ((double)rand()) / RAND_MAX * (4);
                    }
                }
                void generateAlmostSorted(int* arr, int n) {
                    if (n < 20) {
                        generateRandom(arr, n);
                    }
                    else {
                        int i;
                        for (i = 0; i < n - 20; i++) {
                            arr[i] = i;
                        }
                        for (; i < n; i++) {
                            arr[i] = ((double)rand()) / RAND_MAX * (2 * n);
                        }
                    }
                }
 
                void generate(int* arr, int n) {
                    if (generatorType == "random") {
                        generateRandom(arr, n);
                    }
                    else if (generatorType == "inorder") {
                        generateInOrder(arr, n);
                    }
                    else if (generatorType == "reverseorder") {
                        generateReverseOrder(arr, n);
                    }
                    else if (generatorType == "fewdifferentvalues") {
                        generateFewValues(arr, n);
                    }
                    else if (generatorType == "almostsorted") {
                        generateAlmostSorted(arr, n);
                    }
                    else {
                        throw std::string("unknown generator");
                    }
 
                }
 
                bool check (int* arr, int n) {
                    bool ok = true;
                    for (int i = 1; i < n; ++i) {
                        if (arr[i] < arr[i - 1]) {
                            ok = false;
                        }
                    }
                    return ok;
                }
 
            public:
                SortingBenchmark(LineChart& p)
                    : plot (p) {
                    p.setXLabel("Size of Array");
                    p.setYLabel("Runtime (in s)");
 
                    //r = new Random();
 
                    maxSize = 1;
                    baseSize = 1;
                    increment = 1;
                    geoBase = 1.;
                    time_cap = std::numeric_limits<double>::max();
                    setGenerator("random");
                }
 
                void setGenerator(const std::string& generatorName) {
                    generatorType = generatorName;
                }
 
                std::string getGenerator() const {
                    return generatorType;
                }
                void setMaxSize(int size) {
                    maxSize = size;
                }
 
                void setBaseSize(int size) {
                    baseSize = size;
                }
 
                void setIncrement(int inc) {
                    increment = inc;
                }
 
                void setGeometric(double base) {
                    geoBase = base;
                }
 
                void linearRange(int baseSize, int maxSize, int nbPoint) {
                    setBaseSize (baseSize);
                    setMaxSize (maxSize);
                    setIncrement ((maxSize - baseSize) / nbPoint);
                    setGeometric (1.0);
                }
 
                void geometricRange(int baseSize, int maxSize, double base) {
                    setBaseSize (baseSize);
                    setMaxSize (maxSize);
                    setIncrement (0);
                    setGeometric (base);
                    if (base <= 1.0) {
                        std::cerr << "base should be > 1.0\n";
                    }
                }
 
                void setTimeCap(double cap_in_s) {
                    time_cap = cap_in_s;
                }
 
                void run(std::string algoName, void (*runnable)(int*, int)) {
                    std::vector<double> time;
                    std::vector<double> xData;
 
                    //  System.out.println(geoBase);
                    //  System.out.println(increment);
 
                    for (int n = baseSize; n <= maxSize;
                        n = std::max((int)(geoBase * n) + increment, n + 1)) {
 
                        //System.out.println(n);
                        std::vector<int> arr(n);
 
                        generate(&arr[0], n);
 
                        std::chrono::time_point<std::chrono::system_clock> start = std::chrono::system_clock::now();
 
                        runnable(&arr[0], n);
 
                        std::chrono::time_point<std::chrono::system_clock> end = std::chrono::system_clock::now();
 
                        std::chrono::duration<double> elapsed_seconds = end - start;
 
                        if (! check(&arr[0], n)) {
                            std::cerr << "Sorting algorithm " << algoName << " is incorrect\n";
                        }
 
                        time.push_back ((double)elapsed_seconds.count() );
                        xData.push_back ( (double)n );
 
                        if (elapsed_seconds.count() > time_cap) {
                            break;
                        }
                    }
                    plot.setXData(algoName, xData);
                    plot.setYData(algoName, time);
                }
 
        };
    }
}
 
#endif