範囲は2セットあります。各範囲は、単一のより大きな範囲のサブ範囲を表す整数のペア（開始と終了）です。2セットの範囲は、これと同様の構造になっています（もちろん、...は実際の数値に置き換えられます）。
$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のどの範囲とオーバーラップするかを判断する必要があります。2つの範囲が与えられると、それらがオーバーラップするかどうかを簡単に判断できます。私はこれを行うために単にダブルループを使用しています-外側のループのセットAのすべての要素をループし、内側のループのセットBのすべての要素をループし、どの要素がオーバーラップしているかを追跡します。
このアプローチには2つの問題があります。まず、オーバーラップスペースが非常にまばらであるということです。各セットに数千の範囲がある場合でも、セットAの各範囲がセットBの1つまたは2つの範囲とオーバーラップすると予想されます。私のアプローチでは、すべての可能性を列挙します。やり過ぎ。これは私の2番目の問題につながります-それが非常に不十分にスケーリングするという事実。各セットに数百の範囲がある場合、コードは非常に速く（1分未満）終了しますが、各セットに数千の範囲がある場合、非常に長い時間（+/- 30分）かかります。
これらの範囲にインデックスを付けて、重複について不必要なチェックをあまり行わないようにするためのより良い方法はありますか？
更新：私が探している出力は2つのハッシュ（範囲の各セットに1つ）で、キーは範囲IDであり、値はこのセットの特定の範囲と重複する他のセットの範囲のIDです。