25

问题

假设我有两个区间集合，分别命名为 A 和 B。我如何以最节省时间和内存的方式找到差异（相对补码）？

图片说明： 在此处输入图像描述

区间端点是整数( ≤ 2 128 -1 )，它们总是 2 n长并且在 m×2 n晶格上对齐（所以你可以用它们制作二叉树）。

间隔可以在输入中重叠，但这不会影响输出（如果展平，结果将是相同的）。

问题是因为两个集合中有很多间隔（最多 100,000,000），所以幼稚的实现可能会很慢。

输入是从两个文件中读取的，并以这样一种方式进行排序，即较小的子间隔（如果重叠）按大小顺序紧随其父级之后。例如：

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

我尝试了什么？

到目前为止，我一直在研究一种生成二叉搜索树的实现，同时聚合[0,3],[4,7] => [0,7]来自两个集合的相邻区间 (如有必要，在第一棵树中间隔）。

虽然这似乎适用于小型集合，但它需要越来越多的 RAM 来保存树本身，更不用说完成插入和从树中删除所需的时间了。

我认为由于间隔是预先排序的，我可以使用一些动态算法并一次性完成。但是，我不确定这是否可能。

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

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

4

4 回答 4

9

回想一下我们在学校的第一个编程练习——编写一个计算器程序。从输入行获取算术表达式，对其进行解析和评估。还记得跟踪括号深度吗？所以我们开始吧。

类比：区间起点是左括号，终点是右括号。我们跟踪括号深度（嵌套）。二相交的深度，一差的深度

算法：

  • 无需区分A和B，只需将所有起点和终点按升序排序即可
  • 将括号深度计数器设置为零
  • 遍历端点，从最小的一个开始。如果是起点，则增加深度计数器，如果是终点，则减少计数器
  • 跟踪深度为 1 的区间，即 A 和 B 差异的区间。深度为2的区间为AB交点
于 2012-08-09T22:14:52.327 回答
7

您的间隔已排序，这很棒。您可以在几乎没有内存的情况下在线性时间内完成此操作。

首先“压平”你的两组。即对于集合 A，从最低间隔开始，并组合任何重叠间隔，直到您有一个没有重叠的间隔集。然后为 B 执行此操作。

现在拿你的两组，从前两个间隔开始。我们将这些称为 A 和 B、Ai 和 Bi 的区间指数。

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

虽然有处理时间间隔，但请执行以下操作：

考虑两个区间的起点，起点是否相同？如果是这样，将两个区间的起点提前到较小区间的终点，则不向您的输出发送任何内容。将较小区间的索引推进到下一个区间。（也就是说，如果 Ai 在 Bi 之前结束，则 Ai 前进到下一个区间。）如果两个区间在同一位置结束，则 Ai 和 Bi 都前进并且什么都不发射。

一个起点是否早于另一起点？如果是这样，则发出从较早起点到 a) 较晚端点的起点或 b) 较早终点的终点的间隔。如果您选择选项 b，则将前一区间的索引提前。

因此，例如，如果 Ai 的间隔首先开始，则您发出从 Ai 的开始到 Bi 的开始的间隔，或者 Ai 的结束，以较小者为准。如果Ai 在Bi 开始之前结束，你推进Ai。

重复直到所有时间间隔都用完。

附言。我假设您没有多余的内存来将两个间隔集展平为单独的缓冲区。在两个函数中执行此操作。一个“获取下一个区间”函数，它推进区间索引，根据需要进行展平，并将展平的数据提供给差分函数。

于 2012-08-09T20:25:57.440 回答
5

您正在寻找的是扫描线算法。一个简单的逻辑应该告诉您扫描线何时与 A 和 B 中的一个区间相交，以及它只与一组相交。

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

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

于 2012-08-09T20:26:49.067 回答
2

我认为您应该使用 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]}
于 2012-08-12T12:34:32.383 回答