Efficient vector and caching techniques

efficient-techniques.cc

#include <algorithm>
#include <chrono>
#include <iostream>
#include <iterator>
#include <memory>
#include <random>
#include <unordered_map>

// Efficiency with Algorithms, Performance with Data Structures
// CppCon 2014: Chandler Carruth
// https://www.youtube.com/watch?v=fHNmRkzxHWs

const unsigned SEED = 42;

template <class V>
auto InsertIfNotExists(
    const std::string& key, const V& value,
    typename std::unordered_map<std::string, std::unique_ptr<V>>& cache) -> V* {
  if (!cache[key]) {
    cache[key] = std::make_unique<V>(value);
  }
  return cache[key].get();
}

template <class V>
auto InsertIfNotExists2(
    const std::string& key, const V& value,
    typename std::unordered_map<std::string, std::unique_ptr<V>>& cache) -> V* {
  auto& entry = cache[key];
  if (entry) {
    entry = std::make_unique<V>(value);
  }
  return entry.get();
}

auto VectorWithRandomNumbers(const typename std::vector<double>::size_type size)
    -> typename std::vector<double> {
  std::default_random_engine generator(SEED);
  std::uniform_real_distribution distribution(0.0, 1.0);
  std::vector<double> items{};
  for (typename std::remove_const<decltype(size)>::type i{0}; i < size; ++i) {
    const auto random_number = distribution(generator);
    items.push_back(random_number);
  }
  return items;
}

auto VectorWithRandomNumbers2(
    const typename std::vector<double>::size_type size) ->
    typename std::vector<double> {
  std::default_random_engine generator(SEED);
  std::uniform_real_distribution distribution(0.0, 1.0);
  std::vector<double> items{};
  items.reserve(size);
  for (typename std::remove_const<decltype(size)>::type i{0}; i < size; ++i) {
    const auto random_number = distribution(generator);
    items.push_back(random_number);
  }
  return items;
}

auto main() -> int {
  const auto size = 100;
  const auto repeats = 100000;

  std::vector<unsigned long long> inefficient_times{};
  std::vector<unsigned long long> efficient_times{};
  inefficient_times.reserve(repeats);
  efficient_times.reserve(repeats);
  for (int i = 0; i < repeats; ++i) {
    const auto start = std::chrono::high_resolution_clock::now();
    const auto result = VectorWithRandomNumbers(size);
    const auto end = std::chrono::high_resolution_clock::now();
    const auto duration =
        std::chrono::duration_cast<std::chrono::nanoseconds>(end - start)
            .count();
    inefficient_times.push_back(duration);

    const auto start2 = std::chrono::high_resolution_clock::now();
    const auto result2 = VectorWithRandomNumbers2(size);
    const auto end2 = std::chrono::high_resolution_clock::now();
    const auto duration2 =
        std::chrono::duration_cast<std::chrono::nanoseconds>(end2 - start2)
            .count();
    efficient_times.push_back(duration2);
  }
  // std::copy(inefficient_times.begin(), inefficient_times.end(),
  // std::ostream_iterator<unsigned long long>(std::cout, "\n"));
  // std::sort(inefficient_times.begin(), inefficient_times.end());
  // std::cout << "inefficient median: " <<
  // inefficient_times[inefficient_times.size() / 2] << '\n';
  // std::copy(efficient_times.begin(), efficient_times.end(),
  // std::ostream_iterator<unsigned long long>(std::cout, "\n"));
  // std::sort(efficient_times.begin(), efficient_times.end());
  // std::cout << "efficient median: " << efficient_times[efficient_times.size()
  // / 2] << '\n';

  // std::cout << "done part 1\n" << std::flush;
  // std::cout <<
  // "\n\n\n---------------------------------------------------------------------------------------------------------\n\n\n";

  std::vector<unsigned long long> inefficient_cache_times{};
  std::vector<unsigned long long> efficient_cache_times{};
  std::vector<std::string> keys{};
  keys.reserve(inefficient_times.size());
  std::transform(inefficient_times.begin(), inefficient_times.end(),
                 std::back_inserter(keys),
                 [](const unsigned long long x) { return std::to_string(x); });
  std::unordered_map<std::string, std::unique_ptr<unsigned long long>> cache{};
  std::unordered_map<std::string, std::unique_ptr<unsigned long long>> cache2{};
  for (typename std::remove_const<decltype(inefficient_times.size())>::type i{
           0};
       i < inefficient_times.size(); ++i) {
    const auto start = std::chrono::high_resolution_clock::now();
    auto value = InsertIfNotExists(keys[i], efficient_times[i], cache);
    const auto end = std::chrono::high_resolution_clock::now();
    *value *= 2;
    const auto duration =
        std::chrono::duration_cast<std::chrono::nanoseconds>(end - start)
            .count();
    inefficient_cache_times.push_back(duration);

    const auto start2 = std::chrono::high_resolution_clock::now();
    auto value2 = InsertIfNotExists(keys[i], efficient_times[i], cache2);
    const auto end2 = std::chrono::high_resolution_clock::now();
    *value2 += *value;
    const auto duration2 =
        std::chrono::duration_cast<std::chrono::nanoseconds>(end2 - start2)
            .count();
    efficient_cache_times.push_back(duration2);
  }
  std::copy(inefficient_cache_times.begin(), inefficient_cache_times.end(),
            std::ostream_iterator<unsigned long long>(std::cout, "\n"));
  // std::sort(inefficient_cache_times.begin(), inefficient_cache_times.end());
  // std::cout << "inefficient cache median: " <<
  // inefficient_cache_times[inefficient_cache_times.size() / 2] << '\n';
  // std::cout <<
  // "\n\n\n---------------------------------------------------------------------------------------------------------\n\n\n";
  // std::copy(efficient_cache_times.begin(), efficient_cache_times.end(),
  // std::ostream_iterator<unsigned long long>(std::cout, "\n"));
  // std::sort(inefficient_cache_times.begin(), inefficient_cache_times.end());
  // std::sort(efficient_cache_times.begin(), efficient_cache_times.end());
  // std::cout << "efficient cache median: " <<
  // efficient_cache_times[efficient_cache_times.size() / 2] << '\n';
}