Skip to content

Instantly share code, notes, and snippets.

@samatjain
Created June 20, 2018 23:31
Show Gist options
  • Save samatjain/10d72cf594ae1778feb8422c41cefba3 to your computer and use it in GitHub Desktop.
Save samatjain/10d72cf594ae1778feb8422c41cefba3 to your computer and use it in GitHub Desktop.
#include <algorithm>
#include <chrono>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <random>
#include <set>
#include <unordered_set>
#include <thread>
#include <vector>
#include <parallel/algorithm>
using namespace std;
using std::cerr;
using std::cout;
using std::endl;
using std::map;
using std::string;
using std::vector;
using std::set;
using std::unordered_set;
/**
* @brief Portable C++ way to sleep for \a s seconds
*/
void sleep(unsigned int s) {
std::this_thread::sleep_for(std::chrono::seconds(s));
}
/**
* @brief Portable C++ way to sleep for \a ms milliseconds
*/
void usleep(unsigned int ms) {
std::this_thread::sleep_for(std::chrono::milliseconds(ms));
}
/**
* @brief Return an integer between s and e (inclusive)
*/
int RandomIntegerFromRange(const int s, const int e) {
std::random_device rng; // generator
std::uniform_int_distribution<int> dice(s, e); // distribution
return dice(rng);
}
/**
* @brief Decide true or false, 50% of the time
*/
bool Maybe() {
std::random_device rng;
std::bernoulli_distribution distribution(0.5);
return distribution(rng);
}
class ScopedTimer {
typedef std::chrono::high_resolution_clock Timer;
typedef std::chrono::time_point<Timer> TimePoint;
typedef std::chrono::milliseconds ms;
typedef std::chrono::nanoseconds ns;
public:
/**
* @param[out] output Where to save duration. IMPORTANT: This is a pointer, and it needs
* to exist when this object goes out of scope.
*/
ScopedTimer(int* output) : _output(output) {
_start = Timer::now();
}
ScopedTimer(const string& description) : ScopedTimer(nullptr) {
_description = description;
//cerr << "→ `" << description << "` started" << endl;
}
~ScopedTimer() {
_end = Timer::now();
int duration = std::chrono::duration_cast<std::chrono::milliseconds>(_end - _start).count();
if (_output != nullptr) {
*_output = duration;
} else {
cerr << "→ «" << _description << "» finished, took " << duration << "ms" << endl;
}
}
private:
string _description; ///< Description for block we are timing
TimePoint _start, _end; ////< Start and end times
int* _output; ///< Ref. to where we will save time
};
template<class T>
void PrintWhatever(T to_print)
{
auto inner_iterable_count = 0;
for (auto inner_iterable = to_print.cbegin(), end = to_print.cend();
inner_iterable < end; inner_iterable++) {
cout << std::setw(3) << inner_iterable_count << ": ";
inner_iterable_count++;
for (const auto& i: *inner_iterable) {
cout << std::setw(2) << i << " ";
}
cout << endl;
}
}
template<typename Input, typename Output>
static void IntersectionUpdate(const std::set<Input> &ac, std::set<Output> *bc)
{
typename std::set<Input>::const_iterator a = ac.begin();
const typename std::set<Input>::const_iterator a_end = ac.end();
typename std::set<Output>::iterator b = bc->begin();
const typename std::set<Output>::iterator b_end = bc->end();
while (a != a_end && b != b_end) {
if (*a < *b) {
++a;
} else if (*a > *b) {
const typename std::set<Output>::iterator b_old = b++;
bc->erase(b_old); // erase doesn't invalidate b.
} else { // Elements are equal, keep them in the intersection.
++a;
++b;
}
}
bc->erase(b, b_end); // Remove remaining elements in bc but not in ac.
}
int main()
{
/*int time(0);
{
ScopedTimer t(&time);
sleep(1);
}
cout << "Block took " << time << "ms" << endl;
{
ScopedTimer foobar("the foobar block");
usleep(10);
}*/
const int NUM_OUTER = 10000;
const int NUM_INNER = 100;
vector< vector<int> > vector_of_vectors(NUM_OUTER);
{
ScopedTimer vi("Creating a vector of vectors, w/ push_back & reserve");
for (size_t j = 0; j < vector_of_vectors.size(); j++) {
vector<int> v;
v.reserve(NUM_OUTER);
/*
* Fill inner vector with numbers
*
* Some of the vectors may not have all numbers, shifted around a bit. We decide if
* this vector fill will be shifted, and then decide how much it'll be shifted
*
* Disclaimer: I suck at statistics
*/
auto f = Maybe() ? 0 : RandomIntegerFromRange(0, 3);
auto num_inner_fudge = RandomIntegerFromRange(0, 2);
size_t num_inner = NUM_INNER - 1 + num_inner_fudge;
for (size_t i = 0; i < num_inner; i++) {
v.push_back(++f);
}
vector_of_vectors.at(j) = std::move(v);
}
}
//PrintWhatever(vector_of_vectors);
vector< set<int> > vector_of_sets(NUM_OUTER);
{
ScopedTimer vi("Creating a vector of sets, w/ hint w/ OpenMP");
#pragma omp simd
for (size_t j = 0; j < vector_of_sets.size(); j++) {
set<int> v;
/*
* Fill inner vector with numbers
*
* Some of the vectors may not have all numbers, shifted around a bit. We decide if
* this vector fill will be shifted, and then decide how much it'll be shifted
*
* Disclaimer: I suck at statistics
*/
auto f = Maybe() ? 0 : RandomIntegerFromRange(0, 3);
auto num_inner_fudge = RandomIntegerFromRange(0, 2);
size_t num_inner = NUM_INNER - 1 + num_inner_fudge;
for (size_t i = 0; i < num_inner; i++) {
v.insert(v.end(), ++f);
}
vector_of_sets.at(j) = std::move(v);
}
}
//PrintWhatever(vector_of_sets);
// MAGIC
{
ScopedTimer t("Stupid way");
std::map<int, int> counts;
for (const auto& inner_vector: vector_of_vectors) {
for (auto i: inner_vector) {
counts[i]++;
}
/*cout << "Printing counts" << endl;;
for (auto item: counts) {
cout << item.first << " " << item.second << endl;
}*/
}
// Go through counts
set<int> candidates;
for (const auto& item: counts) {
if (item.second == NUM_OUTER) {
candidates.insert(item.first);
}
}
cout << "Largest common element = " << *candidates.rbegin() << endl;
}
{
ScopedTimer t("Non-parallel set intersection");
set<int> last_intersection = vector_of_sets.at(0);
set<int> new_intersection;
for (const auto& inner_set : vector_of_sets) {
new_intersection.clear();
set_intersection(inner_set.begin(), inner_set.end(),
last_intersection.begin(), last_intersection.end(),
std::inserter(new_intersection, new_intersection.begin()));
/*cout << "Comparing inner_set = ";
for (const auto& i: inner_set) {
cout << i << " ";
}
cout << " and ";
for (const auto& i: last_intersection) {
cout << i << " ";
}
cout << endl;*/
last_intersection = std::move(new_intersection);
}
/*cout << "Final intersection = ";
for (const auto& i: last_intersection) {
cout << i << " ";
}
cout << endl;*/
cout << "Largest common element = " << *last_intersection.rbegin() << endl;
}
{
ScopedTimer t("gcc parallel set intersection");
set<int> last_intersection = vector_of_sets.at(0);
set<int> new_intersection;
for (const auto& inner_set : vector_of_sets) {
new_intersection.clear();
__gnu_parallel::set_intersection(
inner_set.begin(), inner_set.end(),
last_intersection.begin(), last_intersection.end(),
std::inserter(new_intersection, new_intersection.begin()));
/*cout << "Comparing inner_set = ";
for (const auto& i: inner_set) {
cout << i << " ";
}
cout << " and ";
for (const auto& i: last_intersection) {
cout << i << " ";
}
cout << endl;*/
last_intersection = std::move(new_intersection);
}
/*cout << "Final intersection = ";
for (const auto& i: last_intersection) {
cout << i << " ";
}
cout << endl;*/
cout << "Largest common element = " << *(last_intersection.rbegin()) << endl;
}
{
ScopedTimer t("in-place set intersection");
set<int> last_intersection = vector_of_sets.at(0);
set<int> new_intersection;
for(auto inner_set = vector_of_sets.cbegin()+1, end = vector_of_sets.cend();
inner_set != end; inner_set++) {
IntersectionUpdate(*inner_set, &last_intersection);
/*cout << "Comparing inner_set = ";
for (const auto& i: *inner_set) {
cout << i << " ";
}
cout << " and ";
for (const auto& i: last_intersection) {
cout << i << " ";
}
cout << endl;*/
}
/*cout << "Final intersection = ";
for (const auto& i: last_intersection) {
cout << i << " ";
}
cout << endl;*/
cout << "Largest common element = " << *(last_intersection.rbegin()) << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment