代码之家 › 专栏 › 技术社区 › Lin Ma

C中的无序集交集++

unordered-set stl c++

8

Lin Ma · 技术社区 · 8 年前

这是我的代码,想知道有什么办法可以让它更快?我的实现是蛮力,它适用于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);
    }
}

4 回复 | 直到 8 年前

1

10

Angew is no longer proud of SO 8 年前

渐进地说,您的算法已经尽可能好了。

实际上,我会添加一个检查来循环两个集合中较小的集合,并在较大的集合中进行查找。假设哈希分布合理均匀,则在 std::unoredered_set 需要固定的时间。这样,您将执行更少的此类查找。

2

4

stephane k. 7 年前

您可以使用std::copy\u if()执行此操作

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

3

doron 8 年前

您的算法与无序集的算法一样好。但是,如果使用 std::set (使用二叉树作为存储)或更好的排序 std::vector ,你可以做得更好。算法应该类似于:

获取迭代器以 a.begin() 和 b.begin()
如果迭代器指向equal元素,则将其添加到交集并递增两个迭代器。
否则,递增指向最小值的迭代器

两者都应该是O(n)时间,但使用一个普通集应该可以避免计算哈希或因哈希冲突而导致的任何性能下降。

4

2

Aconcagua 5 年前

谢谢Angew,为什么你的方法更快?你能再详细一点吗?

好吧,让我们我为您提供一些其他信息。。。

应该非常清楚的是,无论您使用哪种数据结构,都必须在其中至少一种中迭代所有元素,因此您无法获得比 O(n) , n 数据结构中选定要迭代的元素数。现在最基本的是,您可以多快地使用哈希集在另一个结构中查找元素 std::unordered_set 实际上是,这是 O(1) 至少如果碰撞的次数足够小( “合理均匀分布的哈希” ); 退化情况是所有值都具有相同的键。。。

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