Найти, является ли интервал / диапазон частью более длинного интервала / диапазона - PullRequest
Новая
       9

Найти, является ли интервал / диапазон частью более длинного интервала / диапазона

1 голос
/ 10 октября 2019

У меня есть отсортированный массивный двумерный массив x с комбинацией начальной и конечной позиций двух интервалов в каждой строке: 

[[x_start_1, x_end_1, y_start_1, y_end_1],
 [x_start_2, x_end_2, y_start_2, y_end_2],
 ...
 [x_start_n, x_end_n, y_start_n, y_end_n]]

Массив упорядочен по убыванию на длину от x_start_n доx_end_n. Длина x и y интервалов из одной и той же строки всегда одинакова.

Вопрос в том, что было бы наиболее эффективным и хорошим решением для поиска, если интервалы x и yв данной строке есть подинтервалы любых x и y интервалов из любой из строк выше?

Пример: 

array([[35, 39,  1,  5],
       [20, 24,  4,  8],
       [32, 36, 10, 14],
       [35, 38,  1,  4], --> TRUE
       [35, 38, 21, 24],
       [19, 22,  2,  5],
       [36, 39,  2,  5], --> TRUE
       [20, 23,  4,  7], --> TRUE
       [      ...     ]])

Единственное решение, которое я могу придумать иЯ реализовал создание двойного цикла for, расширение списка допустимых строк и использование его на следующей итерации для сравнения.

Для упрощения визуализации: 

1.      ---------    |         ---------
2.    -----          |           -----
3.        ---        |            ---          -> TRUE
4.             --    |                --       -> TRUE

Спасибо за вашу помощь! <3 </p>

1 Ответ

0 голосов
/ 10 октября 2019

Вот векторизованный способ усиления broadcasting - 

m1 = x[:,0,None]<=x[:,0]
m2 = x[:,1,None]>=x[:,1]

m3 = x[:,2,None]<=x[:,2]
m4 = x[:,3,None]>=x[:,3]

m12 = m1 & m2
m34 = m3 & m4
out = np.triu((m12 & m34),1).any(0)

Пример ввода, вывода - 

In [2]: x
Out[2]: 
array([[35, 39,  1,  5],
       [20, 24,  4,  8],
       [32, 36, 10, 14],
       [35, 38,  1,  4],
       [35, 38, 21, 24],
       [19, 22,  2,  5],
       [36, 39,  2,  5],
       [20, 23,  4,  7]])

In [3]: out
Out[3]: array([False, False, False,  True, False, False,  True,  True])
...