Compare performances between different intersection algorithms

list_intersection_performance.cpp

#include <iostream>
#include <string>
#include <unordered_set>
#include <set>
#include <list>
#include <algorithm>
#include <random>
#include <chrono>
#include <sstream>

using std::chrono::high_resolution_clock;
using std::chrono::time_point;
using std::chrono::duration_cast;
using std::chrono::milliseconds;
using namespace std;

template <typename T> using intersection_set = set<reference_wrapper<T const>, less<T>>;

list<string> compare_list_warning_00(list<string> const& list_one, list<string> const& list_two)
{
  list<string> output;
  for(string const& value1 : list_one) {
    for(string const& value2 : list_two) {
      if (value1 == value2) output.push_back(value1);
    }
  }
  return output;
}

list<string> compare_list_warning_01(list<string> const& list_one, list<string> const& list_two)
{
  intersection_set<string> set_one, set_two;
  set_one.insert(begin(list_one), end(list_one));
  set_two.insert(begin(list_two), end(list_two));
  list<string> output;
  set_intersection(begin(set_one), end(set_one), begin(set_two), end(set_two), back_inserter(output), less<string>());
  return output;
}

list<string> compare_list_warning_02(list<string> const& list_one, list<string> const& list_two)
{
  list<string> const& small_list = list_one.size() < list_two.size() ? list_one : list_two;
  list<string> const& big_list = list_one.size() < list_two.size() ? list_two : list_one;

  list<string> duplicates;
  unordered_set<string> duplicate_finder;
  duplicate_finder.reserve(small_list.size());
  duplicate_finder.insert(begin(small_list), end(small_list));
  copy_if(begin(big_list), end(big_list), back_inserter(duplicates), [&](string const& v) { return (duplicate_finder.find(v) != end(duplicate_finder)); });
  return  duplicates;
}

list<string> compare_list_warning_03(list<string> const& list_one, list<string> const& list_two)
{
  list<string> const& small_list = list_one.size() < list_two.size() ? list_one : list_two;
  list<string> const& big_list = list_one.size() < list_two.size() ? list_two : list_one;
  list<string> duplicates;
  set<string> duplicate_finder;
  duplicate_finder.insert(begin(small_list), end(small_list));
  copy_if(begin(big_list), end(big_list), back_inserter(duplicates), [&](string const& v) { return (duplicate_finder.find(v) != end(duplicate_finder)); });
  return  duplicates;
}

class string_generator {
  std::string const alnums = "abcdefghijklmnopqrstuvwxyz0123456789";
  size_t const alnums_size = 36u;
  random_device rd_;
  mt19937 gen_;
  uniform_int_distribution<size_t> size_gen_ = uniform_int_distribution<size_t>(5, 50);
  uniform_int_distribution<unsigned int> char_chooser_ = uniform_int_distribution<unsigned int>(0u, alnums_size - 1u);

 public:
  string_generator() : gen_(rd_()) {}

  std::string operator() () {
    ostringstream output;
    size_t size = size_gen_(gen_);
    for(size_t index = 0u; index < size; ++index) output << alnums.at(char_chooser_(gen_));
    return output.str();
  }
};

size_t measure_exec_time(std::function<list<string>()> func) {
  time_point<high_resolution_clock> start = high_resolution_clock::now();
  func();
  time_point<high_resolution_clock> end = high_resolution_clock::now();
  return duration_cast<milliseconds>(end-start).count();
}

int main() {
  string_generator gen;
  list<string> list1, list2;
  for(size_t nb = 200000u; nb; --nb) list1.emplace_back(gen());
  for(size_t nb = 50000u; nb; --nb) list2.emplace_back(gen());

  auto f0 = std::bind(compare_list_warning_00, list1, list2);
  auto f1 = std::bind(compare_list_warning_01, list1, list2);
  auto f2 = std::bind(compare_list_warning_02, list1, list2);
  auto f3 = std::bind(compare_list_warning_03, list1, list2);

  //std::cout << measure_exec_time(f0) << "\n";
  std::cout << measure_exec_time(f1) << "\n";
  std::cout << measure_exec_time(f2) << "\n";
  //std::cout << measure_exec_time(f3) << "\n";
  std::cout << std::flush;

  return 0;
}