在Perl中确定范围重叠的最快方法

Question

我有两套范围.每个范围是一对整数(开始和结束),表示单个较大范围的某个子范围.两组范围的结构与此类似(当然......将被实际数字替换).

$a_ranges =
{
  a_1 =>
  {
    start => ...,
    end   => ...,
  },
  a_2 =>
  {
    start => ...,
    end   => ...,
  },
  a_3 =>
  {
    start => ...,
    end   => ...,
  },
  # and so on
};

$b_ranges =
{
  b_1 =>
  {
    start => ...,
    end   => ...,
  },
  b_2 =>
  {
    start => ...,
    end   => ...,
  },
  b_3 =>
  {
    start => ...,
    end   => ...,
  },
  # and so on
};

我需要确定集合A的哪个范围与集合B的哪个范围重叠.给定两个范围,很容易确定它们是否重叠.我只是使用双循环来执行此操作 - 循环遍历外部循环中集合A中的所有元素,循环遍历内部循环中集合B的所有元素,并跟踪哪些元素重叠.

我对这种方法有两个问题.首先,重叠空间非常稀疏 - 即使每组中有数千个范围,我希望集A中的每个范围与集合B中的1或2个范围重叠.我的方法列举了每一种可能性,即矫枉过正.这导致了我的第二个问题 - 它的扩展非常差.当每组中有数百个范围时,代码很快(亚分钟)完成,但是当每组中有数千个范围时,需要很长时间(+/- 30分钟).

有没有更好的方法可以索引这些范围,这样我就不会做那么多不必要的重叠检查？

更新:我正在寻找的输出是两个哈希值(每组范围一个),其中键是范围ID,值是另一组中与该组中给定范围重叠的范围的ID.

Answer 1

这听起来像是间隔树的完美用例,间隔树是专门为支持此操作而设计的数据结构.如果你有两组大小为m和n的区间,那么你可以在时间O(m lg m)中将其中一组构建到一个区间树中,然后在时间O(n lg m + k)中进行n次交叉查询,其中k是您找到的交叉点总数.这给出了O((m + n)lg m + k)的净运行时间.请记住,在最坏的情况下k = O(nm),所以这并不比你拥有的更好,但是对于交叉点数量稀疏的情况,这可能比你拥有的O(mn)运行时间要好得多现在.

我没有太多使用区间树的经验(在Perl中没有经验,对不起!),但从描述看起来它们似乎不应该那么难建立.如果一个人不存在,我会非常惊讶.

希望这可以帮助!