python - python列表中的常见元素

Question

我有以下结构的列表:列表结构:[(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)

谁能帮我加快速度？我需要一种算法来比这种粗暴的方法更快地工作。

Answer 1

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