Python, найдите, если диапазон содержит другой меньший диапазон из списка диапазонов - PullRequest
Новая
       18

Python, найдите, если диапазон содержит другой меньший диапазон из списка диапазонов

0 голосов
/ 23 января 2019

Я ищу эффективный и быстрый способ сделать следующее в Python 3.x.Я открыт для использования сторонних библиотек, таких как Numpy, до тех пор, пока есть производительность.

У меня есть список диапазонов, содержащий сотни тысяч записей.На самом деле это не range (), а номера границ, такие как: 

list_a = [(1, 100), (300, 550), (551, 1999)]

Затем я перебираю более ста тысяч других диапазонов (номеров границ).Я хочу найти, содержат ли они один из существующих диапазонов сверху.Например: 

(0, 600) contains list_a[0] and list_a[1]
(550, 2000) contains list_a[2]
(2000, 2200) does not contain an existing range

Сейчас делаем что-то похожее на следующее, что слишком медленно для больших объемов данных: 

for start, end in get_next_range():
    for r in list_a:
        if r[0] >= start and r[1] <= end:
            # do something
        else:
            # do something else

Любая помощь будет принята с благодарностью!

Ответы [ 2 ]

0 голосов
/ 23 января 2019

Предполагая, что они отсортированы внутри, т. Е. Значения диапазона никогда не бывают (высокие, низкие), это позволит сравнить все элементов в a с всеми элементами в b одновременно:

import numpy as np

list_a = [(1, 100), (300, 550), (551, 1999)]
list_b = [(0, 600), (550, 2000), (2000, 2200), (50, 70)]
a = np.array(a)
b = np.array(b)
comparison = np.logical_and(a[:, 1] >= b[:, 1, None], a[:, 0] <= b[:, 0, None])
idx_a, idx_b = idx = np.nonzero(comparison)
print(a[idx_a])
print(b[idx_b])

array([[   1,  100],
       [ 300,  550],
       [ 551, 1999]])

array([[   0,  600],
       [   0,  600],
       [ 550, 2000]])

Это дает вам интервалы в a, которые содержатся в b.Индексы даны в idx_a и idx_b.

0 голосов
/ 23 января 2019

Я бы сделал это следующим образом, используя numpy: 

import numpy as np
start = 0
finish = 600
lista = np.array([[1,100],[300,550],[551,1999]])
S = lista[:,0]>start
F = lista[:,1]<finish
contains = np.logical_and(S,F)
ind = list(np.flatnonzero(contains))
print(ind) #print [0, 1]

Объяснение: сначала я сделал lista как np.array, затем разделил его на две части: одну с нижней границей ([:,0]) и второй для верхней границы ([:,1]), затем использовали операторы сравнения, получая 1D np.array с bool с.Используя np.logical_an d, я получил один 1D np.array с True s для условия заполнения и False s для отдыха.Наконец, я использовал np.flatnonzero, чтобы получить индексы True с.Это решение предполагает, что все данные в порядке (lowerboundary,upperboundary).Пожалуйста, проверьте, достаточно ли быстрое решение для вашей цели.

...