Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Compare performances between different intersection algorithms
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.