c++ - 两个 vector 的集合交集的高效或快速大小

Question

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

std::vector<int> A_, B_

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

我的工作条件是:

• 容器是载体。改变它们是纯粹的痛苦，但如果 yield 值得的话，肯定会这样做。
• A_ 和 B_ 的大小上限为 ~100。但往往很多更小。
• A_ 和 B_ 的元素表示从 {1,2,...,M} 中提取的样本，其中 M >10,000。
• 一般来说，A_ 和 B_ 的大小相似但不相等。
• 两个 vector 都是无序的。
• A_ 和 B_ 的内容发生变化，作为“更大模拟”的一部分。
• 每个 vector 仅包含唯一元素，即没有重复。

我的第一次尝试，使用一个简单的循环，如下所示。但我认为这可能还不够。我假设...由于重复排序和分配，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²)(假设两个 vector 的大小约等于 n )。这是一个 O(n) 算法:

• 创建一个 std::unordered_set<int>
• 放入 vector 的所有项A进入集合
• 遍历 vector 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 ; demo )