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]) 然后使用比较运算符，得到 1D np.arrays of bools .使用 np.logical_and 我得到了单个 1D np.array，其中 True 用于 fullfiling 条件，False 用于休息。最后，我使用 np.flatnonzero 获取 True 的索引。此解决方案假定所有数据都按 (lowerboundary,upperboundary) 顺序排列。请检查该解决方案是否足够快以达到您的目的。