如何在Java中高效地查找两个范围列表中的所有重叠

Question

我在有效地查找两个列表中的所有重叠范围时遇到问题
这个问题类似于This问题，但输入不同

我有两个输入文件，一个包含许多行范围和数据对，另一个包含一个范围列表，以查找到的交点

我已经编写了一个文件读取器类，它从数据文件中读取数据，一次返回一个对象，该对象包含范围和数据对的列表，但是当我试图查找两个范围列表的重叠时遇到了麻烦

目前我所做的是强制执行，将数据列表中的每个范围与交叉点列表中的每个其他范围进行比较，但由于数据文件非常大，因此需要花费很长时间

示例对象：
这是数据列表中的对象：

public DataModel {
    private int start; {set; get;}
    private int end; {set; get;}
    //Other Data
}

范围模型只是成对整数（开始、结束）的列表

while (fileParser.hasNext()) {
    dataList = fileParser.next();
    for (DataModel data : dataList)
        for (RangeModel range : rangeList)
            if(overlaps(data, range))
                print(range.getString + " " + data.getString);
}

为清晰起见，请编辑：

数据模型以较小的数据包形式给出，这些数据包具有不同长度的相似范围，但它们大多在20以下，因此将在相同的RangeModel和每个新的数据模型上重复进行比较。所有数据的总范围约为20亿，但这并不重要。谢谢你的帮助

Answer 1

检查我的理解是否正确：

• DataModel和RangeModel表示范围。（数据模型可能包含更多的数据，但它与此无关）
• 大约有200万个DataModel和少量RangeModel（不过，我的解决方案没有利用这种不对称性）
• 有必要将数据模型中的范围保留为不同的实体，即使它们是重叠的。（如果您只对交叉点感兴趣，则可以在距离较近时折叠这些范围作为优化）

我将要描述的方法可以在两个范围列表之间进行范围交集，而不管范围看起来如何（重叠、大范围等）。限制是两个范围列表的大小之和（排序是瓶颈），以及找到的范围数（遍历是瓶颈）

将范围拆分为2EndPoint个对象，这表示：值（int）、范围的开始或结束（boolean）、开始EndPoint对象（null在范围的开始；如果范围结束，则指向表示范围开始的EndPoint对象）、标记（int，标记它是数据还是要查询的范围）

将所有的{{CD3}}s从两个范围的列表中放在一起，按值排序，通过在结束端点前放置开始（如果考虑触摸是相交），则使用Type Stand。排序步骤的复杂度为O（（m+n）log（m+n））

根据以下伪代码循环经过排序的EndPoint：

open_data = HashSet()
open_range = HashSet()

for e in endpoints:
  if e is start of range:
    if e is data:
      print e intersect with all in open_range
      open_data.add(e)
    else: // e is range to test
      print e intersect with all in open_data
      open_range.add(e)
  else: // e is end of range
    if e is data:
      open_data.remove(e.startPoint)
    else: // e is range to test
      open_range.remove(e.startPoint)

哈希集的添加和删除按O（1）摊销。问题在于打印交叉点，即O（k），其中k是交叉点的数量，在最坏的情况下可能会达到O（m*n）

综合起来，最坏情况下的复杂度是O（（m+n）log（m+n）+m*n）。根据数据的属性，您可能会做得更好。这是一个非常普遍的解决办法

Answer 2

我可以想到不同的优化，但它们取决于您希望在检查后获得什么样的数据

对数据和范围进行排序并按顺序进行处理可以立即提高性能，因为将一个从100开始的范围与另一个以50结束的范围进行比较是没有意义的

另一个改进是“压缩”范围。如果您有（1-10）、（10-20）、（20-30）这样的范围，那么您可以很容易地将它们替换为单个（1-30）范围，并减少测试的数量。您可以创建一个appropiate AggregateRange类，该类跟踪其组成范围的标识，以防您仍然想知道是哪个原始范围导致了重叠

另一个改进是在处理数据列表时巧妙地使用以前的结果。例如：假设您测试的数据范围（1-10）恰好不重叠。如果下一个测试数据范围为（2-8），则不需要根据这些范围对其进行测试，因为之前的结果保证它不会重叠

这一改进背后的基本思想是将任何未测试数据范围的开始提前到并包括最后一个非重叠数据范围的结束。如果新起点超过其自身终点，则无需进行测试，因为它不会重叠。 这意味着非重叠（1-20）应该将未测试（10-100）转换为未测试（20-100）。这可能更难实现，所以要小心，不要做得过火

Answer 3

您可以对每个范围列表进行排序o（N ln N）并对这些范围执行合并排序o（N）

这将以最短的CPU时间显示任何重叠的范围

Answer 4

理想的解决方案将取决于数据的特定特征，但对两个输入集进行排序将是一个良好的第一步，这将允许您减少所需的比较量

一个选项是创建一个从最小值（开始时间）到最大值（结束时间）的数组，并在每个位置存储对覆盖此范围的输入值的引用

因此，如果您的输入是
A:[1-5]和B:[3-7]，您可以有一个如下的数据结构

1: A
2: A
3: A,B
4: A,B
5: A,B
6: B
7: B

然后，为了测试[2-4]与数据集的交集，只需在数组列表中查找2,3,4并连接结果

如果你只关心是否有交叉口，而不是交叉口到底是谁，那么可以进一步提高速度。或者如果你只关心一个十字路口，而不是所有的十字路口