用于产生两个间隔集合的差异的算法

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]两个集合中的相邻interval(),然后遍历第二个树并"碰撞"两个中存在的间隔(细分更大的必要时在第一个树中的间隔).

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

我认为,由于间隔是预先排序的,我可以使用一些动态算法并在一次通过中完成.但是,我不确定这是否可行.

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

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

Answer 1

回想一下我们在学校回来的第一个编程练习 - 写一个计算器程序.从输入行获取算术表达式,解析它并进行评估.还记得跟踪括号的深度吗？所以我们走了.

类比:间隔起点是开括号,终点 - 结束括号.我们跟踪括号深度(嵌套).深度为两个交点的间隔,深度为一个 - 间隔的差异

算法:

Answer 2

您的间隔排序很好.您可以在线性时间内完成此操作,几乎没有内存.

首先"展平"你的两套.这是针对集合A,从最低间隔开始,并组合任何重叠间隔,直到您设置了没有重叠的间隔.然后为B做那个.

现在拿两组,从前两个区间开始.我们将这些称为A和B,Ai和Bi的区间索引.

Ai索引A中的第一个区间,Bi是B中的第一个区间.

虽然有一些间隔要处理,但请执行以下操作:

考虑两个区间的起点,起点是否相同？如果是这样,将两个间隔的起点提前到较小间隔的终点,则不向输出发射任何内容.将较小间隔的索引前进到下一个间隔.(即如果Ai在Bi之前结束,则Ai前进到下一个间隔.)如果两个间隔都在同一个地方结束,则前进Ai和Bi并且不发出任何内容.

一个起点是否早于另一个起点？如果是,则从较早的起始点发出间隔到a)后一个终点的开始,或b)较早结束点的结束.如果选择选项b,则前进预告片间隔的索引.

因此,例如,如果Ai的间隔首先开始,则发出从Ai的开始到Bi的开始或者以Ai为小的结束的间隔.如果Ai在Bi开始之前就结束了,你就会推进艾.

重复直到消耗所有间隔.

PS.我假设您没有备用内存来将两个间隔集平展为单独的缓冲区.这有两个功能.一个"获取下一个间隔"功能,它推进间隔索引,根据需要进行展平,并将展平数据提供给差分函数.

Answer 3

您正在寻找的是Sweep line algorithm。一个简单的逻辑应该会告诉您 Sweep 线何时与 A 和 B 中的一个区间相交，以及它只与一组相交的位置。

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

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