Python:检查重叠范围的复杂性

Question

我有两个范围，想检查它们在 Python (v3.5) 中是否重叠。这些是一些解决方案。

1a:使用 set intersection with range:

def overlap_intersection_set(range1, range2):
  return bool(set(range1).intersection(range2))

1b:使用 set intersection 两个集合:

def overlap_intersection_two_sets(range1, range2):
  return bool(set(range1).intersection(set(range2)))

2:使用any和范围in:

def overlap_any(range1, range2):
  return any([i1 in range2 for i1 in range1])

我一直在尝试计算这些方法的成本，主要是在时间方面，但空间复杂性也可能相当大。

Python Wiki page "Time Complexity"集合交叉点的列表(平均情况):

Intersection s&t (average case): O(min(len(s), len(t)) (replace "min" with "max" if t is not a set)

对于解决方案 1b，我因此假设 O(min(len(range1), len(range2))，再加上从一个范围创建的集合的两倍。我考虑 bool 函数非常便宜。

对于解决方案 1a:O(max(len(range1), len(range2))，加上一次从范围创建的集合。

对于解决方案2(any):我没有找到很多关于复杂性的文档，无论是any还是范围in 。对于后者，我假设范围的行为类似于列表，这意味着每个 in 调用的 O(n)，因此导致 O(n* m) 与 n=len(range1) 和 m=len(range2)。同时，any 应在找到匹配项后立即指向快捷方式，并且可以避免创建集合。

因此，我的问题涉及算法的复杂性及其特定于 Python 的实现:

1. 将范围转换为集合的成本是多少？
2. bool() 函数到底有多贵？
3. 范围的 in 是否真的像在列表中一样 (O(n))？
4. 除了算法复杂性之外，还有哪些相关的实现细节？
5. 最终，考虑以下问题:检查两个范围之间重叠的最有效方法是什么？

这不容易根据经验进行评估，因为实际计算时间在很大程度上取决于范围的属性，即找到重叠元素的时间及其大小。这就是为什么我正在寻找更具分析性的解释。

Answer 1

不要那样做。相反:

1. 安排每个范围按从低到高的顺序排列。
2. 如果 range1.lowest > range2.lowest 则将 range1 与 range2 交换
3. 如果 range1.highest > range2.lowest 则范围相交
4. 如果 range1.highest == range2.lowest 那么范围接触
5. 如果 range1.highest < range2.lowest 则范围不同。

上述算法与范围大小无关，也可以处理非整数范围。

类似于:

def is_overlapped(r1, r2):
    if r1.lowest > r2.lowest:
        r1, r2 = r2, r1
    return r1.highest > r2.lowest

更完整的实现:

from collections import namedtuple

class Range(namedtuple('Range', 'lowest, highest')):

    __slots__ = () 

    def __new__(_cls, lowest, highest):
        'Enforces lowest <= highest'
        if lowest > highest:
            lowest, highest = highest, lowest
        return super().__new__(_cls, lowest, highest)

def is_overlapped(r1, r2):
    r1, r2 = sorted([r1, r2])
    return r1.highest > r2.lowest

if __name__ == '__main__':
    range1, range2 = Range(4, -4), Range(7, 3)
    assert is_overlapped(range2, range1) == is_overlapped(range1, range2)
    print(is_overlapped(range2, range1))  # True