python - 查找与另一个大列表重叠/相交的大列表的子集

Question

我编写了一个 Python 模块，通过检查列表中的项目是否与另一个列表中的项目重叠/相交来查找列表的子集。我的模块的主要部分看起来像这样:

from collections import defaultdict

总列表中共有1865390项(项为元组)

overalllist = [(8361474, 8363645), (8363182, 8363758), …, (14634342, 14634440)] 

我的列表中共有 608348 个项目

mylist = [(8362677, 8363216), (8414202, 8414313), …, (14634354, 14634397)]

查找列表的子集

def mysubsets(list1, list2):                       
    sublist = [(x, y) for x, y in list1 if x <= list2[1] and y >= list2[0]]                  
    return sublist

对于上面给出的示例列表，mylist 的第一项 (8362677, 8363216) 与 overalllist 的前两项 [(8361474, 8363645), (8363182, 8363758)] 重叠。所以对于(8362677, 8363216)，overalllist的子集是[(8361474, 8363645), (8363182, 8363758)], ...

初始化一个空列表字典，它将使用 mylist 中的项目作为键和 overalllist 中的子集作为值填充

mydict = defaultdict(list)

遍历mylist中的每一项，在overalllist中找到子集放入mydict

for item in mylist:
    sublist = mysubsets(overalllist, item)
    mydict.update({item:sublist})

输出看起来像这样

>>> mydict
defaultdict(<type 'list'>, {(14634354, 14634397): [(14634342, 14634440)], …, (8362677, 8363216): [(8361474, 8363645), (8363182, 8363758)]})

我的脚本可以运行，但速度极慢(运行了大约 18 小时)。我使用 cProfile 检查了执行时间，发现 mysubsets() 花费了很多时间:

ncalls tottime percall cumtime percall filename:lineno(function)
608348 1732.827 0.003 1732.827 0.003 mymodule.py:383(mysubsets)

我想知道是否有任何最快速有效的方法来实现我的目标。谢谢。

Answer 1

假设每个列表中的区间之间没有重叠，首先对每个列表进行排序，然后以线性时间从头到尾遍历两个列表，伪代码如下:

i1 = 0
i2 = 0
while i1<len(list1) && i2<len(list2):
  if list1[i1] is to the left of list2[i2]:
    i1 += 1
  elif list2[i2] is to the left of list1[i1]:
    i2 += 1
  else // list1[i1] overlaps list2[i2]
    find all intervals from list2[i2:] that overlap with the interval list1[i1]
    i1 += 1