]>
Commit | Line | Data |
---|---|---|
3a9019d9 FG |
1 | // a sorting example that uses the worst-case distribution for spreadsort.\r |
2 | //\r | |
3 | // Copyright Steven Ross 2009-2014.\r | |
4 | //\r | |
5 | // Distributed under the Boost Software License, Version 1.0.\r | |
6 | // (See accompanying file LICENSE_1_0.txt or copy at\r | |
7 | // http://www.boost.org/LICENSE_1_0.txt)\r | |
8 | \r | |
9 | // See http://www.boost.org/libs/sort for library home page.\r | |
10 | \r | |
11 | #include <boost/sort/spreadsort/spreadsort.hpp>\r | |
12 | #include <time.h>\r | |
13 | #include <stdio.h>\r | |
14 | #include <stdlib.h>\r | |
15 | #include <algorithm>\r | |
16 | #include <vector>\r | |
17 | #include <string>\r | |
18 | #include <fstream>\r | |
19 | #include <sstream>\r | |
20 | #include <iostream>\r | |
21 | using namespace boost::sort::spreadsort;\r | |
22 | using namespace std;\r | |
23 | \r | |
24 | #define DATA_TYPE boost::uint64_t\r | |
25 | \r | |
26 | #define ALR_THRESHOLD 3\r | |
27 | \r | |
28 | const unsigned max_count = ALR_THRESHOLD - 1;\r | |
29 | const unsigned bit_shift = detail::rough_log_2_size(max_count) -\r | |
30 | detail::int_log_mean_bin_size;\r | |
31 | const unsigned radix_threshold = detail::rough_log_2_size(max_count) + 1;\r | |
32 | \r | |
33 | const DATA_TYPE typed_one = 1;\r | |
34 | \r | |
35 | void\r | |
36 | fill_vector(vector<DATA_TYPE> & input, const DATA_TYPE base_value,\r | |
37 | unsigned remaining_bits, const vector<unsigned> & indices,\r | |
38 | int index)\r | |
39 | {\r | |
40 | if (index < 0) {\r | |
41 | for (unsigned u = 0; u < max_count; ++u)\r | |
42 | input.push_back((base_value << remaining_bits) +\r | |
43 | (rand() % (1 << remaining_bits)));\r | |
44 | }\r | |
45 | else {\r | |
46 | unsigned shift = indices[index];\r | |
47 | fill_vector(input, (base_value << shift) + ((1 << shift) - 1),\r | |
48 | remaining_bits - shift, indices, index - 1);\r | |
49 | fill_vector(input, base_value << shift, remaining_bits - shift, indices,\r | |
50 | index - 1);\r | |
51 | }\r | |
52 | }\r | |
53 | \r | |
54 | //Generates a random index from 0 up to but not including count.\r | |
55 | unsigned\r | |
56 | get_index(unsigned count)\r | |
57 | {\r | |
58 | unsigned result = unsigned((rand() % (1 << 16))*uint64_t(count)/(1 << 16));\r | |
59 | if (result >= count)\r | |
60 | return count - 1;\r | |
61 | return result;\r | |
62 | }\r | |
63 | \r | |
64 | //Tests std::sort vs boost::sort::spreadsort on boost::sort's worst distribution.\r | |
65 | int main(int, const char **) {\r | |
66 | unsigned total_length = sizeof(DATA_TYPE) * 8;\r | |
67 | double std_sort_time = 0;\r | |
68 | double spreadsort_time = 0;\r | |
69 | for (int repetition = 0; repetition < 10; ++repetition) {\r | |
70 | vector<DATA_TYPE> input;\r | |
71 | vector<unsigned> offsets;\r | |
72 | unsigned bit_length = total_length - radix_threshold;\r | |
73 | unsigned bit_offset = bit_shift;\r | |
74 | for (; bit_length >= ++bit_offset; bit_length -= bit_offset)\r | |
75 | offsets.push_back(bit_offset);\r | |
76 | for (int ii = (1 << bit_length) - 1; ii >= 0; --ii)\r | |
77 | fill_vector(input, ii, total_length - bit_length,\r | |
78 | offsets, offsets.size() - 1);\r | |
79 | \r | |
80 | //Randomize the inputs slightly so they aren't in reverse-sorted order, for\r | |
81 | //which std::sort is very fast.\r | |
82 | for (unsigned u = 0; u < input.size() / 10; ++u)\r | |
83 | std::swap(input[get_index(input.size())], input[get_index(input.size())]);\r | |
84 | \r | |
85 | //Run both std::sort and boost::sort::spreadsort.\r | |
86 | for (unsigned u = 0; u < 2; ++u) {\r | |
87 | vector<DATA_TYPE> array = input;\r | |
88 | clock_t start, end;\r | |
89 | double elapsed;\r | |
90 | start = clock();\r | |
91 | if (u)\r | |
92 | std::sort(array.begin(), array.end());\r | |
93 | else\r | |
94 | boost::sort::spreadsort::spreadsort(array.begin(), array.end());\r | |
95 | end = clock();\r | |
96 | elapsed = static_cast<double>(end - start);\r | |
97 | if (u)\r | |
98 | std_sort_time += elapsed / CLOCKS_PER_SEC;\r | |
99 | else\r | |
100 | spreadsort_time += elapsed / CLOCKS_PER_SEC;\r | |
101 | array.clear();\r | |
102 | }\r | |
103 | }\r | |
104 | \r | |
105 | printf("std::sort elapsed time %f\n", std_sort_time);\r | |
106 | printf("spreadsort elapsed time %f\n", spreadsort_time);\r | |
107 | return 0;\r | |
108 | }\r |