1

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

我有 2 个输入文件，一个包含多行范围和数据对，另一个包含要查找交点的范围列表。

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

目前我正在做的是暴力破解，将数据列表中的每个范围与交集列表中的每个其他范围进行比较，但是由于数据文件非常大，因此需要很长时间。

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

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);
}

为清楚起见进行编辑：

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

4

4 回答 4

1

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

对数据和范围进行排序并按顺序处理它们可以立即提高性能，因为测试一个以 100 开头的范围与另一个以 50 结尾的范围是没有意义的。

另一个改进是“压缩”范围。如果您有 (1-10)、(10-20)、(20-30) 等范围，那么您可以轻松地将它们替换为单个 (1-30) 范围，并减少测试次数。您可以创建一个适当的 AggregateRange 类来跟踪其组成范围的身份，以防您仍然想知道哪个原始范围导致重叠。

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

这种改进背后的基本思想是将任何未经测试的数据范围的开始推进到并包括最后一个非重叠数据范围的结束。如果新的开始超过它自己的结束，则不需要测试，因为它不重叠。这意味着非重叠 (1-20) 应将未经测试的 (10-100) 转换为未经测试的 (20-100)。这可能难以实现，因此请注意不要过度使用。

于 2013-01-16T21:03:43.300 回答
1

检查我的理解是否正确：

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

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

将范围分割成2个对象，表示EndPoint：值（，标记是数据，还是要查询的范围）。intbooleanEndPointnullEndPointint

将EndPoint两个范围列表中的所有 s 放在一起，按值对它们进行排序，通过将 start 放在 end 端点前面（如果您认为 touch 是交集）来打破平局。排序步骤的复杂度为 O((m + n)log(m + n))。

EndPoint根据这个伪代码循环遍历排序的 s：

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)

从 HashSet 中添加和删除是摊销 O(1)。问题在于打印交叉点，即 O(k)，其中 k 是交叉点的数量，在最坏的情况下可能高达 O(m * n)。

综合起来，在最坏的情况下，复杂度为 O((m + n)log(m + n) + m * n)。根据数据的属性，您也许可以做得更好。这是一个非常通用的解决方案。

于 2013-01-16T22:03:48.257 回答
0

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

一种选择是创建一个从 min(startTime) 到 max(endTime) 的数组，并在每个位置存储对覆盖该范围的输入值的引用。

因此，如果您的输入是
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 并将结果连接起来。

如果您只关心是否存在交叉路口，而不是确切的路口所在的位置，则可以进一步提高速度。或者，如果您只关心一个十字路口，而不是所有十字路口。

于 2013-01-16T21:06:31.513 回答
0

您可以对每个范围列表进行排序 o(N ln N) 并执行这些范围 O(N) 的合并排序

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

于 2013-01-16T21:34:10.213 回答