找到集合的最快方法

Question

我有成对的int对 set<pair<int,int> > x1, x2, ... xn(n可以在2到20之间).找到这些集合的最快方法是什么？

对不起如果我一开始没说清楚,我的意思是性能快,内存分配不是问题.

Answer 1

假设结果也需要是一个集合,那么你别无选择,只能将每个元素插入x_i到结果集中.所以明显的实现是:

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

剩下的问题是这是否可以打败速度.

单个元素insert需要一个position提示,如果正确加快插入速度.所以可能会发现这样的事情比x.insert(x2.begin(), x2.end());以下更快:

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

但这取决于数据:该位置可能准确也可能不准确.您可以通过在开始之前将所有元素按顺序排列来确保它是最好的工具set_union.这可能更好地命名merge_and_dedupe_sorted_ranges,因为它的作用没有什么特别的std::set.你可以set_union进入中间向量,或者进入这样的集合:

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

我对使用的关注set_union是,为了获得以递增的顺序将元素添加到集合中的好处,每次调用它时都需要创建一个新的空容器(因为如果它不是空的,那么添加的元素需要与之交错已存在的值).这些容器的开销可能高于以任意顺序插入集合的开销:您必须测试它.

Answer 2

不幸的是,我相信你只能使用线性O(N)解决方案,因为所有联合都是两组中元素的组合.

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

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

     return result;
}

Answer 3

首先找到最小集合的并集.这是按照设置长度对你的集合进行排序,计算两个最小集合的并集,删除这些集合,根据它的大小将union插入到集合列表中.

如果您测量了两组可能的相似程度,那么您最好首先找到最相似组的并集.这更像是工会操作,可以尽早消除重复.

编辑:对于两组之间的每个联合操作 - 将较小的组合并到较大的组中.