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

Question

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

1a：使用设置intersection的范围：

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"列表（平均情况）：

交点s＆t（平均情况）：O(min(len(s), len(t))（如果t不是一组，则将“min”替换为“max”）

对于解决方案1b，我因此假设O(min(len(range1), len(range2))，加上两次从一个范围创建的集合。我认为bool功能非常便宜。

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

对于解决方案2（any）：我没有找到很多关于复杂性的文档，无论是对于any还是对于范围in。对于后者，我假设一个范围表现得像一个列表，这意味着每个O(n)调用的in，因此导致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