Python，查找范围是否包含范围列表中的另一个较小范围

Question

我正在寻找一种有效和快速的方法来在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

任何帮助将非常感激！

Answer 1

我会按照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]），然后使用比较运算符，获得np.arrays的1D bools。使用np.logical_and我得到单个1D np.array与Trues用于完全填充状态和Falses用于休息。最后我使用np.flatnonzero来获得Trues的指数。此解决方案假定所有数据均为(lowerboundary,upperboundary)顺序。请检查该解决方案是否足够快，以满足您的需求。

Answer 2

假设它们在其中排序，即范围值从不（高，低），这将同时将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]])

这为您提供了b中包含的间隔。这些指数在idx_a和idx_b中给出。