寻找集合并集的最快方法

Question

我有一组由整数对组成的集合，例如 set<pair<int,int> > x1, x2, ... xn （其中 n 可以在 2 到 20 之间）。最快的方法是找到这些集合的并集？

抱歉如果一开始没有表述清楚，我指的是性能上的快速度，内存分配不是问题。

- Damir

---

将所有集合的元素加入一个集合中吗？ - nhahtdh

请问您能定义“快”吗？如果您指的是性能，请提供更多背景信息：需求、元素大小、元素数量、集合数量、目标机器。 - Sebastian Mach

@phresnel：我可以告诉你元素的大小，它是 sizeof<pair<int,int> >；-p 我猜测是8个字节。集合数量为2-20。其余内容不在问题中。 - Steve Jessop

@Steve：问题并不是很清楚。如果它涉及运行时性能，那么除了许多其他因素之外，元素的总数也是非常重要的。如果它们未知，那么它们未知或具有某些界限（或没有）的事实再次非常重要。大O度量并不是一切，特别是对于特定情况而言。但如果它是关于快速实现的，那么问题可以被温和地回答:D - Sebastian Mach

@Steve：哎呀，我意识到自己关于元素大小的错误了:D 我也误读了“其余部分不在问题中”为“其余部分不是问题”。非常抱歉地请求您的原谅。 - Sebastian Mach

我完全同意你的观点，任何答案都无法确定哪种方法对用户数据最快，因为我们不知道用户的数据是什么。同样适用于用户的硬件和C++实现。 - Steve Jessop

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 时，为了让添加的元素按递增顺序排序，每次调用函数都需要创建一个新的空容器（因为如果容器不为空，则添加的元素需要与已有值交错）。这些容器的开销可能会比随意插入 set 中的开销更高：你需要进行测试。

- Steve Jessop

---

问题指定输入数据已经是“set”集合。 - ecatmur

@ecatmur：我知道。不过它没有指定输出格式，这就是为什么我对它做了一个假设的原因。 - Steve Jessop

我的意思是，因为输入数据是“集合”，所以您知道x1和x2已经是排序好的范围。 - ecatmur

关于位置提示的观点很好；我已经在https://dev59.com/HGXWa4cB1Zd3GeqPQdDz上询问了这个问题。 - ecatmur

Answer 2

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

如果您有两个集合之间相似程度的测量值，则最好首先找到最相似的集合的并集。也就是说，优先选择消除重复项的并集操作。

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

- Rafael Baptista

Answer 3

很遗憾，我认为您只能使用线性 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;
}

- Richard J. Ross III

---

我并不认为这个选项是最好的，因为每次插入需要O(log n)的时间，这比set_union的2*(count1+count2)-1要多得多。@phresnel的第一个解决方案应该更快。 - Till

@Till：phresnel的解决方案中的“插入器”也使用了set::insert方法。因此，它与此处的解决方案具有相同的大O复杂度 - 顺便说一下，这里声明的复杂度不是线性的，而是O（N * log（N））。但是，如果您让“插入器”将结果插入到list而不是set中，则phresnel的解决方案可以是线性的。但我不确定这是否符合原始问题的要求。 - mastov

这不正确，因为它会引入重复项。并集由唯一、非重复的条目组成，这些条目要么在A中，要么在B中，要么同时在两者中。 - Aleksandr Hovhannisyan

@AleksandrH s1和s2都已经是集合，这使得类型S成为一个集合。在插入过程中，生成的集合将自动删除任何重复项。 - Richard J. Ross III

@RichardJ.RossIII 嗯，但除非我错了，插入不会删除重复项。例如，假设 s1 = {1, 2, 3} 和 s2 = {2, 3}。那么并集应该是 {1, 2, 3}。 - Aleksandr Hovhannisyan

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

尽管通常情况下，我们应该优先选择标准算法并受益于其高质量的实现。

如果您所说的“快”是指性能，那么我们无法提供帮助，因为我们没有相关要求。不同的方法可能会在不同的情况下得出不同的结果。

（*）注：有时候，这个网站因与标准不完全一致而受到批评。

- Sebastian Mach

Answer 5

尝试使用algorithm头文件中的set_union函数。

- Anon Mail

Answer 6

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

构造一个vector<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());
}

- ecatmur

---

由于问题提出者对速度感兴趣，使用n路去重合并是否比n个原地2路合并后再去重更快呢？在您当前的代码中，第一个集合的内容会在向量中移动2*(n-1)次，这似乎是浪费的。当然，这需要更多的代码，因为没有标准算法可以进行n路合并。 - Steve Jessop

可能是的；我想你会想要按照它们的间接值来排序迭代器列表。比较性能会很有趣。 - ecatmur

Answer 7

你可以使用 std::set_union 递归地进行操作，或者将所有的集合插入到一个结果集中（重复项会被集合消除）。如果项目数量很小，你可以尝试将它们全部插入到一个向量中，对其进行排序并在向量上使用std::unique。

- MadScientist