JMergeSort.cc File Reference

Example program to test performance of JTOOLS::JMergeSort. More...

#include <iostream>
#include <iomanip>
#include <functional>
#include <limits>
#include <vector>
#include <algorithm>
#include "TRandom3.h"
#include "JTools/JMergeSort.hh"
#include "Jeep/JTimer.hh"
#include "Jeep/JParser.hh"
#include "Jeep/JMessage.hh"

Go to the source code of this file.

Classes
struct	JTOOLS::JGetElement< T >
	Auxiliary class to convert value to element. More...

Namespaces
	JTOOLS
	Auxiliary classes and methods for multi-dimensional interpolations and histograms.

Functions
template<class T >
void	JTOOLS::inplace_merge (T __begin, const size_t N, const size_t *delimiter)
	Merge multiple sorted ranges. More...
template<class T >
bool	JTOOLS::is_sorted (T __begin, T __end)
	Test whether range is sorted. More...
int	main (int argc, char **argv)

Detailed Description

Example program to test performance of JTOOLS::JMergeSort.

Author

mdejong

Definition in file JMergeSort.cc.

Function Documentation

int main	(	int	argc,
		char **	argv
	)

Definition at line 126 of file JMergeSort.cc.

{
  using namespace std;

  double         rate_Hz;
  bool           do_test;
  int            debug;

  try {

    JParser<> zap("Example program to test performance of merge sort.");

    zap['B'] = make_field(rate_Hz);
    zap['D'] = make_field(do_test);
    zap['d'] = make_field(debug)               = 0;

    zap(argc, argv);
  }
  catch(const exception &error) {
    FATAL(error.what() << endl);
  }


  using namespace JPP;

  if (rate_Hz <= 0.0) {
    FATAL("Rate " << rate_Hz << " < 0 Hz." << endl);
  }

  const double period = 1.0e9 / rate_Hz;      // [ns]

  const double Tmin   = 0.0;                  // [ns]
  const double Tmax   = 1.0e8;                // [ns]

  const int NUMBER_OF_PMTS    =       31;
  const int NUMBER_OF_MODULES = 115 * 18;


  //typedef int                        hit_type; 
  typedef double                     hit_type; 
  typedef JGetElement<hit_type>      JGetElement_t;
  const   JGetElement_t              getElement;
  typedef std::vector<hit_type>      JBuffer1D;
  typedef std::vector<JBuffer1D>     JBuffer2D;


  // generate random data

  JBuffer2D input(NUMBER_OF_PMTS);

  for (int i = 0; i != NUMBER_OF_PMTS; ++i) {

    for (double t1 = Tmin + gRandom->Exp(period); t1 < Tmax; t1 += gRandom->Exp(period)) {
      input[i].push_back(getElement(t1));
    }

    NOTICE("PMT[" << setw(2) << i << "]  " << input[i].size() << endl);

    input[i].push_back(JGetElement_t::getEndMarker());
  }


  if (true) {

    JTimer timer("std::sort");

    JBuffer1D buffer;

    timer.start();

    for (int i = 0; i != NUMBER_OF_MODULES; ++i) {

      buffer.clear();

      for (int i = 0; i != NUMBER_OF_PMTS; ++i) {
        copy(input[i].begin(), input[i].end() - 1, back_inserter(buffer));
      }

      std::sort(buffer.begin(), buffer.end());

      if (do_test && !JTOOLS::is_sorted(buffer.begin(), buffer.end())) { 
        FATAL("std::sort failed." << endl);
      }
    }

    timer.stop();
    timer.print(cout, false);
  }

  if (true) {

    JTimer timer("std::inplace_merge");

    JBuffer1D buffer;

    vector<size_t> delimiter(NUMBER_OF_PMTS + 1);

    timer.start();

    for (int i = 0; i != NUMBER_OF_MODULES; ++i) {

      size_t n = 0;

      for (int i = 0; i != NUMBER_OF_PMTS; ++i) {
        n += input[i].size() - 1;
      }

      buffer.resize(n);

      JBuffer1D::iterator out = buffer.begin();      

      delimiter[0] = 0;

      for (int i = 0; i != NUMBER_OF_PMTS; ++i) {

        out = copy(input[i].begin(), input[i].end() - 1, out);

        delimiter[i+1] = distance(buffer.begin(), out);
      }

      inplace_merge(buffer.begin(), delimiter.size(), delimiter.data());

      if (do_test && !JTOOLS::is_sorted(buffer.begin(), buffer.end())) {
        FATAL("std::inplace_merge failed." << endl);
      }
    }

    timer.stop();
    timer.print(cout, false);
  }

  if (true) {

    JTimer timer("JMergeSort");

    JBuffer1D            buffer;
    JMergeSort<hit_type> merge;

    timer.start();

    for (int i = 0; i != NUMBER_OF_MODULES; ++i) {

      buffer.clear();
      
      merge(input, buffer);

      if (do_test && !JTOOLS::is_sorted(buffer.begin(), buffer.end())) {
        FATAL("JMergeSort failed." << endl);
      }
    }

    timer.stop();
    timer.print(cout, false);
  }
}