]>
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 | { | |
92f5a8d4 | 99 | typedef std::less<uint64_t> compare; |
11fdf7f2 TL |
100 | const uint32_t NElem = 2000000; |
101 | std::vector<uint64_t> V1,V2,V3; | |
102 | std::mt19937_64 my_rand(0); | |
103 | ||
104 | for (uint32_t i = 0; i < NElem; ++i) V1.push_back(my_rand() % NElem); | |
105 | V3 = V2 = V1; | |
106 | std::stable_sort (V2.begin(), V2.end()); | |
107 | ||
108 | ||
109 | // --------------- unsorted elements 0 threads ---------------------------- | |
110 | V3 = V1; | |
92f5a8d4 | 111 | bss::sample_sort(V3.begin(), V3.end(), compare(), 0); |
11fdf7f2 TL |
112 | for (unsigned i = 0; i < NElem; i++) |
113 | { BOOST_CHECK(V3[i] == V2[i]); | |
114 | }; | |
115 | ||
116 | // --------------- unsorted elements ------------------------------------- | |
117 | V3 = V1; | |
92f5a8d4 | 118 | bss::sample_sort(V3.begin(), V3.end(), compare()); |
11fdf7f2 TL |
119 | for (unsigned i = 0; i < NElem; i++) |
120 | { BOOST_CHECK(V3[i] == V2[i]); | |
121 | }; | |
122 | ||
123 | // --------------- unsorted elements 100 threads ---------------------------- | |
124 | V3 = V1; | |
92f5a8d4 | 125 | bss::sample_sort(V3.begin(), V3.end(), compare(), 100); |
11fdf7f2 TL |
126 | for (unsigned i = 0; i < NElem; i++) |
127 | { BOOST_CHECK(V3[i] == V2[i]); | |
128 | }; | |
129 | }; | |
130 | ||
131 | void test4(void) | |
132 | { | |
133 | const uint32_t KMax = 66000; | |
134 | ||
135 | std::vector<uint64_t> K, M; | |
136 | std::mt19937_64 my_rand(0); | |
137 | ||
138 | for (uint32_t i = 0; i < KMax; ++i) | |
139 | K.push_back(my_rand()); | |
140 | M = K; | |
141 | ||
142 | bss::sample_sort(K.begin(), K.end(), 300); | |
143 | ||
144 | std::stable_sort(M.begin(), M.end()); | |
145 | for (unsigned i = 0; i < KMax; i++) | |
146 | BOOST_CHECK(M[i] == K[i]); | |
147 | }; | |
148 | ||
149 | void test5 (void) | |
150 | { | |
151 | typedef typename std::vector<xk>::iterator iter_t; | |
152 | std::mt19937 my_rand (0); | |
153 | std::vector<xk> V ; | |
154 | const uint32_t NELEM = 100000; | |
155 | V.reserve(NELEM * 10); | |
156 | ||
157 | ||
158 | for (uint32_t k =0 ; k < 10 ; ++k) | |
159 | { for ( uint32_t i =0 ; i < NELEM ; ++i) | |
160 | { V.emplace_back(i , k); | |
161 | }; | |
162 | iter_t first = V.begin() + (k * NELEM); | |
163 | iter_t last = first + NELEM ; | |
164 | std::shuffle( first, last, my_rand); | |
165 | }; | |
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) ); | |
169 | }; | |
170 | } | |
171 | ||
172 | ||
173 | int test_main(int, char *[]) | |
174 | { | |
175 | test1(); | |
176 | test2(); | |
177 | test3(); | |
178 | test4(); | |
179 | test5(); | |
180 | return 0; | |
181 | }; |