查找一个区间是否落在一组区间内 Python

Question

我正在使用 Python 中 portion 包中的 python-intervals：import portion as P

要检查一个项目是否包含在一个集合中，我们可以做item in set，例如2 in {2,3}给出True。（这需要 O(1) 时间）

要检查一个区间是否包含在另一个区间内，我们可以做item in interval，例如P.closed(2,3) in P.open(1,10)给出True.

我想检查一个区间是否包含在区间列表中。执行此操作的迭代方式 (O(n)) 为：

import portion as P

intervals_set = {P.open(1,10), P.open(20,30)}
item = P.closed(2,3)
result = []
for s in intervals_set:
    if item in s:
        result.append(item)

我必须针对很长的间隔执行许多项目的搜索（运行这个 for 循环很多次），所以我想知道是否有一种有效的方法来查找间隔是否存在于一组间隔？

Answer 1

我是 portion 的维护者。

portion 支持开箱即用的间隔集，因此您无需手动创建一组间隔（例如，不需要 {P.open(1,10), P.open(20,30)}）。只需创建这些区间的析取，它就会起作用：

interval = P.open(1, 10) | P.open(20, 30)
item = P.closed(2, 3)
assert item in interval

这会比您提出的解决方案稍快一些，因为 portion 在内部对间隔进行排序（析取），并从这种排序中受益，使事情变得更快。

如果您有很多项，则循环变为：

for item in items: 
  if item in interval: 
    result.append(item)

或者，使用列表理解，[item for item in items if item in interval]。

查找一个区间是否落在一组区间内 Python

Find whether an interval falls within a set of intervals Python

python

search

set

intervals