我有两个范围,希望检查它们在Python(v3.5)中是否重叠。这些是一些解决办法。在
1a:使用具有范围的集合intersection
:
def overlap_intersection_set(range1, range2):
return bool(set(range1).intersection(range2))
1b:将set intersection
与两个集合一起使用:
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
调用,这意味着O(n)
,因此结果是{any
应该在找到匹配项后立即指向一个快捷方式,并且可以避免创建集合。在
因此,我的问题涉及到算法的复杂性及其特定于Python的实现:
bool()
函数到底有多贵?在in
真的像列表(O(n)
)中的行为吗?在由于实际计算时间在很大程度上取决于范围的属性,即重叠元素发现的时间有多早,以及它们的大小,所以这并不容易进行经验评估。这就是为什么我在寻找一个更具分析性的解释。在
别那样做。取而代之的是:
上述算法与区间大小无关,也可以处理非整数范围。在
比如:
更完整的实现:
^{pr2}$相关问题 更多 >
编程相关推荐