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

非常感谢您的帮助！

- jrm

---

它们已经排序了吗？ - Ahmad Khan

@MuhammadAhmad 第一个列表可以轻松排序，但第二个不行。 - jrm

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的bool类型的np.array。使用np.logical_and得到单个1D的np.array，其中True表示满足条件，False表示不满足。最后，我使用np.flatnonzero来获取True的索引。这个解决方案假设所有数据都是按照(lowerboundary,upperboundary)的顺序排列的。请检查该解决方案是否足够快速地满足您的需求。最初的回答。

- Daweo

---

非常感谢，我在一个小的子集上进行了测试，这将完美地工作。 - jrm

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中包含的a中的区间。索引分别为idx_a和idx_b。

- RunOrVeith