我正在尝试迭代两个循环,第一个 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) 没有堆。 (假设两个列表都已经排序。)
