ceph/src/boost/libs/sort/test/test_sample_sort.cpp

   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 };