C++中的无序集交集

Question

这是我的代码，想知道有什么办法可以让它更快吗？我的实现是brute force，就是对于a中的任意元素，尝试查找它是否也在b中，如果是，则放入结果集c中。任何更聪明的想法都会受到赞赏。

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> a = {1,2,3,4,5};
    std::unordered_set<int> b = {3,4,5,6,7};
    std::unordered_set<int> c;
    for (auto i = a.begin(); i != a.end(); i++) {
        if (b.find(*i) != b.end()) c.insert(*i);
    }
    for (int v : c) {
        std::printf("%d \n", v);
    }
}

Answer 1

渐近地，您的算法已达到最佳状态。

在实践中，我会添加一个检查以循环遍历两个集合中较小的集合并在较大的集合中进行查找。假设散列合理均匀分布，在 std::unoredered_set 中查找需要常数时间。所以这样一来，您将执行更少的此类查找。

Answer 2

Thanks Angew, why your method is faster? Could you elaborate a bit more?

好吧，让我为您提供一些额外的信息...

应该很清楚，无论您使用哪种数据结构，您都必须至少迭代其中一种数据结构中的所有元素，因此您无法比 O(n)、n 更好是选择迭代的数据结构中的元素数。现在最基本的是，你可以多快地查找另一个结构中的元素——使用哈希集，std::unordered_set 实际上是，这是 O(1)——至少如果冲突的数量足够小（ “合理均匀分布的哈希值”);退化的情况是所有值都具有相同的键...

到目前为止，你得到 O(n) * O(1) = O(n)。但是你仍然可以选择：O(n) 或 O(m)，如果 m 是另一个集合中的元素数。好吧，在复杂度计算中，这是一样的，我们有一个线性算法，但在实践中，如果您选择元素数量较少的集合，则可以节省一些哈希计算和查找...

Answer 3

您的算法对于无序集来说是最好的了。但是，如果您使用 std::set（使用二叉树作为存储）或更好的排序 std::vector，您可以做得更好。该算法应该是这样的：

获取 a.begin() 和 b.begin()
如果迭代器指向相等的元素，则添加到交集并递增两个迭代器。
否则递增指向最小值的迭代器
转到 2。

两者都应该是 O(n) 时间，但使用普通集合应该可以避免计算哈希或因哈希冲突引起的任何性能下降。

Answer 4

你可以用 std::copy_if()

std::copy_if(a.begin(), a.end(), std::inserter(c, c.begin()), [b](const int element){return b.count(element) > 0;} );

C++中的无序集交集

unordered set intersection in C++

c++

stl

unordered-set