buckettest.cpp

Go to the documentation of this file.

#include <cassert>
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

#include <aclock.h>
#include <bucket.h>
#include <buckethybrid.h>
#include <buckettest.h>
#include <print.h>
#include <random.h>
#include <unitdouble.h>

string buckettest::doc[] = 
{
  "",
  "Use bucket: sorting a array of doubles in range [0.0,1.0).",
  "Testing the buckets sorting time of doubles in the range [0.0,1.0) tested in progressive powers of two.",
  "Test the hybrid bucket sort time of doubles in the range [0.0,1.0) tested in progressive powers of two.",
  "Test hybrid bucket sort with bad data."

};

void buckettest::fill(double * data, uintc n)
{
  random10<double> r;

  for (uint i=0; i<n; ++i)
    data[i] = r();
}

void buckettest::test01()
{
  cout << "Testing Bucket Sort" << endl << endl;

  uintc n(10);

  vector<double> v(n);
  fill(&v[0],n);

  cout << "Vector of random values" << endl;
  cout << print(v,"\n"); 
  cout << endl << endl;



  cout << "Sorting" << endl;
  unitdouble f1(2*n);
  bucket<double,unitdouble> b(&v[0],n,f1);
  b.eval();

  vector<double> v2(n);
  b.copy(&v2[0]);

  cout << print(v2) << endl;

}

boolc buckettest::verifyequalvectors
(
  vector<double> & v1,
  vector<double> const & v2
)
{
  sort(v1.begin(),v1.end());
  if (v1.size()!=v2.size())
    return false;

  uint sz = v1.size();
  for (uint i=0; i<sz; ++i)
    if (v1[i]!=v2[i])
      return false;

  return true;
}

void buckettest::createandtest(uintc n)
{
  vector<double> v(n);
  fill(&v[0],n);
  cout << n << " ";

  unitdouble f1(n);
  bucket<double,unitdouble> b(&v[0],n,f1);

  aclock c;
  c.measure();
  b.eval();
  c.measure();
  cout << c.diff_s() << endl;

  vector<double> v2(n);
  b.copy(&v2[0]);

  assert(verifyequalvectors(v,v2));
}

void buckettest::test02()
{
  cout << "Testing Bucket Sort" << endl << endl;

  cout << "Testing Sorting Time" << endl;

  uint u=10000;
  for (uint k=0; k<10; ++k)
  {
    createandtest(u);
    u *= 2;
  }
}

void buckettest::createandtest2(uintc n, uintc chainmax )
{
  vector<double> v(n);
  fill(&v[0],n);
  cout << n << " ";
  unitdouble f1(n*2);
  typedef buckethybrid<double,unitdouble, multiset<double> > bhd;
  bhd b(&v[0],n,f1,chainmax);

  aclock c;
  c.measure();
  b.eval();
  c.measure();
  cout << c.diff_s() << endl;

  vector<double> v2(n);
  b.copy(&v2[0]);

  assert(verifyequalvectors(v,v2));
}

// This is the worst situation: all the data is in the one place.
void buckettest::fillbad(double * data, uintc n)
{
  random10<double> r;

  doublec x = r();

  for (uint i=0; i<n; ++i)
    data[i] = x;
}

void buckettest::test03()
{
  cout << "Testing Bucket Hybrid Sort" << endl << endl;
  cout << "Testing Sorting Time" << endl;

  uint u=10000;
  uint blen = 4;
  for (uint k=0; k<9; ++k)
  {
    createandtest2(u,blen);
    u *= 2;
    ++blen;
  }
}

void buckettest::createandtest3(uintc n, uintc chainmax )
{
  vector<double> v(n);
  fillbad(&v[0],n);
  cout << n << " ";
  unitdouble f1(n*2);
  typedef buckethybrid<double,unitdouble, multiset<double> > bhd;
  bhd b(&v[0],n,f1,chainmax);

  aclock c;
  c.measure();
  b.eval();
  c.measure();
  cout << c.diff_s() << endl;

  vector<double> v2(n);
  b.copy(&v2[0]);

  cout << SHOW(v.size()) << endl;
  cout << SHOW(v2.size()) << endl;

  cout << "v=" << print(v) << endl;
  cout << "v2=" << print(v2) << endl;

  assert(verifyequalvectors(v,v2));
}

void buckettest::test04()
{
  cout << "Testing Bucket Hybrid Sort" << endl << endl;
  cout << "Testing Sorting Time" << endl;

  uint u=1000;
  uint blen = 4;
  for (uint k=0; k<1; ++k)
  {
    createandtest3(u,blen);
    u *= 2;
    ++blen;
  }
}