我有两组范围。每个范围都是表示某个单独的较大范围的子范围的一对整数（起始和结束）。两组范围的结构类似于这样（当然，...s将被实际数字替换）。
$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。