gistfile1.txt

#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;
}