生成两个区间集合差的算法

Question

问题

假设我有两个区间的集合，命名为A和B。如何以最高效的时间和内存找到它们之间的差异（相对补集）？

下面是一个示意图：

区间端点是整数（≤ 2¹²⁸-1），它们总是2ⁿ长，并且在m×2ⁿ的网格上对齐（因此您可以用它们创建二叉树）。

输入数据中的区间可能会重叠，但这不会影响输出结果（平坦化后的结果相同）。

问题在于两个集合都包含许多区间（多达100,000,000个），因此朴素的实现可能会很慢。

输入从两个文件读取，并按照某种方式排序，使得较小的子区间（如果重叠）紧随其父级以大小顺序出现。例如：

[0,7]
[0,3]
[4,7]
[4,5]
[8,15]
...

我尝试了什么？

到目前为止，我一直在开发一个生成二叉搜索树的实现，同时聚合两个集合中邻近的区间（[0,3]，[4,7] => [0,7]），然后遍历第二棵树并“挤出”同时存在于两个树中的区间（如果必要，将在第一个树中分割更大的区间）。

虽然对小集合似乎有效，但需要越来越多的RAM来保留树本身，更不用说需要完成从树中插入和删除所需的时间。

我想到既然区间预先排序，就可以使用某些动态算法，并在一次扫描中完成。但我不确定这是否可能。

---

那么，如何以高效的方式解决这个问题呢？

免责声明：这不是作业，而是我面临的实际问题的修改/概括。我正在使用C++进行编程，但我可以接受任何[命令式]语言的算法。

- user267885

---

怎么样使用简单的线性单次搜索呢？看起来需要更少的内存，特别是如果你一次只存储一个区间对。 - user529758

+1，@H2CO3。我觉得这个问题有点类似于查找两个已排序数组的交集，因此线性搜索可能可以应用在这里。 - Kevin

@Kevin 是的，基本上我只是考虑KISS，而B树似乎有点过于繁琐。 - user529758

@H2CO3 是的，这正是我想到的，但问题是这些区间不一定是完全匹配的，而只是彼此之间的子区间。 - user267885

也许你可以进行第一次遍历，其中舍弃或合并所有子间隔。 - Kevin

Answer 1

回想一下我们在学校里做的第一个编程练习——编写一个计算器程序。从输入行中获取算术表达式，解析并计算。还记得如何跟踪括号深度吗？接下来就是这个问题。

类比：区间起点为左括号，终点为右括号。我们跟踪括号深度（嵌套层数）。深度为2的交集为两个区间的交集，深度为1的差集为A和B区间的差集

算法：

• 不需要区分A和B，只需按升序排序所有起点和终点
• 将括号深度计数器设置为零
• 从最小的终点开始迭代，如果它是起点，则增加深度计数器；如果它是终点，则减少计数器
• 跟踪深度为1的区间，这些是A和B区间的差集。深度为2的区间是AB的交集

- Arik G

---

这是一个很棒的解决方案！我需要为A和B分别维护两个计数器，因为多个区间可能会在两者中重叠，而我希望它们只计数一次。不过除此之外，我可以在一次遍历中计算A ∩ B，A - B，B - A 和 A ∪ B！ - user267885

我只想补充一点，深度！= 0表示联合。 - Roman Reiner

除非我理解错误，否则这并不是差异，只是异或运算。如果存在一个区间在A中不存在但存在于B中，则深度为1将得出它。 - Alex Beals

是的，“A而不B”的线段不是由简单的深度=1深度给出的。 - MattArmstrong

Answer 2

你的区间已经排好序了，这很好。你可以在几乎没有内存消耗的情况下用线性时间完成这项工作。

首先“压缩”你的两个集合。对于集合A，从最低区间开始，将任何重叠的区间组合在一起，直到得到一个没有重叠的区间集。然后对B也做同样的操作。

现在，取出你的两个集合，并从第一和第二个区间开始。我们分别称这些为A和B的区间索引，Ai和Bi。

其中，Ai是A中的第一个区间索引，Bi是B中的第一个区间索引。

当还有区间需要处理时，请执行以下步骤：

考虑两个区间的起点，这些起点是否相同？如果相同，请将两个区间的起点都推进到较小区间的终点处，将不会向输出中发出任何内容。将较小区间的索引推进到下一个区间。（即如果Ai在Bi之前结束，则Ai推进到下一个区间。）如果两个区间在同一位置结束，则同时将Ai和Bi推进，并且不发出任何内容。

是否有一个起点比另一个起点更早？如果是这样，请发出从较早起点到较晚终点的区间，或者是从较早终点到较晚终点。如果选择b选项，请将较早区间的索引推进。

例如，如果Ai处的区间开始最早，则发出从Ai起始位置到Bi起始位置或Ai结束位置中小的那个位置的区间。如果Ai在Bi的起始位置之前结束，则推进Ai。

重复执行，直到所有区间都被消耗完。

注：我假设你没有多余的内存来将两个区间集压缩成单独的缓冲区。因此需要使用两个函数分别完成这一过程。一个“获取下一个区间”的函数可推进区间索引并在必要时完成压缩，另一个函数负责将压缩后的数据传递给差异化函数。

- Rafael Baptista

Answer 3

你需要的是一个扫描线算法。一种简单的逻辑可以告诉你，当扫描线在A和B的区间中相交，以及它在其中一个集合中相交的位置。

这非常类似于这个问题。只需考虑您有一组通过B段端点的垂直线。

该算法复杂度为O((m+n) log (m+n))，这是初始排序的成本。对排序后的集合进行扫描线算法需要O(m+n)。

- Samy Arous

Answer 4

我认为你应该使用boost.icl（区间容器库）http://www.boost.org/doc/libs/1_50_0/libs/icl/doc/html/index.html。

#include <iostream>
#include <boost/icl/interval_set.hpp>

using namespace boost::icl;

int main()
{
  typedef interval_set<int> TIntervalSet;
  TIntervalSet intSetA;
  TIntervalSet intSetB;

  intSetA += discrete_interval<int>::closed( 0, 2);
  intSetA += discrete_interval<int>::closed( 9,15);
  intSetA += discrete_interval<int>::closed(12,15);

  intSetB += discrete_interval<int>::closed( 1, 2);
  intSetB += discrete_interval<int>::closed( 4, 7);
  intSetB += discrete_interval<int>::closed( 9,10);
  intSetB += discrete_interval<int>::closed(12,13);

  std::cout << intSetA << std::endl;
  std::cout << intSetB << std::endl;

  std::cout << intSetA - intSetB << std::endl;

  return 0;
}

这将会打印出来

{[0,2][9,15]}
{[1,2][4,7][9,10][12,13]}
{[0,1)(10,12)(13,15]}

- Industrial-antidepressant

---

不错的解决方案，我之前不知道ICL。然而，这似乎是在RAM中运行，所以它并不能真正扩展到数亿个间隔。 - user267885