检查两个整数范围是否重叠。

Question

我有两个范围，我想检查这些范围是否有重叠。我已将这些范围转换为列表，并正在检查 readRegion 中的一个值是否在 refRegion 中，但这种方法非常缓慢。有没有更有效的方法来完成这个任务？

readRegion=[*range(end,start,1)] #this list is always 600 in length
refRegion=[*range(600000,600500,1)] #this range will vary
p=0
for i in readRegion:
    if i in refRegion and p < 10000:
        regReads.append(filteredReads[n])
        p=10000    
    p+=1

- Sarah

---

为什么不检查一个数的低端是否比另一个数的高端更低，反之亦然？ - undefined

你的步长总是1吗？ - undefined

Answer 1

如果步长为1，那么两个区间重叠的条件是它们的起始值中较大的一个小于它们的停止值中较小的一个。

def overlaps(x, y):
    return max(x.start,y.start) < min(x.stop,y.stop)

print(overlaps(range(10, 100), range(94, 200))

- Pranav Hosangadi

Answer 2

假设两个范围始终步长为1：

a = range(end, start, 1)
b = range(600000, 600500, 1)
overlapping = (b.start <= a.start < b.stop) or (a.start <= b.start < a.stop)

如果不是这样，我们需要更加通俗易懂：

def ranges_overlap(a: range, b: range) -> bool:
    if b.start <= a.start < b.stop:
        return (a.start - b.start) % b.step == 0
    if a.start <= b.start < a.stop:
        return (b.start - a.start) % a.step == 0
    return False

- orlp

Answer 3

>>> def range_intersect(a: range, b:range) -> range:
...     assert a.step == b.step == 1
...     return range(max((a.start, b.start)), min((a.stop, b.stop)))
...
>>> range_intersect(range(1, 10), range(5, 20))
range(5, 10)

如果您只想检查重叠是否为非零值，请获取结果范围的len。

>>> len(range_intersect(range(1, 3), range(5, 10)))
0

- Samwise

Answer 4

1. 如果您的区域始终是 step=1，例如 1, 2, 3, 4, 5，

   只需对您的范围进行检查，即将您的 end 和 start 与您的 refRegion 范围进行比较，然后计算差异。

2. 如果您的区域不一定始终为 step = 1，例如有时候为 1, 3, 5, 7, 9，并且给定了 step = 2

   在计算中包括步长，如 @orlp 的答案所指出

3. 如果您的区域根本没有遵循任何步长，例如 1, 5, 11, 31, 99

   尝试使用 set 中的 union

   readRegion=[*range(end,start,2)] #这个列表始终是600长
   refRegion=[*range(600000,600500,1)] #这个范围会变动
   regionUnion = set(readRegion).intersection(set(refRegion))
   print(len(regionUnion))
   

- kennysliding

---

我给你的回答点了踩，因为它不必要地低效。我们谈论的是高内存使用和极长的运行时间与即时且无内存使用相比，所以这不仅仅是一个小优化。 - undefined

更不用说，如果OP的整数范围不一定遵循“步长”模式，使用“union”将是适应所有情况的方法。 - undefined

这里实际上不需要使用蛮力算法。 - undefined

@orlp 谢谢你的提醒，我已经修复了代码。还要感谢你的理解。作为一个初学者，你的支持对我来说意义重大。 - undefined

Answer 5

你可以使用 set 来检查两个集合的交集是否有任何值。

例如，你可以做一些简单的事情：

>>> print (True) if set(range(1,100)) & set(range(90,150)) else print (False)
True

>>> print (True) if set(range(1,100)) & set(range(110,150)) else print (False)
False

如果你要将这些转换成一个函数，那么你会得到类似这样的东西：

def compare_ranges(x,y):
    return True if set(x) & set(y) else False

compare_ranges(range(1,100),range(110,150))
compare_ranges(range(1,100),range(90,150))

这两个的输出将是：

False
True

第一个没有任何共同的值，第二个有共同的值。

您还可以使用相同的函数来检查字符串或其他数据类型。

compare(['a','b','c','d'],['a','c','e','f'])
compare(['a','b','c','d'],['e','f','g','h'])

这将输出：

True
False

- Joe Ferndz