]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // a sorting example that uses the worst-case distribution for spreadsort. |
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 | ||
33 | const DATA_TYPE typed_one = 1; | |
34 | ||
35 | void | |
36 | fill_vector(vector<DATA_TYPE> & input, const DATA_TYPE base_value, | |
37 | unsigned remaining_bits, const vector<unsigned> & indices, | |
38 | int index) | |
39 | { | |
40 | if (index < 0) { | |
41 | for (unsigned u = 0; u < max_count; ++u) | |
42 | input.push_back((base_value << remaining_bits) + | |
43 | (rand() % (1 << remaining_bits))); | |
44 | } | |
45 | else { | |
46 | unsigned shift = indices[index]; | |
47 | fill_vector(input, (base_value << shift) + ((1 << shift) - 1), | |
48 | remaining_bits - shift, indices, index - 1); | |
49 | fill_vector(input, base_value << shift, remaining_bits - shift, indices, | |
50 | index - 1); | |
51 | } | |
52 | } | |
53 | ||
54 | //Generates a random index from 0 up to but not including count. | |
55 | unsigned | |
56 | get_index(unsigned count) | |
57 | { | |
58 | unsigned result = unsigned((rand() % (1 << 16))*uint64_t(count)/(1 << 16)); | |
59 | if (result >= count) | |
60 | return count - 1; | |
61 | return result; | |
62 | } | |
63 | ||
64 | //Tests std::sort vs boost::sort::spreadsort on boost::sort's worst distribution. | |
65 | int main(int, const char **) { | |
66 | unsigned total_length = sizeof(DATA_TYPE) * 8; | |
67 | double std_sort_time = 0; | |
68 | double spreadsort_time = 0; | |
69 | for (int repetition = 0; repetition < 10; ++repetition) { | |
70 | vector<DATA_TYPE> input; | |
71 | vector<unsigned> offsets; | |
72 | unsigned bit_length = total_length - radix_threshold; | |
73 | unsigned bit_offset = bit_shift; | |
74 | for (; bit_length >= ++bit_offset; bit_length -= bit_offset) | |
75 | offsets.push_back(bit_offset); | |
76 | for (int ii = (1 << bit_length) - 1; ii >= 0; --ii) | |
77 | fill_vector(input, ii, total_length - bit_length, | |
78 | offsets, offsets.size() - 1); | |
79 | ||
80 | //Randomize the inputs slightly so they aren't in reverse-sorted order, for | |
81 | //which std::sort is very fast. | |
82 | for (unsigned u = 0; u < input.size() / 10; ++u) | |
83 | std::swap(input[get_index(input.size())], input[get_index(input.size())]); | |
84 | ||
85 | //Run both std::sort and boost::sort::spreadsort. | |
86 | for (unsigned u = 0; u < 2; ++u) { | |
87 | vector<DATA_TYPE> array = input; | |
88 | clock_t start, end; | |
89 | double elapsed; | |
90 | start = clock(); | |
91 | if (u) | |
92 | std::sort(array.begin(), array.end()); | |
93 | else | |
94 | boost::sort::spreadsort::spreadsort(array.begin(), array.end()); | |
95 | end = clock(); | |
96 | elapsed = static_cast<double>(end - start); | |
97 | if (u) | |
98 | std_sort_time += elapsed / CLOCKS_PER_SEC; | |
99 | else | |
100 | spreadsort_time += elapsed / CLOCKS_PER_SEC; | |
101 | array.clear(); | |
102 | } | |
103 | } | |
104 | ||
105 | printf("std::sort elapsed time %f\n", std_sort_time); | |
106 | printf("spreadsort elapsed time %f\n", spreadsort_time); | |
107 | return 0; | |
108 | } |