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
fill_vector(vector<DATA_TYPE> & input,const DATA_TYPE base_value,unsigned remaining_bits)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.
main(int,const char **)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 }
79