Python 3.5中范围重叠检查的算法复杂度与最优实现分析

嘿，咱们来逐个拆解你的问题，最后再给出最靠谱的range重叠检查方案！

你的问题解答 #

1. 将range转换为set的开销有多大？

开销非常大，尤其是当range的范围很广的时候。Python的range是惰性序列，它本身只存储start、stop、step三个参数，不会预先生成所有元素。但一旦转成set，就必须遍历整个range的每一个元素，把它们全部存入集合——这意味着：

• 时间复杂度是O(n)，n是range里元素的个数；
• 空间复杂度也是O(n)，要占用和元素数量成正比的内存。
  比如range(1, 10**8)转set，直接会把内存撑爆，完全不可行。另外你提到的1a和1b，1b还要转两个set，开销是1a的两倍，更不划算。

2. bool()函数的实际开销如何？

几乎可以忽略不计。bool()只是Python内部对对象做布尔值的快速判断——比如对空集合返回False，非空返回True，这个操作经过了高度优化，和转集合、遍历元素这些操作比起来，成本微乎其微，完全不用在意。

3. range的in操作是否和list一样为O(n)复杂度？

完全不一样！这是很多人容易踩的坑。list的in操作需要逐个遍历元素，是O(n)；但range是特殊的序列类型，它的in操作是数学计算实现的O(1)。

举个例子，检查x in range(a, b, s)时，Python会做这几步：

1. 判断x是否在[a, b)（如果step为正）或者[b, a)（如果step为负）的区间内；
2. 计算(x - a)是否能被step整除。
   全程不需要遍历任何元素，瞬间就能得出结果。

4. 除算法复杂度外，还有哪些相关实现细节？

• 短路求值：你的方案2里，如果用any(i1 in range2 for i1 in range1)（注意不要加[]，用生成器表达式），只要找到第一个重叠的元素就会立刻停止遍历，而转set的方法必须遍历完整个range才能生成集合，不管有没有重叠；
• 步长处理：很多人会忽略range的步长不为1的情况，但range的in操作已经自动处理了步长，而数学判断法也需要考虑步长的影响；
• 内存占用：转set的方法在大range场景下会占用巨量内存，而用any或者数学方法，内存开销几乎为0，因为不需要存储任何元素；
• 空range边界：如果其中一个range是空的（比如range(5,3)），所有方法都要正确返回False，数学方法需要先处理这种情况。

最优方案：直接用数学逻辑判断 #

既然range的本质是三个参数的数学序列，那最有效的方法就是直接通过数学计算判断两个range是否有重叠，时间和空间复杂度都是O(1)，不管range多大都能瞬间得出结果。

这里给出一个能处理任意步长（正、负）的实现：

def overlap_math(range1, range2):
    # 辅助函数：把任意步长的range转成等效的正步长形式（start <= stop，step>0）
    def normalize_range(r):
        start, stop, step = r.start, r.stop, r.step
        if step < 0:
            # 负步长的range等价于反转后的正步长range，比如range(10, 5, -1)等价于range(6, 11, 1)
            start, stop = stop + 1, start + 1
            step = -step
        # 处理空range的情况
        if start >= stop:
            return (0, 0, 1)
        return (start, stop, step)

    s1, e1, step1 = normalize_range(range1)
    s2, e2, step2 = normalize_range(range2)

    # 先判断两个range的区间是否有重叠的可能
    overlap_start = max(s1, s2)
    overlap_end = min(e1, e2)
    if overlap_start >= overlap_end:
        return False

    # 检查在重叠区间内是否存在同时属于两个range的元素
    # 方法：找重叠区间内第一个属于range1的元素，看是否在range2里
    delta = (overlap_start - s1) % step1
    candidate = s1 + delta
    if candidate < overlap_end and (candidate - s2) % step2 == 0:
        return True

    # 再找重叠区间内第一个属于range2的元素，看是否在range1里（防止上面的候选不在range2，但存在其他元素）
    delta = (overlap_start - s2) % step2
    candidate = s2 + delta
    if candidate < overlap_end and (candidate - s1) % step1 == 0:
        return True

    return False

如果你的场景里range的步长都是1，那逻辑可以更简化：

def overlap_math_step1(range1, range2):
    # 先处理负步长转正步长
    def normalize(r):
        if r.step < 0:
            return range(r.stop + 1, r.start + 1)
        return r
    r1, r2 = normalize(range1), normalize(range2)
    return max(r1.start, r2.start) < min(r1.stop, r2.stop)

各方案对比总结 #

内容的提问来源于stack exchange，提问作者Carsten