时间戳

首页 > 解决方案 > python列表中的常见元素

python - python列表中的常见元素

问题描述

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

谁能帮我加快速度？我需要一种算法比这种蛮力方法工作得更快。

标签： pythonlist

解决方案

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

推荐阅读