快速集重叠匹配算法

Question

假设我有两套：

A = [1, 3, 5, 7, 9, 11]

和

B = [1, 3, 9, 11, 12, 13, 14]

这两个集合都可以是任意的(以及不同数量的元素)。

我正在编写一个性能关键的应用程序，它要求我执行搜索以确定这两个集合具有共同之处的元素的数量。我实际上不需要返回匹配，只需要返回匹配的数量。

显然，一种天真的方法会是一种蛮力，但我怀疑这并不是最优的方法。是否有执行这种操作的算法？

如果有帮助，在任何情况下，集合都将由整数组成。

Answer 1

如果两个集合大小大致相同，则同步遍历它们(类似于合并排序合并操作)的速度与其速度相当。

看第一个元素。

如果它们匹配，则将该元素添加到结果中，并向前移动两个指针。

否则，将指向最小值的指针向前移动。

一些伪Python：

a = []
b = []
res = []
ai = 0
bi = 0
while ai < len(a) and bi < len(b):
    if a[ai] == b[bi]:
        res += a[ai]
        ai+=1
        bi+=1
    elif a[ai] < b[bi]:
      ai+=1
    else:
      bi+=1
return res

如果其中一组明显大于另一组，则可以使用二进制搜索从较大的项中的较小项中查找每个项。

Answer 2

这是一个想法(非常高层次的描述)。

顺便说一句，我冒昧地假设，每组中的数字不会出现超过一次，例如，1,3,5,5,7,7,9,11不会发生。

您定义了两个变量，用于保存每个数组中正在检查的索引。

从每组的第一个数开始，比较它们。有两个可能的条件:它们是相等的，或者一个比另一个大。

如果它们相等，则计算事件并将两个数组中的指针移动到下一个元素。

如果它们不同，则将较低值的指针移动到数组中的下一个元素，并重复处理(比较这两个值)。

当到达任何数组的最后一个元素时，循环就结束了。

希望我能清楚地解释这件事。

Answer 3

如果对两个集合进行排序，则两个集合的最小元素要么是第一个集合的最小元素，要么是第二个集合的最小元素。如果是第一组的最小值，那么下一个最小的元素要么是第二组的最小值，要么是第一组的第二个最小值。如果您重复到这两个集合的末尾，您已经订购了两个集合。对于您的具体问题，只需比较元素是否也相等。

您可以使用以下算法迭代两个集合的合并：

intersection_set_cardinality(s1, s2)
{
   iterator i = begin(s1);
   iterator j = begin(s2);

   count = 0;
   while(i != end(s1) && j != end(s2))
   { 
       if(elt(i) == elt(j))
       {
            count = count + 1;
            i = i + 1;
            j = j + 1;
       }
       else if(elt(i) < elt(j))
       {
           i = i + 1;
       }
       else
       {
           j = j + 1;           
       }
   }
   return count
}