The fastest way to find union of sets

问题:

I have sets of pairs of int like set<pair<int,int> > x1, x2, ... xn ( n can be between 2 and 20). What is the fastest way to find union of those sets ?

Sorry If I wasn't make clear at the beginning, I meant fast in performance, memory allocation is not a problem.

回答1:

Unfortunately, I believe that you are limited to a linear O(N) solution, as all a union would be is a combination of the elements in both sets.

template<typename S>
S union_sets(const S& s1, const S& s2)
{
     S result = s1;

     result.insert(s2.cbegin(), s2.cend());

     return result;
}

回答2:

Assuming that the result needs to be a set too, then you have no choice but to insert every element of each x_i into that result set. So the obvious implementation is:

set<pair<int,int>> x(x1);
x.insert(x2.begin(), x2.end());
// etc

The remaining question is whether this can be beaten for speed.

The single-element insert takes a position hint, which if correct speeds up insertion. So it might turn out that something like this is faster than x.insert(x2.begin(), x2.end());:

auto pos = x.begin()
for (auto it = x2.begin(); it != x2.end(); ++it) {
    pos = x.insert(pos, *it);
}

It depends on the data, though: that position may or may not be accurate. You can ensure that it is by putting all the elements in order before you start, for which the best tool is probably set_union. That might better be named merge_and_dedupe_sorted_ranges, because what it does has nothing particularly to do with std::set. You could either set_union into intermediate vectors, or else into sets like this:

set<pair<int,int>> x;
set_union(x1.begin(), x1.end(), x2.begin(), x2.end(), inserter(x, x.end());

My concern with using set_union is that in order to get the benefit of adding the elements to a set in increasing order, you need to create a new empty container each time you call it (because if it's not empty then the elements added need to interleave with the values already in it). The overhead of these containers might be higher than the overhead of inserting into a set in arbitrary order: you would have to test it.

回答3:

Find the union of the smallest sets first. That is order your sets by set length, compute the union of the two smallest sets, delete those sets, insert the union into your set list according it its size.

If you had a measurement of how similar two sets are likely to be then you best bet there would be to first find the union of the most similar sets first. That is prefer union operations that eliminate duplicates early.

Edit: And for each union operation between two sets - merge the smaller set into the bigger set.

回答4:

I assume with fast you mean fast to implement.

Then: std::set_union (*)

Example for two sets:

#include <set>
#include <algorithm>
#include <iterator>
using namespace std;

int main () {
    set<pair<int,int> > a, b, uni;
    set_union (a.begin(), a.end(),
               b.begin(), b.end(),
               inserter(uni, uni.begin()));

}

for n sets, hand writing it might be the most maintainable solution:

#include <set>
#include <vector>
using namespace std;

int main () {
    vector<set<pair<int,int>>> sets;
    set<pair<int,int>> uni;

    for (const auto &s : sets)
        for (const auto &elem : s)
            uni.insert (elem);
}

though in general, one should prefer standard algorithms and profit from their quality implementation.

If by fast you mean performance, we can't help as we don't have the requirements. Different approaches might give different results for different circumstances.

---

(*) note: the site is frowned upon sometimes for not being 100% accurate vs. the standard

回答5:

Try the set_union in the header algorithm.

回答6:

You could use std::set_union recursively or simply insert all sets into a result set (duplicate items are eliminated by the set). If the number of items is very small you can try to insert it all into a vector, sorting it and use std::unique on the vector.

回答7:

To save on memory allocations and improve locality, it'd be better to use a single vector<T> as working memory.

Construct a vector<T> and reserve the total number of elements in all of the s (counting duplicates). Then, starting with the empty range [v.begin(), v.begin()), extend it to a set-like (unique, sorted) range by appending the contents of each set, merging and uniquifying:

vector<T> v;
v.reserve(<total size>);
for (set<T> &s: sets) {
    auto middle = v.insert(v.end(), s.begin(), s.end());
    inplace_merge(v.begin(), middle, v.end());
    v.erase(v.unique(v.begin(), v.end()), v.end());
}