Объединение списка кортежей времени, имеющих перекрывающиеся интервалы времени

У меня есть список кортежей, где каждый кортеж (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 

Я пытаюсь выяснить, если

  1. Является ли встроенная функция в каком-то модуле python, который может сделать это более эффективно? или
  2. Есть ли более питонический способ достижения одной и той же цели?

Ваша помощь приветствуется. Благодаря!

5 Solutions collect form web for “Объединение списка кортежей времени, имеющих перекрывающиеся интервалы времени”

Несколько способов сделать его более эффективным, Pythonic:

  1. Устраните конструкцию set() , поскольку алгоритм должен вырезать дубликаты во время основного цикла.
  2. Если вам просто нужно перебирать результаты, используйте yield для генерации значений.
  3. Уменьшите построение промежуточных объектов, например: переместите вызов 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)) 

Сортируйте кортежи, затем перечислите, если t1.right> = t2.left => объединить и перезапустить с новым списком, …

->

 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 

Сортировка: используйте стандартную сортировку, она уже сравнивает кортежи.

 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 ; это все-таки известная последовательность.

Отсортируйте все границы, затем возьмите все пары, где за границей следует граничный старт.

 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, а затем сортирую их по значению и выводя их только тогда, когда баланс между открытой и закрытой фигурными скобками равен нулю.

Поздно, но может помочь кому-то найти это. У меня была аналогичная проблема, но со словарями. Учитывая список диапазонов времени, я хотел найти совпадения и объединить их, когда это возможно. Небольшая модификация ответа @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'} ] 
  • Python: слияние двух списков словарей
  • слияние словарей Python
  • Объединение столбцов нескольких файлов в один файл - Python
  • Класс Python для объединения отсортированных файлов, как это можно улучшить?
  • Объедините два словаря и удалите дубликаты в python
  •  
    Interesting Posts for Van-Lav
    Python - лучший язык программирования в мире.