logo标签列表

两个集合的高效交集

c++algorithmdata-structures
4
我有两组（或映射）需要有效地处理它们的交集。 我知道有两种方法可以做到这一点：
- 像std::set_intersection一样迭代两个映射：O(n1+n2) - 迭代一个映射并在另一个映射中查找元素：O(n1*log(n2))
根据大小，这两个解决方案中的任何一个都明显更好（已经计时），因此我需要基于大小在这些算法之间切换（有点混乱） - 或者找到一种胜过两者的解决方案，例如使用某种map.find()的变体，将前一个迭代器作为提示（类似于map.emplace_hint(...)） - 但我找不到这样的函数。
问题：是否可能直接使用STL或某个兼容库结合这两个解决方案的性能特征？
请注意，性能要求使其与早期的问题不同，例如Efficient intersection of sets?。
2
这个问题中的“性能要求”与链接问题有何不同之处？你只是说需要高效，而另一个问题则是要求高效地完成它... - 463035818_is_not_a_number
性能要求从调用到调用会动态变化，因此我不能静态地选择一个替代方案。这部分在链接的问题中没有解决。 - Hans Olsson
1
在这个优化级别（不仅仅是使用标准库），我们真的需要看到样本数据和基准测试。一旦你得到了实际数据、编译器和硬件，那么你总是可以进行更多的优化。如果没有这些信息，那么这个问题与链接的问题并没有太大的区别，尽管它表达了根据手头情况切换方法的意愿（标准库可能已经做到了这一点）。 - wally
@wally 标准 set_intersection 的实现可能会切换方法，但是否有任何实现这样做呢？如果有，是如何实现的？ - Hans Olsson
1
那么，如果if ((n1+n2) < n1*log2(n2))，那么应该选择哪一个呢？（当然还需要考虑到 n2*log2(n1)）。顺便说一句，这并不是一个不同的要求，而只是在一般情况下如何高效地完成。抱歉挑剔了一下，我只是想更好地理解你的意思，尽管我仍然觉得这接近于重复问题。 - 463035818_is_not_a_number
显示剩余8条评论
4个回答
4
几乎在所有情况下，`std::set_intersection` 都是最佳选择。只有当集合中包含非常少的元素时，才可能有其他更好的解决方案。由于以二为底数的对数特性，它的增长速度如下：

n = 2, log(n)= 1
n = 4, log(n)= 2
n = 8, log(n)= 3
.....
n = 1024 log(n) = 10

如果集合的长度超过5-10个元素，那么O(n1*log(n2))比O(n1 + n2)要复杂得多。STL 添加这样的函数并实现是有道理的。这也会使代码更易读。
选择排序对于长度小于20的集合比归并排序或快速排序更快，但很少使用。
首先，有5个元素和>1000个元素的情况，这是可能发生的。然而，我不同意这个结论。对于选择排序和快速排序，它取决于算法的复杂度。我还没有测试++与在映射中查找的相对性能-但它们似乎更相似。如果(n1+n2)和n2*log2(n1)的常数相同，那么n1=1000时，n2=111，n1=10,000时，n2=813。 - Hans Olsson
我提到了选择排序，因为它的复杂度是O(n^2)，但对于少量元素来说，它比快速排序或合并排序表现更好。然而，如果集合的大小相等，那么对于包含10个元素的集合，你将需要10+10的操作或者10*3.32(log(10))的操作 - 超过30。唯一可能使find更快的方法是当你有小于4个元素的集合时，log(n)将小于2。 - Petar Velev
@PetarVelev 这些集合的长度可能非常不同。如果我们有一个包含1024个元素的集合和另一个只有100个元素的集合，那么它们的交集大小为1024+100=1124，而100*log2(1024)=1000 - 我发现有些情况下，大于1000个元素的集合与不仅是小于100个元素的集合相交，甚至是小于10个元素的集合。 - Hans Olsson
1
@HansOlsson，你在比较苹果和橙子。std::set_intersection被规定为“最多2 （N1 + N2-1）次比较”，而std::set :: find被规定为O（log（size（）））。对于一个，你有一个严格的操作计数*，而另一个是渐近界限。 - Caleth
@Caleth 理论上保证有所不同，但实际上 set_intersection 实际上使用了这么多的比较，而 set::find 对于小集合没有主要开销和小常数，即它对 "小" c1 和 c2 是 <=c1+c2*log2(size()) 的 - 这给出了类似的结论。我也可以看到，将算法更改为不使用 set_intersection 可以改善程序中该部分的性能，从约 90 秒提高到 30 秒 - 而该部分还涉及大量其他代码。 - Hans Olsson
2
对于以二叉树实现的集合，实际上有一种算法可以结合您提到的两种过程的优点。基本上，您执行类似于std :: set_intersection的合并操作，但在遍历一个树时，跳过其他树中所有小于当前值的分支。
结果交集需要O（min（n1 log n2，n2 log n1，n1 + n2）），这正是您想要的。
不幸的是，我相信std :: set不提供支持此操作的接口。
在处理倒排索引等类似事物时，我以前做过几次。通常我会创建具有skipTo（x）操作的迭代器，该操作将推进到下一个元素> = x。为了满足我的承诺的复杂度，它必须能够在对数时间内跳过N个元素。然后，交集看起来像这样：
void get_intersection(vector<T> *dest, const set<T> set1, const set<T> set2)
{
    auto end1 = set1.end();
    auto end2 = set2.end();
    auto it1 = set1.begin();
    if (it1 == end1)
        return;
    auto it2 = set2.begin();
    if (it2 == end2)
        return;
    for (;;)
    {
        it1.skipTo(*it2);
        if (it1 == end1)
            break;
        if (*it1 == *it2)
        {
            dest->push_back(*it1);
            ++it1;
        }
        it2.skipTo(*it1);
        if (it2 == end2)
            break;
        if (*it2 == *it1)
        {
            dest->push_back(*it2);
            ++it2;
        }
    }
}

使用迭代器的向量可以轻松扩展为任意数量的集合，几乎任何有序的集合都可以扩展以提供所需的迭代器 -- 排序数组、二叉树、B-树、跳表等。

好的，那似乎是我正在寻找的内容。你有任何参考资料吗？是否有Boost或类似库的实现？ - Hans Olsson
不幸的是，我认为你必须自己编写代码。关键通常是一个具有高效跳过操作的集合。如果你遇到这种情况，我会更新答案以描述如何基于该操作实现。 - Matt Timmermans
0
关于性能要求，O(n1 + n2) 在大多数情况下是非常好的复杂度，因此只有在紧密循环中进行此计算时才值得考虑。
如果您确实需要它，组合方法并不太糟糕，也许可以尝试以下伪代码：
x' = set_with_min_length([x, y])
y' = set_with_max_length([x, y])
if (x'.length * log(y'.length)) <= (x'.length + y'.length):
     return iterate_over_map_find_elements_in_other(y', x')

return std::set_intersection(x, y)

我认为你不会找到一个能够超越这两个复杂度的算法，但如果有证据证明我错了，我也很乐意接受。

@Caleth 哦，现在我明白了，这里太热了 ;) 我完全忽略了前两行。 - 463035818_is_not_a_number
0

我不知道如何使用标准库来实现这个，但是如果你自己写了一个平衡二叉搜索树，那么可以实现一个有限的“带提示查找”。（根据您的其他要求，BST 重新实现也可以省略父指针，这可能比STL更高效。）

假设提示值小于要查找的值，并且我们知道提示节点的祖先堆栈以及提示节点所属的左子树中的节点。首先在提示节点的右子树中正常搜索，根据需要将节点推入堆栈（为下一次准备好提示）。如果这行不通，那么当堆栈顶部节点的值小于查询值时，弹出堆栈。从上次弹出的最后一个节点（如果有的话）开始搜索，需要时将其推入。

我声明，在按升序连续搜索值时使用此机制时，(1)每条树边最多遍历一次，(2)每个查找最多遍历两条下降路径的边。给定具有n2个节点的二叉树中2*n1下降路径的代价是O(n1 log n2)。它也是O(n2)，因为每条边只会遍历一次。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接