1 //----------------------------------------------------------------------------
2 /// @file test_parallel_stable_sort.cpp
3 /// @brief test program of the parallel_stable_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 <cstdio>
15 #include <cstdlib>
16 #include <ctime>
17 #include <vector>
18 #include <random>
19 #include <algorithm>
20 #include <boost/sort/parallel_stable_sort/parallel_stable_sort.hpp>
21 #include <boost/test/included/test_exec_monitor.hpp>
22 #include <boost/test/test_tools.hpp>
23
24 namespace bss = boost::sort;
25
26
27 struct xk
28 {
29 unsigned tail : 4;
30 unsigned num : 28;
xkxk31 xk ( uint32_t n =0 , uint32_t t =0): tail (t), num(n){};
operator <xk32 bool operator< (xk A) const { return (num < A.num); };
33 };
test1()34 void test1()
35 {
36
37 std::mt19937_64 my_rand(0);
38
39 const uint32_t NMAX = 100000;
40
41 std::vector<xk> V1, V2, V3;
42 V1.reserve(NMAX);
43 for (uint32_t i = 0; i < 8; ++i)
44 {
45 for (uint32_t k = 0; k < NMAX; ++k)
46 { uint32_t NM = my_rand();
47 xk G;
48 G.num = NM >> 3;
49 G.tail = i;
50 V1.push_back(G);
51 };
52 };
53 V3 = V2 = V1;
54 bss::parallel_stable_sort(V1.begin(), V1.end());
55 std::stable_sort(V2.begin(), V2.end());
56 bss::parallel_stable_sort(V3.begin(), V3.end(), 0);
57
58 BOOST_CHECK(V1.size() == V2.size());
59 for (uint32_t i = 0; i < V1.size(); ++i)
60 { BOOST_CHECK(V1[i].num == V2[i].num and V1[i].tail == V2[i].tail);
61 };
62
63 BOOST_CHECK(V3.size() == V2.size());
64 for (uint32_t i = 0; i < V3.size(); ++i)
65 { BOOST_CHECK(V3[i].num == V2[i].num and V3[i].tail == V2[i].tail);
66 };
67 };
68
test2(void)69 void test2(void)
70 {
71 const uint32_t NElem = 2000000;
72 std::vector<uint64_t> V1;
73
74 // ----------------- sorted elements ------------------------------------
75 V1.clear();
76 for (uint32_t i = 0; i < NElem; ++i) V1.push_back(i);
77 bss::parallel_stable_sort(V1.begin(), V1.end());
78 for (unsigned i = 1; i < NElem; i++)
79 { BOOST_CHECK(V1[i - 1] <= V1[i]);
80 };
81
82 // ------------- reverse sorted elements --------------------------------
83 V1.clear();
84 for (uint32_t i = 0; i < NElem; ++i) V1.push_back(NElem - i);
85 bss::parallel_stable_sort(V1.begin(), V1.end());
86 for (unsigned i = 1; i < NElem; i++)
87 { BOOST_CHECK(V1[i - 1] <= V1[i]);
88 };
89
90 // -------------------- equals elements -----------------------------------
91 V1.clear();
92 for (uint32_t i = 0; i < NElem; ++i) V1.push_back(1000);
93 bss::parallel_stable_sort(V1.begin(), V1.end());
94 for (unsigned i = 1; i < NElem; i++)
95 { BOOST_CHECK(V1[i - 1] == V1[i]);
96 };
97 };
test3(void)98 void test3(void)
99 {
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;
111 bss::parallel_stable_sort(V3.begin(), V3.end(), 0);
112 for (unsigned i = 0; i < NElem; i++)
113 { BOOST_CHECK(V3[i] == V2[i]);
114 };
115
116 // --------------- unsorted elements -------------------------------------
117 V3 = V1;
118 bss::parallel_stable_sort(V3.begin(), V3.end());
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;
125 bss::parallel_stable_sort(V3.begin(), V3.end(), 100);
126 for (unsigned i = 0; i < NElem; i++)
127 { BOOST_CHECK(V3[i] == V2[i]);
128 };
129 };
130
test4(void)131 void test4(void)
132 {
133 typedef std::less<uint64_t> compare;
134 const uint32_t KMax = 66000;
135
136 std::vector<uint64_t> K, M;
137 std::mt19937_64 my_rand(0);
138
139 for (uint32_t i = 0; i < KMax; ++i)
140 K.push_back(my_rand());
141 M = K;
142
143 bss::parallel_stable_sort(K.begin(), K.end(), compare(), 300);
144
145 std::stable_sort(M.begin(), M.end(), compare());
146 for (unsigned i = 0; i < KMax; i++)
147 BOOST_CHECK(M[i] == K[i]);
148 };
149
test5(void)150 void test5 (void)
151 {
152 typedef typename std::vector<xk>::iterator iter_t;
153 std::mt19937 my_rand (0);
154 std::vector<xk> V ;
155 const uint32_t NELEM = 100000;
156 V.reserve(NELEM * 10);
157
158
159 for (uint32_t k =0 ; k < 10 ; ++k)
160 { for ( uint32_t i =0 ; i < NELEM ; ++i)
161 { V.emplace_back(i , k);
162 };
163 iter_t first = V.begin() + (k * NELEM);
164 iter_t last = first + NELEM ;
165 std::shuffle( first, last, my_rand);
166 };
167 bss::parallel_stable_sort( V.begin() , V.end());
168 for ( uint32_t i =0 ; i < ( NELEM * 10); ++i)
169 { BOOST_CHECK ( V[i].num == (i / 10) and V[i].tail == (i %10) );
170 };
171 }
172
173
test_main(int,char * [])174 int test_main(int, char *[])
175 {
176 test1();
177 test2();
178 test3();
179 test4();
180 test5();
181 return 0;
182 };
183
184