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