c++ - 找出两组是否重叠的最快方法？

Question

显然执行 std::set_intersection() 是浪费时间。 算法头中没有一个函数可以做到这一点吗？ 据我所知，std::find_first_of() 正在进行线性搜索。

Answer 1

这是一个仅适用于 std::set(或 multi)的解决方案。 map 的解决方案只需要多一点工作。

我尝试了 3 种方法。

首先，如果一个比另一个大得多，我只需在另一个中寻找一个的所有元素。反之亦然。

常量 100 在理论上是错误的。它应该是 k n lg m > m 对于一些 k，而不是 100 n > m 以获得最佳的 big-O 性能:但是常数因子很大，并且 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 中快速执行)。与原始的 ++ 相比，它在“交错”元素上的表现也很差(按 log n 因子)。

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

排序数组的渐近最优版本将使用偏向于在列表开头查找下界的二分搜索——在 1、2、4、8 等处搜索，而不是在一半、四分之一等处搜索。注意这具有相同的 lg(n) 最坏情况，但如果搜索的元素是 第一个 而不是 O(lg(n))，则为 O(1)。由于这种情况(搜索进展较少)意味着全局进展较少，针对这种情况优化子算法可为您提供更好的全局最坏情况速度。

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

但是，到目前为止，我们已经远远超出了一个优化漏洞:配置文件，并在继续这样做之前确定它是否值得。

---

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

(上面的优化——选择一个然后对另一个进行 bin 搜索，以及指数前进搜索——对于 std::set_intersection 可能是合法的。)

---

我认为使用3种算法很重要。在一侧比另一侧小得多的情况下设置交集测试可能很常见:一个元素在一侧，而另一侧有许多元素的极端情况是众所周知的(作为搜索)。

在这种常见情况下，朴素的“双线性”搜索可为您提供线性性能。通过检测两侧之间的不对称性，您可以在适当的时候切换到“小线性，大登录”，并在这些情况下获得更好的性能。 O(n+m) vs O(m lg n) - 如果 m < O(n/lg n) 第二个打败第一个。如果 m 是一个常数，那么我们得到 O(n) vs O(lg n) —— 这包括“使用函数来查找单个元素是否在某个大型集合中”的边缘情况。