Объединение списка кортежей времени, имеющих перекрывающиеся интервалы времени
У меня есть список кортежей, где каждый кортеж является (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, который может сделать это более эффективно? или
- Есть ли более питонический способ достижения той же цели?
Ваша помощь приветствуется. Спасибо!
Ответы
Ответ 1
Несколько способов сделать его более эффективным, 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))
Ответ 2
Сортировка кортежей, затем список, если t1.right >= t2.left = > merge и перезапустите с новым списком,...
→
def f(l, sort = True):
if sort:
sl = sorted(tuple(sorted(i)) for i in l)
else:
sl = l
if len(sl) > 1:
if sl[0][1] >= sl[1][0]:
sl[0] = (sl[0][0], sl[1][1])
del sl[1]
if len(sl) < len(l):
return f(sl, False)
return sl
Ответ 3
Часть сортировки: используйте стандартную сортировку, она уже сравнивает кортежи.
sorted_tuples = sorted(initial_ranges)
Слияние. Он также устраняет повторяющиеся диапазоны, поэтому нет необходимости в set. Предположим, что у вас есть current_tuple и next_tuple.
c_start, c_end = current_tuple
n_start, n_end = next_tuple
if n_start <= c_end:
merged_tuple = min(c_start, n_start), max(c_end, n_end)
Надеюсь, что логика достаточно ясна.
Чтобы заглянуть в следующий кортеж, вы можете использовать индексированный доступ к sorted tuples; это все-таки известная последовательность.
Ответ 4
Отсортируйте все границы, затем возьмите все пары, где за границей следует граничный старт.
def mergeOverlapping(initialranges):
def allBoundaries():
for r in initialranges:
yield r[0], True
yield r[1], False
def getBoundaries(boundaries):
yield boundaries[0][0]
for i in range(1, len(boundaries) - 1):
if not boundaries[i][1] and boundaries[i + 1][1]:
yield boundaries[i][0]
yield boundaries[i + 1][0]
yield boundaries[-1][0]
return getBoundaries(sorted(allBoundaries()))
Хм, не так красиво, но было интересно писать хотя бы!
EDIT: Спустя годы, после взлома, я понял, что мой код был неправильным! Это новая версия просто для удовольствия:
def mergeOverlapping(initialRanges):
def allBoundaries():
for r in initialRanges:
yield r[0], -1
yield r[1], 1
def getBoundaries(boundaries):
openrange = 0
for value, boundary in boundaries:
if not openrange:
yield value
openrange += boundary
if not openrange:
yield value
def outputAsRanges(b):
while b:
yield (b.next(), b.next())
return outputAsRanges(getBoundaries(sorted(allBoundaries())))
В основном я отмечаю границы с -1 или 1, а затем сортирую их по значению и выводя их только тогда, когда баланс между открытой и закрытой фигурными скобками равен нулю.
Ответ 5
Поздно, но может помочь кому-то найти это. У меня была аналогичная проблема, но со словарями. Учитывая список диапазонов времени, я хотел найти совпадения и объединить их, когда это возможно. Небольшая модификация ответа @samplebias привела меня к этому:
Функция слияния:
def merge_range(ranges: list, start_key: str, end_key: str):
ranges = sorted(ranges, key=lambda x: x[start_key])
saved = dict(ranges[0])
for range_set in sorted(ranges, key=lambda x: x[start_key]):
if range_set[start_key] <= saved[end_key]:
saved[end_key] = max(saved[end_key], range_set[end_key])
else:
yield dict(saved)
saved[start_key] = range_set[start_key]
saved[end_key] = range_set[end_key]
yield dict(saved)
Данные:
data = [
{'start_time': '09:00:00', 'end_time': '11:30:00'},
{'start_time': '15:00:00', 'end_time': '15:30:00'},
{'start_time': '11:00:00', 'end_time': '14:30:00'},
{'start_time': '09:30:00', 'end_time': '14:00:00'}
]
Исполнение:
print(list(merge_range(ranges=data, start_key='start_time', end_key='end_time')))
Вывод:
[
{'start_time': '09:00:00', 'end_time': '14:30:00'},
{'start_time': '15:00:00', 'end_time': '15:30:00'}
]
