2

我花了相当多的时间为我的一个应用程序编写 Baeza-Yates 的快速集合交集算法。虽然我在 STL set_intersect 上做的稍微好一点，但在对输出进行排序后，我从实现自己的算法中获得的任何时候都需要对结果集进行排序这一事实被删除。鉴于 STL set_intersect 表现良好，任何人都可以指出它实际实现的算法吗？或者它是否实现了相同的 Baeza-Yates 算法，但只是以更有效的方式？

Baeza-Yates：http ://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.7899&rep=rep1&type=pdf

4

3 回答 3

3

STL 不需要任何特定的算法，它只是对某些操作的算法复杂性设置约束。由于它都是基于模板的，因此您可以轻松查看特定实现的源代码以了解它是如何工作的。

于 2010-10-27T04:56:31.423 回答
2

至少在我看过的实现中，实现相当简单——按照这个一般顺序：

template <class inIt, class outIt>
outIt set_intersection(inIt start1, inIt end1, inIt start2, inIt end2, outIt out) {
    while (start1 != end1 && start2 != end2) {
       if (*start1 < *start2)
           ++start1;
       else if (*start2 < *start1)
           ++start2;
       else {                 // equal elements.
           *out++ = *start1;
           ++start1;
           ++start2;
       }
    }
    return out;
}

当然，我只是在脑海中打出这个——它甚至可能无法编译，而且肯定不是迂腐正确的（例如，可能应该使用比较器函数而不是operator<直接使用，并且应该有另一个模板参数以允许 start1/end1 与 start2/end2 不同）。

然而，从算法的角度来看，我猜大多数实际的实现都和上面差不多。

于 2010-10-27T05:23:46.777 回答
0

有趣的。因此，算法中的比较次数与两组中的元素数量呈线性比例关系。Baeza-Yates 算法是这样的（注意它假设两个输入集都是排序的）：

1）求集合A的中位数（这里A是较小的集合） 2）求A在B中的中位数，如果找到，加到结果中，否则，中位数在B中的插入秩是已知的。3) 将集合 A 的中位数拆分为两部分，将集合 B 的插入秩拆分为两部分，并在两部分上递归重复该过程。此步骤有效，因为 A 中小于中位数的所有元素只会与 A 在 B 中的中位数插入秩之前的元素相交。

由于您可以使用二进制搜索来定位 A 在 B 中的中位数，显然，该算法中的比较次数低于您提到的比较次数。事实上，在“最好”的情况下，比较的次数是 O(log(m) * log(n))，其中 m 和 n 是集合的大小，而在最坏的情况下，比较的次数是O(m + n)。我到底是怎么把实现搞得这么糟糕的？:(

于 2010-10-28T18:22:29.350 回答