ceph/src/boost/libs/sort/example/alrbreaker.cpp

   1 // a sorting example that uses the worst-case for conventional MSD radix sorts.
   2 //
   3 //  Copyright Steven Ross 2009-2014.
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8
   9 //  See http://www.boost.org/libs/sort for library home page.
  10
  11 #include <boost/sort/spreadsort/spreadsort.hpp>
  12 #include <time.h>
  13 #include <stdio.h>
  14 #include <stdlib.h>
  15 #include <algorithm>
  16 #include <vector>
  17 #include <string>
  18 #include <fstream>
  19 #include <sstream>
  20 #include <iostream>
  21 using namespace boost::sort::spreadsort;
  22 using namespace std;
  23
  24 #define DATA_TYPE boost::uint64_t
  25
  26 #define ALR_THRESHOLD 3
  27
  28 const unsigned max_count = ALR_THRESHOLD - 1;
  29 const unsigned bit_shift = detail::rough_log_2_size(max_count) -
  30   detail::int_log_mean_bin_size;
  31 const unsigned radix_threshold = detail::rough_log_2_size(max_count) + 1;
  32 //Increase this size if too fast to test accurately
  33 const unsigned top_splits = 12;
  34
  35 const DATA_TYPE typed_one = 1;
  36
  37 void
  38 fill_vector(vector<DATA_TYPE> & input, const DATA_TYPE base_value,
  39             unsigned remaining_bits)
  40 {
  41   if (remaining_bits >= radix_threshold) {
  42     input.push_back((base_value << remaining_bits) +
  43                     ((typed_one << remaining_bits) - 1));
  44     fill_vector(input, base_value << bit_shift, remaining_bits - bit_shift);
  45   }
  46   else {
  47     for (unsigned u = 0; u < max_count; ++u)
  48       input.push_back((base_value << remaining_bits) +
  49                       (rand() % (1 << remaining_bits)));
  50   }
  51 }
  52
  53 //Tests spreadsort on the worst-case distribution for standard MSD radix sorts.
  54 int main(int, const char **) {
  55   vector<DATA_TYPE> input;
  56   for (int ii = (1 << top_splits) - 1; ii >= 0; --ii)
  57     fill_vector(input, ii, (sizeof(DATA_TYPE) * 8) - top_splits);
  58
  59   //Run both std::sort and spreadsort
  60   for (unsigned u = 0; u < 2; ++u) {
  61     vector<DATA_TYPE> array = input;
  62     clock_t start, end;
  63     double elapsed;
  64     start = clock();
  65     if (u)
  66       std::sort(array.begin(), array.end());
  67     else
  68       boost::sort::spreadsort::spreadsort(array.begin(), array.end());
  69     end = clock();
  70     elapsed = static_cast<double>(end - start);
  71     if (u)
  72       printf("std::sort elapsed time %f\n", elapsed / CLOCKS_PER_SEC);
  73     else
  74       printf("spreadsort elapsed time %f\n", elapsed / CLOCKS_PER_SEC);
  75     array.clear();
  76   }
  77   return 0;
  78 }