我有以下结构的列表: 列表结构:[(id,start, end), (id,start, end), (id,start, end)]
例如,它们可能看起来像这样:
List1 = [(1,50,56),(1,61,69),(1,70,87),(1,90,99),(1,110,117),(1,119,126),(2,3,9), (2,11,17), (3,2,9)]
List2 = [(1,44,56),(1,59,64),(1,70,81),(1,84,90),(1,99,155), (2,5,15), (3,3,9)]
我需要找到它们之间的重叠区域。
我已经用这段代码尝试了暴力方法:
for a1, s1, e1 in List1:
for a2, s2, e2 in List2:
sgroup = [s1, s2]
egroup = [e1, e2]
mstart = max(sgroup)
mend = min(egroup)
if a1 == a2 and e2>=s1 and s2<=e1:
t = (mstart, mend)
print(t)
谁能帮我加快速度?我需要一种算法来比这种粗暴的方法更快地工作。
请您参考如下方法:
for a1, s1, e1 in List1:
for a2, s2, e2 in List2:
if a1 == a2 and s2 <= e1 and e2 >= s1:
print (max(s1, s2), min(e1, e2))
[编辑]:测量时间:
import time
def group1():
res = []
for a1, s1, e1 in List1:
for a2, s2, e2 in List2:
sgroup = [s1, s2]
egroup = [e1, e2]
mstart = max(sgroup)
mend = min(egroup)
if a1 == a2 and e2>=s1 and s2<=e1:
t = (mstart, mend)
res.append(t)
return res
def group2():
res = []
for a1, s1, e1 in List1:
for a2, s2, e2 in List2:
if a1 == a2 and s2 <= e1 and e2 >= s1:
res.append((max(s1, s2), min(e1, e2)))
return res
List1 = [(1,50,56),(1,61,69),(1,70,87),(1,90,99),(1,110,117),(1,119,126),(2,3,9), (2,11,17), (3,2,9)]
List2 = [(1,44,56),(1,59,64),(1,70,81),(1,84,90),(1,99,155), (2,5,15), (3,3,9)]
for func in [group1, group2]:
start = time.time()
func()
end = time.time()
print(f'{func.__name__}: {end - start}')
print(func())
输出:
group1: 6.985664367675781e-05
group2: 1.9788742065429688e-05
