Python：优化区间之间的成对重叠

Question

我有很多区间，大约有五千到一万条。这些区间都有一个开始位置和一个结束位置，比如说(203, 405)。这些区间的坐标都存储在一个列表里。

我想找出每一对区间之间重叠部分的坐标和长度。可以通过以下方式来实现：

# a small list for clarity, with length normally around 5000s
cList = ((20, 54), (25, 48), (67, 133), (90,152), (140,211), (190,230)) 
for i, c1 in enumerate(cList[:-1]): # a linear pairwise combination
    for c2 in cList[i + 1:]:
        left =  max(c1[0], c2[0])
        right = min(c1[1], c2[1])
        overlap = right - left
        if overlap > 0:
            print "left: %s, right: %s, length: %s" % (left, right, overlap)

结果是：

left: 25, right: 48, length: 23
left: 90, right: 133, length: 43
left: 140, right: 152, length: 12
left: 190, right: 211, length: 21

可以看到，这个方法是有效的……不过这个过程可能会花费不少时间（大约20秒），所以我想知道怎么优化一下这个过程。我尝试在第二个循环中，当第二个区间的开始位置超过第一个区间的结束位置时，就停止第二个循环：

if c1[1] < c2[0]:
    break

这样做确实大大缩短了处理时间，但得到的重叠数量大约比之前少了三倍，因此结果肯定是不准确的。这是因为有些区间的长度远大于前面的区间。

我相信一定有什么数学技巧可以解决这个问题。

Answer 1

一般来说，如果你先把区间按照起始点排序，这类问题会变得简单很多。

首先，我们定义一个函数，这样会更清楚：

def overlap( r1, r2 ):
    left =  max(r1[0], r2[0])
    right = min(r1[1], r2[1])
    over = right - left
    return (left, right, over) if over>0 else None

你描述的算法可以写成：

for i, c1 in enumerate(cList[:-1]): 
    for c2 in cList[i + 1:]:
        o = overlap(c1,c2)
        if not o is None:
            print "left: %s, right: %s, length: %s" % o

如果你对元素进行排序，一旦找到一个不重叠的区间，就可以“短路”处理，因为你知道列表中后面的区间会更远：

l= sorted(cList)
for i, c1 in enumerate(l[:-1]): 
    for c2 in l[i + 1:]:
        o= overlap(c1,c2)
        if o is None:
            break
        print "left: %s, right: %s, length: %s" % o

当然，如果你的输入数据已经排好序（看起来是这样），你就可以跳过这一步。

需要注意的是，通常情况下，你可以用更清晰的 itertools.combinations 来代替双重 for 循环。这样也能保证相同的顺序。不过，遗憾的是，这种方法不适合优化后的算法，但你的算法可以写成：

from itertools import combinations
for c1,c2 in combinations(cList, 2):
    o= overlap(c1,c2)
    if not o is None:
        print "left: %s, right: %s, length: %s" % o

最后，如果你想对区间进行快速的通用操作，你可能还想考虑使用 区间树 数据结构。在 pypi上有一个Python实现。