Найти интервалы, которые имеют непустое пересечение с заданным интервалом

Question

Проблема в следующем: у меня есть список intervals, который состоит из кортежей вида (start, end) [с start <= end].Каждый кортеж представляет интервал (реальной строки).Мы предполагаем, что интервалы в intervals не перекрывают друг друга.Учитывая новый интервал (s,e), я хотел бы написать функцию Python, которая проверяет, перекрывает ли (s, e) какой-либо из интервалов в intervals.Если (s, e) имеет непустое пересечение с хотя бы одним из интервалов в intervals, функция должна вернуть индексы этих интервалов в списке intervals.

Скажите, что функция называется find_intersections.Тогда, учитывая, что intervals = [(1, 3.5), (5.5, 8.7), (10.2, 22.6), (22.7, 23.1)], ожидаемые результаты будут:

• find_intersection(intervals, (3.2, 5.)) возврат array([0])
• find_intersection(intervals, (6.1, 7.3)) возврат array([1])
• find_intersection(intervals, (9.1, 10.2)) возвращает No intersection.
• find_intersection(intervals, (5.8, 22.9)) возвращает array([1, 2, 3]).

Код для find_intersection Я написал:

import itertools

def find_intersection(intervals, new_interval):
    _times = sorted(list(itertools.chain.from_iterable(intervals)))
    ind = np.searchsorted(_times, np.asarray(new_interval))
    parity = np.mod(ind, 2)
    if (not np.any(parity)) and ind[1] == ind[0]:
        print('No intersection.')
    elif parity[0] == 1:
        ub = ind[1] if parity[1] == 1 else ind[1] - 1
        return np.arange((ind[0] - 1) / 2, (ub - 1) / 2 + 1)
    elif parity[1] == 1:
        lb = ind[0] if parity[0] == 1 else ind[0] + 1
        return np.arange((lb - 1) / 2, (ind[1] - 1) / 2 + 1)
    else:
        lb = ind[0] if parity[0] == 1 else ind[0] + 1
        ub = ind[1] if parity[1] == 1 else ind[1] - 1
        return np.arange((lb - 1) / 2, (ub - 1) / 2 + 1)

Я считаю,что код выполняет свою работу.

Есть ли более простой / умный способ решения этой проблемы?

Answer 1

Вы можете использовать пакет дерева интервалов *1001*, который предлагает встроенные функции, которые возвращают множество похожих запросов. К сожалению, похоже, что нет функции, которая возвращает индексы перекрывающихся интервалов, а только сами интервалы. Например:

import IntervalTree

intervals = [(1, 3.5), (5.5, 8.7), (10.2, 22.6), (22.7, 23.1)]
tree = IntervalTree.from_tuples(intervals)

tree.search(3.2, 5.) % ~~>   {Interval(1, 3.5)}
tree.search(9.1, 10.2) % ~~> set()
tree.search(5.8, 22.9) % ~~> {Interval(5.5, 8.7), Interval(10.2, 22.6), Interval(22.7, 23.1)}
tree[5.8:22.9] % ~~>         same as above

Как только у вас будет необходимый набор интервалов, вы можете легко вернуть их индексы:

[intervals.index((tr.begin, tr.end)) for tr in tree[5.8:22.9]]

Если список интервалов большой, вы можете вместо этого создать словарь и искать индексы, потому что метод .index требует линейного времени по длине списка.

Хотя установка пакета для решения только этой проблемы, вероятно, является чрезмерной нагрузкой, если вы имеете дело с интервалами, тогда используйте структуру данных дерева интервалов и воспользуйтесь преимуществами базовых оптимизированных методов, написанных в пакете, стоит. Для повышения производительности вы также можете проверить пакет ncls , хотя его документация и методы ограничены.

Надеюсь, это поможет.

Answer 2

i -й интервал в списке перекрывается, если

start[i] < e and s < end[i].

Итак, сортируйте интервалы, увеличивая значения start, затем просматривайте список, пока не найдете первый end[i] > s, и продолжайте до тех пор, пока start[i] < e. Сохраняйте индексы на ходу.

Это принимает O (N Log N) для сортировки, за которым следует Θ (N) наихудший случай для поиска.

---

Если сортировка разрешена, и у вас есть много (s,e) интервалов для проб, может быть полезно найти первый и последний i с помощью дихотомического поиска среди значений start[i] и end[i], а не с помощью линейного поиска , Это уменьшает стоимость с Θ (M + K) до Θ (Log N), где M - средний показатель первого перекрытия (обычно M = O (N)), а K - среднее число перекрытий.

---

Если сортировка не разрешена, вам нужно проверять каждый интервал по очереди на совпадение, используя вышеуказанное условие. Стоимость Θ (N).

Answer 3

Два интервала пересекаются, если

def intersect(i1, i2):
    return max(i1[0], i2[0]) < min(i1[1], i2[1])

Итак, просто понимание списка

def find intersection(intervals, i2):
    return [i1 for i1 in intervals if intersect(i1, i2)]

Answer 4

intervals = [(1, 3.5), (5.5, 8.7), (10.2, 22.6), (22.7, 23.1)]


def find_intersection(intervals, new_interval):
    start, end = new_interval

    return (i for i, (a, b) in enumerate(intervals)
        if (a < start < b) or (a < end < b) or (a > start and b < end))


candidates = ((3.2, 5.), (6.1, 7.3), (9.1, 10.2), (5.8, 22.9))
for c in candidates:
    print(c, "->", list(find_intersection(intervals, c)))