14

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

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

4

7 回答 7

11

假设结果也需要是一个集合，那么您别无选择，只能将每个元素的每个元素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是，为了获得以递增顺序将元素添加到集合中的好处，每次调用它时都需要创建一个新的空容器（因为如果它不是空的，那么添加的元素需要与已经在其中的值）。这些容器的开销可能高于以任意顺序插入集合的开销：您必须对其进行测试。

于 2012-07-06T12:24:48.133 回答
6

首先找到最小集合的并集。也就是说，按集合长度对集合进行排序，计算两个最小集合的并集，删除这些集合，根据其大小将并集插入集合列表中。

如果您测量了两个集合的相似程度，那么您最好先找到最相似集合的并集。那是更喜欢尽早消除重复的联合操作。

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

于 2012-07-06T12:27:43.290 回答
6

不幸的是，我相信您仅限于线性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;
}
于 2012-07-06T12:23:37.913 回答
4

我假设快速你的意思是快速实施。

然后：std::set_union (*)

两组示例：

#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()));

}

对于 n 个集合，手写它可能是最易于维护的解决方案：

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

虽然一般来说，人们应该更喜欢标准算法并从它们的质量实施中获益。

如果您所说的快速是指性能，我们将无能为力，因为我们没有要求。对于不同的情况，不同的方法可能会给出不同的结果。

(*) 注意：该网站有时会因为与标准相比不是 100% 准确而令人不悦

于 2012-07-06T12:23:00.723 回答
3

为了节省内存分配并改善局部性，最好使用单个vector<T>作为工作内存。

构造 avector<T>并保留所有 s 中的元素总数（计算重复项）。然后，从空范围开始，[v.begin(), v.begin())通过附加每个集合的内容、合并和唯一化，将其扩展到类似集合（唯一、排序）的范围：

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());
}
于 2012-07-06T12:38:38.587 回答
3

尝试头部算法中的 set_union。

于 2012-07-06T12:20:47.833 回答
2

您可以递归使用std::set_union 或简单地将所有集合插入结果集中（重复项被集合消除）。如果项目的数量非常少，您可以尝试将其全部插入向量中，对其进行排序并在向量上使用 std::unique。

于 2012-07-06T12:21:33.067 回答