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

2024-03-29 13:51:09 发布

您现在位置:Python中文网/ 问答频道 /正文

我有两个范围,希望检查它们在Python(v3.5)中是否重叠。这些是一些解决办法。在

1a:使用具有范围的集合intersection

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

1b:将set intersection与两个集合一起使用:

^{pr2}$

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函数非常便宜。在

对于解1aO(max(len(range1), len(range2)),加上从一个范围创建一个集合。在

对于解决方案2any):我没有发现太多关于复杂性的文档,既没有针对any的文档,也没有针对范围{}的文档。对于后者,我假设一个范围的行为类似于一个列表,对于每个in调用,这意味着O(n),因此结果是{},其中{}和{}。同时,any应该在找到匹配项后立即指向一个快捷方式,并且可以避免创建集合。在

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

  1. 把一个范围转换成一组有多贵?在
  2. bool()函数到底有多贵?在
  3. 一个范围的in真的像列表(O(n))中的行为吗?在
  4. 除了算法复杂性之外,还有哪些实现细节是相关的?在
  5. 最后,考虑这些问题:检查两个范围之间重叠的最有效方法是什么?在

由于实际计算时间在很大程度上取决于范围的属性,即重叠元素发现的时间有多早,以及它们的大小,所以这并不容易进行经验评估。这就是为什么我在寻找一个更具分析性的解释。在


Tags: in文档列表lendef时间anymin
1条回答
网友
1楼 · 发布于 2024-03-29 13:51:09

别那样做。取而代之的是:

  1. 将每个范围从最低到最高排列。在
  2. 如果range1.lowest>;range2.lowest,则将range1与range2交换
  3. 如果range1.highest>;range2.lower,则范围相交
  4. 如果range1.highest==range2.lower,则ranges触摸
  5. 如果range1.highest<;range2.lower则范围不同。在

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

比如:

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

更完整的实现:

^{pr2}$

相关问题 更多 >