У меня есть два набора диапазонов. Каждый диапазон представляет собой пару целых чисел (начало и конец), представляющих некоторый поддиапазон одного большего диапазона. Два набора диапазонов имеют структуру, подобную этой (конечно, ... будут заменены фактическими числами).
$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 до перекрытия может быть с 1 или 2 диапазонами из набора B. Мой подход перечисляет каждую отдельную возможность, которая излишество. Это приводит ко второй моей проблеме - к тому, что она очень плохо масштабируется. Код завершается очень быстро (менее минуты), когда в каждом наборе сотни диапазонов, но занимает очень много времени (+/- 30 минут), когда в каждом наборе тысячи диапазонов.
Есть ли лучший способ индексировать эти диапазоны, чтобы я не делал так много ненужных проверок на перекрытие?
Обновление : вывод, который я ищу, - это два хэша (по одному для каждого набора диапазонов), где ключи - это идентификаторы диапазонов, а значения - идентификаторы диапазонов из другого набора, которые перекрываются с заданным диапазоном в этом наборе.