ベタ書きすまぬ

main.cc

#include <algorithm>
#include <iostream>
#include <sstream>
#include <random>
#include "radix_sort.hpp"

#include <chrono>


std::chrono::milliseconds time_evaluate(std::function<void(void)> f) {
  std::this_thread::sleep_for(std::chrono::seconds(1));
  auto start = std::chrono::system_clock::now();
  f();
  auto end = std::chrono::system_clock::now();
  return std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
}

void init_vector(std::vector<uint64_t>& target, size_t nworkers) {
  auto init_time = time_evaluate([=, &target]() {
    std::vector<std::thread> workers;
    for (size_t i = 0; i < nworkers; ++i) {
      workers.emplace_back([=, &target]() {
        std::random_device rd;
        std::mt19937 mt((unsigned int) rd());
        for (size_t j = i * target.size() / nworkers;
             j < (i + 1) * target.size() / nworkers;
             ++j) {
          target[j] = mt();
        }
      });
    }
    for (size_t i = 0; i < nworkers; ++i) {
      workers[i].join();
    }
  });
  std::cout << "initializing time: " << init_time.count()
      << " msec. with " << nworkers << " threads" << std::endl;
}

bool check_sorted(const std::vector<uint64_t>& t) {
  uint64_t now_min = 0;
  for (auto i = t.begin(); i != t.end(); ++i) {
    if (*i < now_min) {
      std::cerr << "array is not sorted!!" << std::endl;
      for (auto data : t) {
        std::cerr << data << std::endl;
      }
      break;
    } else {
      now_min = *i;
    }
  }
}

int main() {
  size_t size = 50000;
  size_t nworkers = 4;
  std::vector<uint64_t> target(size);
  init_vector(target, nworkers);

  {
    std::random_shuffle(target.begin(), target.end());
    auto rd_sort_time = time_evaluate([&] {
        radix_sort(std::begin(target), std::end(target));
    });
    check_sorted(target);
    assert(target.size() == size);
    assert(std::is_sorted(target.begin(), target.end()));
    std::cout << size << " items my radix sort: " << rd_sort_time.count()
        << " msec." << std::endl;
  }

  {
    std::random_shuffle(target.begin(), target.end());
    auto rd_sort_time = time_evaluate([&] {
        radix_sort_wc(std::begin(target), std::end(target));
    });
    check_sorted(target);
    assert(target.size() == size);
    assert(std::is_sorted(target.begin(), target.end()));
    std::cout << size << " items write_combining radix sort: " << rd_sort_time
                                                                      .count()
        << " msec." << std::endl;
  }
  
  {
    std::random_shuffle(target.begin(), target.end());
    auto rd_sort_time = time_evaluate([&] {
        radix_sort_wc_opt(std::begin(target), std::end(target));
    });
    check_sorted(target);
    assert(target.size() == size);
    assert(std::is_sorted(target.begin(), target.end()));
    std::cout << size << " items write_combining_opt radix sort: " <<
        rd_sort_time
                                                                      .count()
        << " msec." << std::endl;
  }

  {
    std::random_shuffle(target.begin(), target.end());
    auto std_sort_time = time_evaluate([&] {
      std::sort(target.begin(), target.end());
    });
    check_sorted(target);
    assert(target.size() == size);
    assert(std::is_sorted(target.begin(), target.end()));
    std::cout << size << " items std::sort: " << std_sort_time.count()
    << " msec" << std::endl;
  }

  return 0;
}