我有一个元组列表，其中每个元组都是一个 (start-time, end-time)。我正在尝试合并所有重叠的时间范围并返回不同时间范围的列表。
例如
[(1, 5), (2, 4), (3, 6)] ---> [(1,6)]
[(1, 3), (2, 4), (5, 8)] ---> [(1, 4), (5,8)]
这是我的实现方式。
# Algorithm
# initialranges: [(a,b), (c,d), (e,f), ...]
# First we sort each tuple then whole list.
# This will ensure that a<b, c<d, e<f ... and a < c < e ...
# BUT the order of b, d, f ... is still random
# Now we have only 3 possibilities
#================================================
# b<c<d: a-------b Ans: [(a,b),(c,d)]
# c---d
# c<=b<d: a-------b Ans: [(a,d)]
# c---d
# c<d<b: a-------b Ans: [(a,b)]
# c---d
#================================================
def mergeoverlapping(initialranges):
i = sorted(set([tuple(sorted(x)) for x in initialranges]))
# initialize final ranges to [(a,b)]
f = [i[0]]
for c, d in i[1:]:
a, b = f[-1]
if c<=b<d:
f[-1] = a, d
elif b<c<d:
f.append((c,d))
else:
# else case included for clarity. Since
# we already sorted the tuples and the list
# only remaining possibility is c<d<b
# in which case we can silently pass
pass
return f
我想知道是否
- 是否是某些 python 模块中的内置函数可以更有效地执行此操作？或
- 是否有更 Pythonic 的方式来实现相同的目标？
感谢您的帮助。谢谢!
最佳答案
提高效率的几种方法，Pythonic:
- 消除
set()构造，因为该算法应在主循环期间删除重复项。 - 如果您只需要迭代结果，请使用
yield生成值。 - 减少中间对象的构造，例如:将
tuple()调用移动到产生最终值的位置，从而使您不必构造和丢弃额外的元组，并重用列出saved用于存储当前时间范围以供比较。
代码:
def merge(times):
saved = list(times[0])
for st, en in sorted([sorted(t) for t in times]):
if st <= saved[1]:
saved[1] = max(saved[1], en)
else:
yield tuple(saved)
saved[0] = st
saved[1] = en
yield tuple(saved)
data = [
[(1, 5), (2, 4), (3, 6)],
[(1, 3), (2, 4), (5, 8)]
]
for times in data:
print list(merge(times))
关于python - 合并具有重叠时间范围的时间范围元组列表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5679638/