Skip to main content
 首页 » 编程设计

python之在python中迭代两个相关循环的有效方法

2024年12月31日8insus

我正在尝试迭代两个循环,第一个 segment_arr 是一条线的小(例如 0.1m)段列表(按沿线的距离排序),第二个 fail_sections 是该线的较大部分(例如 5m)的列表,这些部分以某种方式“失败”(也按沿线的距离排序)。最终我试图合并 float 范围 - 有一些答案 here ,但都基于整数,并且有一些关于重叠的警告。

我有一个非常幼稚的版本,它的性能似乎足以满足我的目的,但这让我开始思考,如何才能提高效率:

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 中是否有任何方法可以逐渐缩小第二个循环的范围,因此不再迭代因为它们超出第一个循环范围而不再相关的元素?所以随着时间的推移,第二个循环会变小,直到什么都没有,这可能有助于在更大的数据集上提高性能。或者任何其他可能的重大效率改进?

请您参考如下方法:

您可以将当前“事件”的失败段存储在堆上,按它们的最终值排序,然后在该结束值小于当前段的末尾时将它们从堆中弹出。然后,如果堆上有任何元素,则当前段失败。

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) 

对于 n 个段和 m 个失败段,基于堆的解决方案的复杂度为 O(n+mlogm),而且只是O(n+m) 没有堆。 (假设两个列表都已经排序。)