]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/sort/test/test_sample_sort.cpp
1 //----------------------------------------------------------------------------
2 /// @file test_sample_sort.cpp
3 /// @brief test sample_sort algorithm
5 /// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
6 /// Distributed under the Boost Software License, Version 1.0.\n
7 /// ( See accompanying file LICENSE_1_0.txt or copy at
8 /// http://www.boost.org/LICENSE_1_0.txt )
12 //-----------------------------------------------------------------------------
19 #include <boost/sort/sample_sort/sample_sort.hpp>
20 #include <boost/test/included/test_exec_monitor.hpp>
21 #include <boost/test/test_tools.hpp>
23 namespace bss
= boost::sort
;
30 xk ( uint32_t n
=0 , uint32_t t
=0): tail (t
), num(n
){};
31 bool operator< (xk A
) const { return (num
< A
.num
); };
36 std::mt19937_64
my_rand(0);
38 const uint32_t NMAX
= 100000;
40 std::vector
<xk
> V1
, V2
, V3
;
42 for (uint32_t i
= 0; i
< 8; ++i
)
44 for (uint32_t k
= 0; k
< NMAX
; ++k
)
45 { uint32_t NM
= my_rand();
53 bss::sample_sort(V1
.begin(), V1
.end());
54 std::stable_sort(V2
.begin(), V2
.end());
55 bss::sample_sort(V3
.begin(), V3
.end(), 0);
57 BOOST_CHECK(V1
.size() == V2
.size());
58 for (uint32_t i
= 0; i
< V1
.size(); ++i
)
59 { BOOST_CHECK(V1
[i
].num
== V2
[i
].num
and V1
[i
].tail
== V2
[i
].tail
);
62 BOOST_CHECK(V3
.size() == V2
.size());
63 for (uint32_t i
= 0; i
< V3
.size(); ++i
)
64 { BOOST_CHECK(V3
[i
].num
== V2
[i
].num
and V3
[i
].tail
== V2
[i
].tail
);
70 const uint32_t NElem
= 2000000;
71 std::vector
<uint64_t> V1
;
73 // ----------------- sorted elements ------------------------------------
75 for (uint32_t i
= 0; i
< NElem
; ++i
) V1
.push_back(i
);
76 bss::sample_sort(V1
.begin(), V1
.end());
77 for (unsigned i
= 1; i
< NElem
; i
++)
78 { BOOST_CHECK(V1
[i
- 1] <= V1
[i
]);
81 // ------------- reverse sorted elements --------------------------------
83 for (uint32_t i
= 0; i
< NElem
; ++i
) V1
.push_back(NElem
- i
);
84 bss::sample_sort(V1
.begin(), V1
.end());
85 for (unsigned i
= 1; i
< NElem
; i
++)
86 { BOOST_CHECK(V1
[i
- 1] <= V1
[i
]);
89 // -------------------- equals elements -----------------------------------
91 for (uint32_t i
= 0; i
< NElem
; ++i
) V1
.push_back(1000);
92 bss::sample_sort(V1
.begin(), V1
.end());
93 for (unsigned i
= 1; i
< NElem
; i
++)
94 { BOOST_CHECK(V1
[i
- 1] == V1
[i
]);
99 typedef std::less
<uint64_t> compare
;
100 const uint32_t NElem
= 2000000;
101 std::vector
<uint64_t> V1
,V2
,V3
;
102 std::mt19937_64
my_rand(0);
104 for (uint32_t i
= 0; i
< NElem
; ++i
) V1
.push_back(my_rand() % NElem
);
106 std::stable_sort (V2
.begin(), V2
.end());
109 // --------------- unsorted elements 0 threads ----------------------------
111 bss::sample_sort(V3
.begin(), V3
.end(), compare(), 0);
112 for (unsigned i
= 0; i
< NElem
; i
++)
113 { BOOST_CHECK(V3
[i
] == V2
[i
]);
116 // --------------- unsorted elements -------------------------------------
118 bss::sample_sort(V3
.begin(), V3
.end(), compare());
119 for (unsigned i
= 0; i
< NElem
; i
++)
120 { BOOST_CHECK(V3
[i
] == V2
[i
]);
123 // --------------- unsorted elements 100 threads ----------------------------
125 bss::sample_sort(V3
.begin(), V3
.end(), compare(), 100);
126 for (unsigned i
= 0; i
< NElem
; i
++)
127 { BOOST_CHECK(V3
[i
] == V2
[i
]);
133 const uint32_t KMax
= 66000;
135 std::vector
<uint64_t> K
, M
;
136 std::mt19937_64
my_rand(0);
138 for (uint32_t i
= 0; i
< KMax
; ++i
)
139 K
.push_back(my_rand());
142 bss::sample_sort(K
.begin(), K
.end(), 300);
144 std::stable_sort(M
.begin(), M
.end());
145 for (unsigned i
= 0; i
< KMax
; i
++)
146 BOOST_CHECK(M
[i
] == K
[i
]);
151 typedef typename
std::vector
<xk
>::iterator iter_t
;
152 std::mt19937
my_rand (0);
154 const uint32_t NELEM
= 100000;
155 V
.reserve(NELEM
* 10);
158 for (uint32_t k
=0 ; k
< 10 ; ++k
)
159 { for ( uint32_t i
=0 ; i
< NELEM
; ++i
)
160 { V
.emplace_back(i
, k
);
162 iter_t first
= V
.begin() + (k
* NELEM
);
163 iter_t last
= first
+ NELEM
;
164 std::shuffle( first
, last
, my_rand
);
166 bss::sample_sort( V
.begin() , V
.end());
167 for ( uint32_t i
=0 ; i
< ( NELEM
* 10); ++i
)
168 { BOOST_CHECK ( V
[i
].num
== (i
/ 10) and V
[i
].tail
== (i
%10) );
173 int test_main(int, char *[])