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

Question

我有大量的间歇训练（大约 5k 到 10k）。这些元素有一个开始和结束位置；像（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 秒），我的问题是，我将如何优化它？我尝试在第二个循环的开始位置超过第一个结束位置时切断第二个 for 循环：

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 o is not 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)

当然，如果您的输入已经排序（看起来），您可以跳过该步骤。

请注意，一般来说，您可以使用更清晰的

for

，而不是使用双

itertools.combinations

。它保证相同类型的排序。不幸的是，它不适合算法的优化版本，但你的可以写成

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

最后，如果您想按时间间隔执行快速的

通用操作，您可能还需要考虑使用间隔树数据结构。 PyPI 上有 Python 实现。