]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/sort/example/binaryalrbreaker.cpp
1 // a sorting example that uses the worst-case distribution for spreadsort.
3 // Copyright Steven Ross 2009-2014.
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)
9 // See http://www.boost.org/libs/sort for library home page.
11 #include <boost/sort/spreadsort/spreadsort.hpp>
21 using namespace boost::sort::spreadsort
;
24 #define DATA_TYPE boost::uint64_t
26 #define ALR_THRESHOLD 3
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;
33 const DATA_TYPE typed_one
= 1;
36 fill_vector(vector
<DATA_TYPE
> & input
, const DATA_TYPE base_value
,
37 unsigned remaining_bits
, const vector
<unsigned> & indices
,
41 for (unsigned u
= 0; u
< max_count
; ++u
)
42 input
.push_back((base_value
<< remaining_bits
) +
43 (rand() % (1 << remaining_bits
)));
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
,
54 //Generates a random index from 0 up to but not including count.
56 get_index(unsigned count
)
58 unsigned result
= unsigned((rand() % (1 << 16))*uint64_t(count
)/(1 << 16));
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);
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())]);
85 //Run both std::sort and boost::sort::spreadsort.
86 for (unsigned u
= 0; u
< 2; ++u
) {
87 vector
<DATA_TYPE
> array
= input
;
92 std::sort(array
.begin(), array
.end());
94 boost::sort::spreadsort::spreadsort(array
.begin(), array
.end());
96 elapsed
= static_cast<double>(end
- start
);
98 std_sort_time
+= elapsed
/ CLOCKS_PER_SEC
;
100 spreadsort_time
+= elapsed
/ CLOCKS_PER_SEC
;
105 printf("std::sort elapsed time %f\n", std_sort_time
);
106 printf("spreadsort elapsed time %f\n", spreadsort_time
);