]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | //---------------------------------------------------------------------------- |
2 | /// @file test_sample_sort.cpp | |
3 | /// @brief test sample_sort algorithm | |
4 | /// | |
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 ) | |
9 | /// @version 0.1 | |
10 | /// | |
11 | /// @remarks | |
12 | //----------------------------------------------------------------------------- | |
13 | #include <ciso646> | |
14 | #include <cstdlib> | |
15 | #include <ctime> | |
16 | #include <algorithm> | |
17 | #include <vector> | |
18 | #include <random> | |
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> | |
22 | ||
23 | namespace bss = boost::sort; | |
24 | ||
25 | ||
26 | struct xk | |
27 | { | |
28 | unsigned tail : 4; | |
29 | unsigned num : 28; | |
30 | xk ( uint32_t n =0 , uint32_t t =0): tail (t), num(n){}; | |
31 | bool operator< (xk A) const { return (num < A.num); }; | |
32 | }; | |
33 | void test1() | |
34 | { | |
35 | ||
36 | std::mt19937_64 my_rand(0); | |
37 | ||
38 | const uint32_t NMAX = 100000; | |
39 | ||
40 | std::vector<xk> V1, V2, V3; | |
41 | V1.reserve(NMAX); | |
42 | for (uint32_t i = 0; i < 8; ++i) | |
43 | { | |
44 | for (uint32_t k = 0; k < NMAX; ++k) | |
45 | { uint32_t NM = my_rand(); | |
46 | xk G; | |
47 | G.num = NM >> 3; | |
48 | G.tail = i; | |
49 | V1.push_back(G); | |
50 | }; | |
51 | }; | |
52 | V3 = V2 = V1; | |
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); | |
56 | ||
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); | |
60 | }; | |
61 | ||
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); | |
65 | }; | |
66 | }; | |
67 | ||
68 | void test2(void) | |
69 | { | |
70 | const uint32_t NElem = 2000000; | |
71 | std::vector<uint64_t> V1; | |
72 | ||
73 | // ----------------- sorted elements ------------------------------------ | |
74 | V1.clear(); | |
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]); | |
79 | }; | |
80 | ||
81 | // ------------- reverse sorted elements -------------------------------- | |
82 | V1.clear(); | |
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]); | |
87 | }; | |
88 | ||
89 | // -------------------- equals elements ----------------------------------- | |
90 | V1.clear(); | |
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]); | |
95 | }; | |
96 | }; | |
97 | void test3(void) | |
98 | { | |
99 | const uint32_t NElem = 2000000; | |
100 | std::vector<uint64_t> V1,V2,V3; | |
101 | std::mt19937_64 my_rand(0); | |
102 | ||
103 | for (uint32_t i = 0; i < NElem; ++i) V1.push_back(my_rand() % NElem); | |
104 | V3 = V2 = V1; | |
105 | std::stable_sort (V2.begin(), V2.end()); | |
106 | ||
107 | ||
108 | // --------------- unsorted elements 0 threads ---------------------------- | |
109 | V3 = V1; | |
110 | bss::sample_sort(V3.begin(), V3.end(), 0); | |
111 | for (unsigned i = 0; i < NElem; i++) | |
112 | { BOOST_CHECK(V3[i] == V2[i]); | |
113 | }; | |
114 | ||
115 | // --------------- unsorted elements ------------------------------------- | |
116 | V3 = V1; | |
117 | bss::sample_sort(V3.begin(), V3.end()); | |
118 | for (unsigned i = 0; i < NElem; i++) | |
119 | { BOOST_CHECK(V3[i] == V2[i]); | |
120 | }; | |
121 | ||
122 | // --------------- unsorted elements 100 threads ---------------------------- | |
123 | V3 = V1; | |
124 | bss::sample_sort(V3.begin(), V3.end(), 100); | |
125 | for (unsigned i = 0; i < NElem; i++) | |
126 | { BOOST_CHECK(V3[i] == V2[i]); | |
127 | }; | |
128 | }; | |
129 | ||
130 | void test4(void) | |
131 | { | |
132 | const uint32_t KMax = 66000; | |
133 | ||
134 | std::vector<uint64_t> K, M; | |
135 | std::mt19937_64 my_rand(0); | |
136 | ||
137 | for (uint32_t i = 0; i < KMax; ++i) | |
138 | K.push_back(my_rand()); | |
139 | M = K; | |
140 | ||
141 | bss::sample_sort(K.begin(), K.end(), 300); | |
142 | ||
143 | std::stable_sort(M.begin(), M.end()); | |
144 | for (unsigned i = 0; i < KMax; i++) | |
145 | BOOST_CHECK(M[i] == K[i]); | |
146 | }; | |
147 | ||
148 | void test5 (void) | |
149 | { | |
150 | typedef typename std::vector<xk>::iterator iter_t; | |
151 | std::mt19937 my_rand (0); | |
152 | std::vector<xk> V ; | |
153 | const uint32_t NELEM = 100000; | |
154 | V.reserve(NELEM * 10); | |
155 | ||
156 | ||
157 | for (uint32_t k =0 ; k < 10 ; ++k) | |
158 | { for ( uint32_t i =0 ; i < NELEM ; ++i) | |
159 | { V.emplace_back(i , k); | |
160 | }; | |
161 | iter_t first = V.begin() + (k * NELEM); | |
162 | iter_t last = first + NELEM ; | |
163 | std::shuffle( first, last, my_rand); | |
164 | }; | |
165 | bss::sample_sort( V.begin() , V.end()); | |
166 | for ( uint32_t i =0 ; i < ( NELEM * 10); ++i) | |
167 | { BOOST_CHECK ( V[i].num == (i / 10) and V[i].tail == (i %10) ); | |
168 | }; | |
169 | } | |
170 | ||
171 | ||
172 | int test_main(int, char *[]) | |
173 | { | |
174 | test1(); | |
175 | test2(); | |
176 | test3(); | |
177 | test4(); | |
178 | test5(); | |
179 | return 0; | |
180 | }; |