Эффективный способ перебора двух связанных циклов в Python

Question

Я пытаюсь перебрать два цикла, первый segment_arr - это список небольших (например, 0,1 м) сегментов линии (отсортированных по расстоянию вдоль линии), а второй fail_sections - это списокбольшие участки этой линии (например, 5 м), которые каким-то образом «проваливаются» (также сортируются по расстоянию вдоль линии).В конечном итоге я пытаюсь объединить плавающие диапазоны - здесь есть некоторые ответы здесь , но все они основаны на целых числах и с некоторыми оговорками о перекрытии.

У меня очень наивная версия, которая, кажется,достаточно производительный для моих целей, но это заставило меня задуматься, как это можно сделать более эффективным:

new_seg_array = []
for seg in segment_arr:
        segfail = False
        for fail_sec in fail_sections:
            if seg.start_dist >= fail_sec.start_dist and seg.end_dist <= fail_sec.end_dist:
                segfail = True
        seg_data = Segment(start_dist=seg.start_dist,end_dist=seg.end_dist, does_fail=segfail)
        new_seg_array.append(seg_data)

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

filtered_fail_sections = (x for x in fail_sections where x.start_distance > seg.start_distance and x.end_distance < seg.end_distance)
for fail_sec in filtered_fail_sections:

, чтобы отфильтровать соответствующие сегменты сбоев, но меня поразило, что он просто выполняет фильтрацию в генераторе.Есть ли какой-нибудь способ в Python постепенно уменьшить область действия второго цикла, чтобы элементы, которые больше не были релевантными, потому что они находятся выше диапазона первого цикла, больше не повторялись?Таким образом, со временем второй цикл станет меньше, пока он не станет ничем, что, вероятно, будет способствовать повышению производительности на гораздо больших наборах данных.Или возможны ли другие существенные улучшения эффективности?

Answer 1

Вы можете сохранить сбойные сегменты, которые в данный момент «активны», в куче, отсортированные по их конечному значению, а затем извлечь их из кучи, когда это конечное значение меньше конца текущего сегмента.Затем, если в куче есть какие-либо элементы, текущий сегмент завершается ошибкой.

import heapq
segments = [(1,2), (3,4), (5,7), (9,10)]
fail = [(0,4), (8,11)]

idx = 0
covering = []
for (start, end) in segments:
    while idx < len(fail) and fail[idx][0] <= start:
        heapq.heappush(covering, fail[idx][1])
        idx += 1
    while covering and covering[0] < end:
        heapq.heappop(covering)
    print(start, end, covering)    

Пример вывода:

1 2 [4]
3 4 [4]
5 7 []
9 10 [11]

Таким образом, вы не только узнаете , если текущий сегмент терпит неудачу, но также и какой и сколько неудачных сегментов он пересекает.Обратите внимание, что если вы хотите поместить полный отказавший сегмент в кучу, вы должны использовать кортеж (end, f_seg), чтобы гарантировать, что тот, у кого самый низкий end, будет отсортирован первым в куче.

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

idx = 0
last_fail = -1
for (start, end) in segments:
    while idx < len(fail) and fail[idx][0] <= start:
        last_fail = max(last_fail, fail[idx][1])
        idx += 1
    print(start, end, last_fail >= end)

Сложность для решения на основе кучи будет O (n + mlogm) для n сегментов и m fail-сегментов, и просто O (n+ м) без кучи.(Предполагая, что оба списка уже отсортированы.)