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

Question

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

4

我有大量的间隔（约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秒），所以我的问题是，我该如何优化它？我尝试在第二个循环的开始位置超过第一个结束位置时切断第二个循环：

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

这大大缩短了流程时间，但重叠数量比以前少了约三倍，因此结果肯定是无效的。这是由于某些元素的长度比前面的元素要大得多。

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

- Benjamin

1

如果列表是[(0, 4), (1, 5), (2, 6)]，那么你将面对一个复杂的多重重叠模式。在这种情况下，你是否仍想要成对的重叠结果？（在这种情况下，重叠的区间本身也会发生重叠。） - user2357112

如果列表是[(0, 4), (2, 6), (4, 8), (6, 10)]，你想要输出[(2, 4), (4, 6), (6, 8)]，还是[(2, 8)]，或者其他什么？ - user2357112

1

这个（基因组）数据肯定包含多重重叠。但在我的情况下，只有检索成对的重叠才是有趣的。我理解你所说的重叠重叠的意思。在上面的例子中可能有点令人困惑。真实数据由对象组成，而不仅仅是坐标... - Benjamin

我想要每个成对重叠的部分，所以[(2,8)]不正确。 - Benjamin

1

@Benjamin 请编辑您的问题，明确说明您想要成对重叠。按照目前的阅读方式，似乎您想要所有区域都重叠的片段。 - loopbackbee

如果您正在寻找与此类问题相关的信息，那么您所称之为“元素”的通常被称为“区间”。 - loopbackbee

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- loopbackbee · Accepted Answer

通常，如果您按起始点对区间进行排序，这种问题会变得更加容易解决。

首先，让我们定义一个函数，以便使事情更清晰：

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代替双重循环。它保证了相同类型的排序。不幸的是，它不适用于算法的优化版本，但你的算法可以写成

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实现。