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

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

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

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

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

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

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