两个向量的集合交集的有效或快速大小

Question

我发现自己需要返回两个向量的交集大小:

std::vector<int> A_, B_

我不需要相交的值,只需要集合的大小.这个功能需要被调用很多次.这是对(数学)图形/网络进行更大模拟的一部分.

我的工作条件是:

• 容器是载体.改变它们是纯粹的痛苦,但如果获得保证肯定会这样做.
• A_和B_的大小具有~100的上限.但往往要小得多.
• A_和B_的元素表示取自{1,2,...,M}的样本,其中M> 10,000.
• 通常,A_和B_具有相似但不相等的大小.
• 两个向量都是无序的.
• 作为"更大模拟"的一部分,A_和B_的内容发生变化.
• 每个向量仅包含唯一元素,即不重复.

我的第一次尝试,使用一个天真的循环,在下面.但我认为这可能还不够.我假设......由于重复的排序和分配,std :: set_intersection将过于繁重.

   int vec_intersect(const std::vector<int>& A_, const std::vector<int>& B_) {

      int c_count=0;

  for(std::vector<int>::const_iterator it = A_.begin(); it != A_.end(); ++it){
     for(std::vector<int>::const_iterator itb = B_.begin(); itb != B_.end(); ++itb){

      if(*it==*itb) ++c_count;
     }
  }

  return c_count;
}

鉴于我的上述条件,我还能如何实现这一点以获得速度,相对容易？我应该考虑哈希表还是使用排序和STL,或者不同的容器？

Answer 1

您的算法的元素数量为O(n ²)(假设两个向量的大小大致相等n).这是一个O(n)算法:

• 创建一个 std::unordered_set<int>
• 将所有向量项A放入集合中
• 浏览向量的所有项目B,检查它们是否存在于其中unordered_set,并递增每个项目的计数.
• 返回最终计数.

这是C++ 11中的一个实现,使用lambda简洁:

vector<int> a {2, 3, 5, 7, 11, 13};
vector<int> b {1, 3, 5, 7, 9, 11};
unordered_set<int> s(a.begin(), a.end());
int res = count_if(b.begin(), b.end(), [&](int k) {return s.find(k) != s.end();});
// Lambda above captures the set by reference. count_if passes each element of b
// to the lambda. The lambda returns true if there is a match, and false otherwise.

(这个打印4; 演示)