Общие элементы в списках 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

Answer 2

Здесь следует отметить пару замечаний:

1. диапазоны с разными идентификаторами не могут перекрываться.Это означает, что мы можем разделить проблему на основе идентификаторов, а затем решить каждый раздел отдельно, игнорируя идентификатор.

2. Если вы сортируете списки, то вам не нужно проверятьвсе диапазоны против всех диапазонов, вместо этого вы можете прерваться рано, как только увидите, что e1

То, что вы ищете здесьэто форма алгоритма скользящего окна, не слишком отличающаяся от того, что вы увидите в TCP.

Поэтому, собрав все это вместе:

from itertools import groupby

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)]

def partition(lst):
    part = groupby(lst, lambda el: el[0])
    return {id: list(el) for id, el in part}

# you may be able to skip sorted() here if you know your input is already sorted
List1_part = partition(sorted(List1))
List2_part = partition(sorted(List2))

for id in set(List1_part) & set(List2_part):
    window_size = max((e-s) for _, s, e in List2_part[id])
    window = 0
    for r1 in List1_part[id]:
        for r2 in List2_part[id][window:]:
            _, s1, e1 = r1
            _, s2, e2 = r2
            if e1 < s2:
                break
            elif e2 >= s1:
                print(id, max(s1, s2), min(e1, e2))
            elif s2 + window_size < s1: 
                window += 1

Answer 3

Хорошо ... это крайнее излишество (мне было весело, оставь меня в покое!), Но он работает примерно в 3 раза быстрее, чем простой алгоритм.

Реальная сила этого подхода в том, что он можетобрабатывать очень большие списки, не замедляя при этом, и ничего не хранит в памяти.Так что попробуйте это со списками со 100 или 1000 вещами в них, и вы увидите большее улучшение.

Я не предполагаю, что списки отсортированы, поэтому время должно доминировать над сортировкой O(n.log(n)), предполагая, что PythonsАлгоритм сортировки хорош.

from itertools import groupby
from operator import itemgetter


def get_list_overlaps(list_a, list_b):
    for range_id, (a_ranges, b_ranges) in align_lists(list_a, list_b):
        a_range = next(a_ranges)
        b_range = next(b_ranges)

        try:
            while a_range and b_range:
                overlap = get_overlap(a_range, b_range)
                if overlap:
                    yield overlap

                    # If we overlap, discard the one which ends earliest
                    if a_range[2] < b_range[2]:
                        a_range = next(a_ranges)
                    else:
                        b_range = next(b_ranges)

                else:
                    # If not, discard the one which starts earliest
                    if a_range[1] < b_range[1]:
                        a_range = next(a_ranges)
                    else:
                        b_range = next(b_ranges)

    except StopIteration:
            continue

def align_lists(list_a, list_b):
    b_grouped = groupby(sorted(list_b), key=itemgetter(0))
    b_id, b_intervals = next(b_grouped)

    for a_id, a_intervals in groupby(sorted(list_a), key=itemgetter(0)):
        # Work until our lists line up
        if a_id < b_id:
            continue

        try:
            while a_id > b_id:
                b_id, b_intervals = next(b_grouped)
        except StopIteration:
            break

        yield a_id, (a_intervals, b_intervals)


def get_overlap(a_range, b_range):
    _, a_start, a_end = a_range
    _, b_start, b_end = b_range

    # If either ends before the other starts, no overlap
    if b_end < a_start or a_end < b_start:
        return

    return max(a_start, b_start), min(a_end, b_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 overlap in get_list_overlaps(List1, List2):
    print(overlap)

Идея состоит в том, чтобы сначала сгруппировать по идентификатору, чтобы мы никогда не сравнивали вещи с разными идентификаторами, а затем скользили по вещам в каждом идентификаторе, выбрасывая их, когдаи не пересекаются.

Вы могли бы оптимизировать это, вставив некоторые функции и т. д.

Answer 4

Если вы хотите использовать понимание списка, вы можете сделать:

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)]                                                                      

output = [(max(s1, s2), min(e1, e2)) for id1, s1, e1 in List1 
                                     for id2, s2, e2 in List2                                                               
                                     if id1 == id2 and e2 >= s1 and s2 <= e1]

print(output)

Вывод:

[(50, 56), (61, 64), (70, 81), (84, 87), (90, 90), (99, 99), (110, 117), (119, 126), (5, 9), (11, 15), (3, 9)]                                       

, который выглядит так же, как и в оригинале.Как правило, понимание списка происходит быстрее, чем стандартные циклы.

Понимание списка: 6,51 мкс ± 13,7 нс на цикл (среднее ± стандартное отклонение из 7 циклов, 100000 циклов в каждом)

Исходный цикл: 25,2 мкс ± 239 нс на цикл (среднее ± стандартное отклонение из 7 циклов, по 10000 циклов каждый)

(код сравнения "Original Loop" был:

    output = []
    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:
                output.append((mstart, mend))

)

Answer 5

Похоже, вы уже гарантировали, что ваши списки отсортированы по идентификатору и времени начала и не имеют совпадений.По сути, каждый идентификатор представляет собой отдельный список для обнаружения перекрытия.

Вы будете проходить через пару списков так же, как и при слиянии списков (что, по сути, и есть).Иметь индекс в каждом списке (index_a, index_b);на каждой итерации вы работаете с меньшим из двух упомянутых значений (начальное значение, которое находится в индексе).

Для обработки одного интервала - элемент в list_a [index_a]:

• получить конечное значение.
• set check_b = index_b
  • сравнить это с начальным значением элемента в другом списке.
  • while end [index a]> начните [check_b], тогда у вас есть перекрытие;сообщить об этом.
  • Приращение check_b.
• Приращение index_a.
• Проверить новый элемент list_a с текущим элементом list_b;выберите тот, у которого начальное значение меньше, и вернитесь к началу этого процесса (первая буква).