sort.cpp

Go to the documentation of this file.

#include "catch.hpp"
 
#include "kblib/sort.h"
 
#include "kblib/stats.h"
#include "kblib/stringops.h"
#include <iomanip>
#include <iostream>
#include <map>
 
template <typename T, std::size_t N>
constexpr auto sort_test(kblib::trivial_array<T, N> val) noexcept -> bool {
   kblib::trivial_array<T, N> out{};
   kblib::insertion_sort_copy(val.begin(), val.end(), out.begin(), out.end());
   kblib::insertion_sort(val.begin(), val.end());
   return true;
}
 
TEST_CASE("sort") {
   constexpr kblib::trivial_array<int, 7> input{{3, 7, 4, 3, 1, 9, 5}};
   const auto goal = [&] {
      auto copy = input;
      std::sort(copy.begin(), copy.end());
      return copy;
   }();
 
   KBLIB_UNUSED auto print_arr = [&](auto c) {
      for (const auto& v : c) {
         std::cout << v << ", ";
      }
      std::cout << '\n';
   };
 
#if KBLIB_USE_CXX17
   static_assert(sort_test(input), "insertion_sort should be constexpr");
#endif
 
   SECTION("insertion_sort") {
      auto input_copy = input;
      kblib::insertion_sort(input_copy.begin(), input_copy.end());
      CHECK(input_copy == goal);
      static_assert(
          noexcept(kblib::insertion_sort(input_copy.begin(), input_copy.end())),
          "insertion_sort for array<int> should be noexcept");
   }
   SECTION("insertion_sort_copy") {
      std::remove_const<decltype(input)>::type output;
      kblib::insertion_sort_copy(input.begin(), input.end(), output.begin(),
                                 output.end());
      CHECK(output == goal);
      static_assert(
          noexcept(kblib::insertion_sort_copy(input.begin(), input.end(),
                                              output.begin(), output.end())),
          "insertion_sort_copy for array<int> should be noexcept");
   }
   SECTION("adaptive_insertion_sort_copy") {
      std::remove_const<decltype(input)>::type output;
      kblib::adaptive_insertion_sort_copy(input.begin(), input.end(),
                                          output.begin(), output.end());
      CHECK(output == goal);
   }
   SECTION("insertion_sort is stable") {
      std::minstd_rand rng{std::random_device{}()};
      std::uniform_int_distribution<int> dist(0, 8);
      for ([[gnu::unused]] auto _i : kblib::range(100)) {
         // sort based on first key, second is used to distinguish between equal
         // elements
         std::vector<std::pair<int, int>> inputs;
         auto pcomp = [](auto a, auto b) { return a.first < b.first; };
 
         {
            std::map<int, int> counts;
            for ([[gnu::unused]] auto _j : kblib::range(100)) {
               auto r = dist(rng);
               inputs.emplace_back(r, counts[r]++);
            }
         }
 
         kblib::insertion_sort(inputs.begin(), inputs.end(), pcomp);
 
         {
            std::map<int, int> counts;
            for (auto p : inputs) {
               CHECK(p.second == counts[p.first]++);
            }
         }
      }
   }
   SECTION("insertion_sort on random data") {
      std::minstd_rand rng{std::random_device{}()};
      std::uniform_int_distribution<int> dist(0, 65535);
      for ([[gnu::unused]] auto _i : kblib::range(100)) {
         std::vector<int> input2(100);
         std::generate(begin(input2), end(input2), [&] { return dist(rng); });
 
         auto output_std = input2;
         std::sort(output_std.begin(), output_std.end());
         decltype(input2) output_kblib(input2.size());
         kblib::insertion_sort_copy(cbegin(input2), cend(input2),
                                    output_kblib.begin(), output_kblib.end());
         CHECK(output_std == output_kblib);
      }
   }
}
 
static std::ostream& log_location = std::cout;
 
auto linear(std::size_t i) { return static_cast<double>(i); }
 
TEST_CASE("insertion sort performance") {
   auto time_and_log
       = [&](auto line, auto&& f, std::size_t quick = 30,
             std::size_t slow = 10000, double (*O)(std::size_t) = linear) {
            auto time_fast = f(quick) / O(quick);
            auto time_slow = f(slow) / O(slow);
            auto error = time_slow / time_fast;
            log_location << __FILE__ ":" << std::left << line << ": \t"
                         << time_fast << "\t " << std::setw(12) << time_slow
                         << '\t' << std::setw(14) << error << '\t'
                         << time_slow * 10000 << '\t' << time_fast * 30 << "\n";
 
            // Can't overshoot the bound by more than 5%:
            CHECK(error < 1.05);
         };
#define TIME(...) time_and_log(__LINE__, __VA_ARGS__)
 
   SECTION("labels") {
      using namespace std::literals;
      log_location << __FILE__ ":" << std::left << __LINE__
                   << ": \t/el (30)\t /el (10000)"
                      "\tsuperlinearity\ttotal (10000)\t"
                      "total (30)\n"
                   << kblib::repeat(" -"s, 60) << '\n';
   }
 
   SECTION("insertion_sort_copy on sorted data is fast") {
      auto time_per = [](std::size_t size) {
         std::vector<int> input(size);
         decltype(input) output(size);
         std::iota(input.begin(), input.end(), 0);
 
         auto start = std::chrono::high_resolution_clock::now();
         kblib::insertion_sort_copy(input.cbegin(), input.cend(),
                                    output.begin(), output.end());
         auto end = std::chrono::high_resolution_clock::now();
         auto duration = end - start;
         return static_cast<double>(duration.count());
      };
 
      TIME(time_per);
   }
   SECTION("insertion_sort_copy on reverse sorted data is slow") {
      auto time_per = [](std::size_t size) {
         std::vector<int> input(size);
         decltype(input) output(size);
         std::iota(input.rbegin(), input.rend(), 0);
 
         auto start = std::chrono::high_resolution_clock::now();
         kblib::insertion_sort_copy(input.cbegin(), input.cend(),
                                    output.begin(), output.end());
         auto end = std::chrono::high_resolution_clock::now();
         auto duration = end - start;
         return static_cast<double>(duration.count());
      };
 
      TIME(
          time_per, 30, 1000, +[](std::size_t i) {
             return static_cast<double>(i) * static_cast<double>(i);
          });
   }
   SECTION("adaptive_insertion_sort_copy on sorted data is fast") {
      auto time_per = [](std::size_t size) {
         std::vector<int> input(size);
         decltype(input) output(size);
         std::iota(input.begin(), input.end(), 0);
 
         auto start = std::chrono::high_resolution_clock::now();
         kblib::adaptive_insertion_sort_copy(input.cbegin(), input.cend(),
                                             output.begin(), output.end());
         auto end = std::chrono::high_resolution_clock::now();
         auto duration = end - start;
         return static_cast<double>(duration.count());
      };
 
      TIME(time_per);
   }
   SECTION("adaptive_insertion_sort_copy on reverse sorted data is fast") {
      auto time_per = [](std::size_t size) {
         std::vector<int> input(size);
         decltype(input) output(size);
         std::iota(input.rbegin(), input.rend(), 0);
 
         auto start = std::chrono::high_resolution_clock::now();
         kblib::adaptive_insertion_sort_copy(input.cbegin(), input.cend(),
                                             output.begin(), output.end());
         auto end = std::chrono::high_resolution_clock::now();
         auto duration = end - start;
         return static_cast<double>(duration.count());
      };
 
      TIME(time_per);
   }
   SECTION("insertion_sort_copy on mostly sorted data is fast") {
      std::minstd_rand rng{std::random_device{}()};
      auto time_per = [&](int ssize, int noise) {
         auto size = static_cast<std::size_t>(ssize);
         std::uniform_int_distribution<int> dist(-noise, noise);
         std::vector<int> input(size);
         decltype(input) output(size);
         for (auto i : kblib::range(ssize)) {
            input[kblib::to_unsigned(i)] = i + dist(rng);
         }
 
         auto start = std::chrono::high_resolution_clock::now();
         kblib::insertion_sort_copy(input.cbegin(), input.cend(),
                                    output.begin(), output.end());
         auto end = std::chrono::high_resolution_clock::now();
         auto duration = end - start;
         return static_cast<double>(duration.count());
      };
 
      auto n = 10000;
      // deviation by +/- sqrt(n)
      auto v = 100;
 
      using namespace std::literals;
      log_location << kblib::repeat(" -"s, 60) << '\n'
                   << __FILE__ ":" << std::left << __LINE__
                   << ": \t/el (s) \t /el (v)    "
                      "\tsuperlinearity\ttotal (v)    \t"
                      "total (s)\n"
                   << kblib::repeat(" -"s, 60) << '\n';
 
      auto time_fast = time_per(n, 0) / n;
      auto time_slow = time_per(n, v) / n;
      auto ratio = time_slow / time_fast;
      auto error = ratio / (n / v);
 
      log_location << __FILE__ ":" << std::left << __LINE__ << ": \t"
                   << time_fast << "\t " << std::setw(12) << time_slow << '\t'
                   << std::setw(14) << error << '\t' << time_slow * 10000
                   << '\t' << time_fast * 30 << "\n";
 
      // Can't overshoot the bound by more than 5%:
      CHECK(error < 1.05);
   }
   log_location << std::flush;
#undef TIME
}
 
TEST_CASE("byte extraction") {
   constexpr std::uint32_t x{0xAB23CD67};
 
   static_assert(std::numeric_limits<std::uint32_t>::digits
                     == sizeof(uint32_t) * CHAR_BIT,
                 "these checks assume uint32_t does not have padding.");
   static_assert(CHAR_BIT == 8, "these checks assume 8-bit bytes");
 
   static_assert(kblib::byte_count(x) == sizeof(x), "");
   static_assert(+kblib::get_byte_index(x, 0) == 0x67, "");
   static_assert(+kblib::get_byte_index(x, 1) == 0xCD, "");
   static_assert(+kblib::get_byte_index(x, 2) == 0x23, "");
   static_assert(+kblib::get_byte_index(x, 3) == 0xAB, "");
 
   std::string str{"0123456789"};
   CHECK(kblib::byte_count(str) == str.length());
   for (auto i : kblib::range(str.length())) {
      CHECK((kblib::get_byte_index(str, i)) == str[i]);
   }
 
   constexpr std::array<std::int32_t, 2> arr{0x10325476,
                                             std::int32_t(0x98BADCFE)};
   static_assert(kblib::byte_count(arr) == 8, "");
   static_assert(+kblib::get_byte_index(arr, 0) == 0x76, "");
   static_assert(+kblib::get_byte_index(arr, 1) == 0x54, "");
   static_assert(+kblib::get_byte_index(arr, 2) == 0x32, "");
   static_assert(+kblib::get_byte_index(arr, 3) == 0x10, "");
   static_assert(+kblib::get_byte_index(arr, 4) == 0xFE, "");
   static_assert(+kblib::get_byte_index(arr, 5) == 0xDC, "");
   static_assert(+kblib::get_byte_index(arr, 6) == 0xBA, "");
   static_assert(+kblib::get_byte_index(arr, 7) == 0x98, "");
}