两个集合是否有重叠的最快方法是什么？

Question

两个集合是否有重叠的最快方法是什么？

c++algorithm

5

显然使用std::set_intersection()是浪费时间。算法头文件中没有一个可以直接实现这个功能的函数吗？据我理解，std::find_first_of()执行的是线性搜索。

- user4590120

5

你已经测试过，发现set_intersection对你的需求来说太慢了？ - Borgleader

1

问题不是如何完成这个任务，而是最快的方法。 - user4590120

我看了一下std::set_intersection()的接口，我明白它不可能是最快的方式。这就是为什么对于一个集合来说，set::lower_bound()比std::lower_bound()更快的原因。 - user4590120

4

std::set_intersection() 是线性的，任何对这个问题的快速解决方案也将是线性的。 - QuestionC

1

假设集合实现为位图（在C/C++中它们肯定应该是这样），那么如果 A ^ B != A | B，则集合重叠。 - Lee Daniel Crocker

显示剩余4条评论

4个回答

5

如果输入已排序，您可以使用以下模板函数：

template<class InputIt1, class InputIt2>
bool intersect(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
{
    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2) {
            ++first1;
            continue;
        } 
        if (*first2 < *first1) {
            ++first2;
            continue;
        } 
        return true;
    }
    return false;
}

您可以像这样使用：

#include <iostream>
int main() {
    int a[] = {1, 2, 3};
    int b[] = {3, 4};
    int c[] = {4};
    std::cout << intersect(a, a + 3, b, b + 2) << std::endl;
    std::cout << intersect(b, b + 2, c, c + 1) << std::endl;
    std::cout << intersect(a, a + 3, c, c + 1) << std::endl;
}

结果：

1
1
0

这个函数的复杂度为 O(n + m)，其中 n、m 是输入大小。但是如果一个输入比另一个输入小得多（例如 n << m），最好使用二分查找检查每个 n 元素是否属于另一个输入。这将花费 O(n * log(m)) 的时间。

#include <algorithm>
template<class InputIt1, class InputIt2>
/**
 *  When input1 is much smaller that input2
 */
bool intersect(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) {
    while (first1 != last1)
        if (std::binary_search(first2, last2, *first1++))
            return true;
    return false;
}

- JuniorCompressor

1

两个双精度浮点数容器。一个只包含 +inf，另一个包含 200 万个双精度浮点数（全部小于 +inf）。您的代码执行 200 万次递增操作。如果第一个容器包含一堆负数，然后是 +inf，第二个容器包含一堆正数，则您将遍历两个集合中的每个元素。最好情况下它执行 min(n,m) 次操作，但最坏情况下它执行 n+m 次操作。 - Yakk - Adam Nevraumont

3

不是。考虑 {1, 2, 10}, {3, 4, 5, 6, 7, 8, 9}。 - T.C.

1

无论如何，O(n+m) 都比 O(n*log(m)) 小。 - Bill Lynch

2

@Bill 让 n = 1，m = 十亿。O(n+m)= 十亿零一。O(n lg m)=30。那么，当1000000001再次小于30时，确切的时间是什么？ - Yakk - Adam Nevraumont

1

@AndyG 修复 n 为 1 的情况——当你询问“另一个集合中是否有元素”时。让 m 不断增长。在这种情况下，O(n+m)支配了O(n lg m)。对于任何固定的 n，随着 m 的增长，O(n+m)都支配了O(n lg m)。只有当 n 和 m 都增长时，O(n+m)才会被O(n lg m)和O(m lg n)所支配。多变量复杂性分析的重点在于有时某些值不会增长，而其他常数会增长，有时增长率（变量之间）不是线性的。如果强制所有变量线性增长，则多变量复杂性没有意义。 - Yakk - Adam Nevraumont

显示剩余9条评论

5

有时候，你可以将一组数字编码成一个单独的内存字。例如，你可以将集合{0,2,3,6,7}编码在内存字中：...00000011001101。规则是：如果且仅当数字i在集合中时，从右向左读取的第i位为高位。

现在，如果你有两个集合，它们分别被编码在内存字a和b中，你可以使用按位运算符&执行交集操作。

int a = ...;
int b = ...;
int intersection = a & b;
int union = a | b;  // bonus

这种方法的好处是，交集（并集、补集）可以在一个CPU指令中执行（我不知道这是否是正确的术语）。如果需要处理大于内存字位数的数字，可以使用多个内存字。通常，我使用一个内存字数组。

如果要处理负数，只需使用两个数组，一个用于负数，另一个用于正数。

这种方法的缺点是，它只能处理整数。

- optimusfrenk

这种方法可能不仅适用于整数，至少如果我们将问题扩展到包括概率解决方案的话。例如，可以对元素进行哈希（这些元素可能是任意字符串），以确定要设置哪个位，类似于布隆过滤器。我最近一直在思考这些方面。 - Dave Dopson

0

我觉得你可以做一个二分查找

#include <set>
#include <iostream>
#include <algorithm>

bool overlap(const std::set<int>& s1, const std::set<int>& s2)
{
    for( const auto& i : s1) {
        if(std::binary_search(s2.begin(), s2.end(), i))
            return true;
    }
    return false;
}

int main()
{
    std::set<int> s1 {1, 2, 3};
    std::set<int> s2 {3, 4, 5, 6};

    std::cout << overlap(s1, s2) << '\n';
}

- Loreto

4

哇，你已经有两个集合了，而且还能想出二次算法。std::set迭代器是双向迭代器，不是随机访问迭代器，所以使用std::binary_search没有任何意义。只需要使用s2.count(i)即可。 - roman-kashitsyn

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yakk - Adam Nevraumont · Accepted Answer

这是一个只针对std::set（或多个）的解决方案。对于map，需要稍微多做一些工作。

我尝试了三种方法。

首先，如果其中一个集合远大于另一个，则我会查找另一个集合中的所有元素。然后反过来。

常量100在理论上是错误的。对于最佳Big-O性能，应该是k n lg m > m而不是100 n > m，但是常数因子很大，并且100>lg m，所以你应该进行实验。

如果不是这种情况，我们将遍历每个集合，寻找碰撞，就像set_intersection一样。我们使用.lower_bound而不是仅使用++来尝试更快地跳过每个列表。

请注意，如果您的列表由交错元素组成（例如{1,3,7}和{0,2,4,6,8}），则这将比仅使用++慢一个对数因子。

如果两个集合相互“交叉”得较少，则可以跳过每个集合的大量内容。

如果要比较两种行为，请用简单的++替换lower_bound部分。

template<class Lhs, class Rhs>
bool sorted_has_overlap( Lhs const& lhs, Rhs const& rhs ) {
  if (lhs.empty() || rhs.empty()) return false;
  if (lhs.size() * 100 < rhs.size()) {
    for (auto&& x:lhs)
      if (rhs.find(x)!=rhs.end())
        return true;
    return false;
  }
  if (rhs.size() * 100 < lhs.size()) {
    for(auto&& x:rhs)
      if (lhs.find(x)!=lhs.end())
        return true;
    return false;
  }

  using std::begin; using std::end;

  auto lit = begin(lhs);
  auto lend = end(lhs);

  auto rit = begin(rhs);
  auto rend = end(rhs);

  while( lit != lend && rit != rend ) {
    if (*lit < *rit) {
      lit = lhs.lower_bound(*rit);
      continue;
    }
    if (*rit < *lit) {
      rit = rhs.lower_bound(*lit);
      continue;
    }
    return true;
  }
  return false;
}

一个已排序的数组可以使用第三种算法选择，并使用std::lower_bound来快速推进“其他”容器。这样做的优点是使用部分搜索（在set中无法快速执行）。与天真的++相比，它也会在“交错”元素上表现不佳（以对数n的因素）。

前两个也可以通过已排序的数组快速完成，将方法调用替换为std中的算法调用。这样的转换基本上是机械的。

在已排序的数组上渐近最优的版本将使用二进制搜索偏向于找到列表开头的下限--在1、2、4、8等处进行搜索，而不是在一半、四分之一等处进行搜索。请注意，这具有相同的lg(n)最坏情况，但如果要搜索的元素是first，则为O(1)，而不是O(lg(n))。由于这种情况（搜索进度较少）意味着全局进度较小，因此优化子算法可获得更好的全局最坏速度。

要理解为什么，在“快速交替”时，它不会表现得比++差--下一个元素是符号交换的情况需要O(1)操作，并且如果间隔较大，则将O(k)替换为O(lg k)。

然而，到了这个地步，我们已经深入了一个优化洞。在继续这种方式之前，请进行性能分析并确定是否值得。

另一种在已排序的数组上的方法是假定std::lower_bound是最优的（在随机访问迭代器上）。使用一个输出迭代器，如果写入则抛出异常。当您捕获该异常时返回true，否则返回false。

（上面的优化--选择其中一个并二分搜索另一个，以及指数级增长搜索--可能对std::set_intersection合法。）

我认为使用3种算法很重要。在一个较小的一侧进行集合交集测试可能是常见的：一个元素在一侧，另一侧有许多元素的极端情况非常出名（作为搜索）。通过检测两侧之间的不对称性，在适当的时候切换到“小线性，大对数”的模式，并在这些情况下获得更好的性能。O(n+m)与O(m lg n)--如果m < O(n/lg n)，则第二个胜过第一个。如果m是一个常数，那么我们得到O(n) vs O(lg n)--这包括“使用函数找出单个元素是否在某个大集合中”的边缘情况。