Получить объединения и пересечения списка диапазонов дат и времени python - PullRequest
Новая
       21

Получить объединения и пересечения списка диапазонов дат и времени python

0 голосов
/ 29 августа 2018

У меня есть два списка диапазонов datetime. например. 

l1 = [(datetime.datetime(2018, 8, 29, 1, 0, 0), datetime.datetime(2018, 8, 29, 3, 0, 0)), (datetime.datetime(2018, 8, 29, 6, 0, 0), datetime.datetime(2018, 8, 29, 9, 0, 0))]
l2 = [(datetime.datetime(2018, 8, 29, 2, 0, 0), datetime.datetime(2018, 8, 29, 4, 0, 0)), (datetime.datetime(2018, 8, 29, 5, 0, 0), datetime.datetime(2018, 8, 29, 7, 0, 0))]

И я хочу получить объединение l1 и l2. Желаемые выходы: 

union = [(datetime.datetime(2018, 8, 29, 1, 0, 0), datetime.datetime(2018, 8, 29, 4, 0, 0)), (datetime.datetime(2018, 8, 29, 5, 0, 0), datetime.datetime(2018, 8, 29, 9, 0, 0))]
intersection = [(datetime.datetime(2018, 8, 29, 2, 0, 0), datetime.datetime(2018, 8, 29, 3, 0, 0)), (datetime.datetime(2018, 8, 29, 6, 0, 0), datetime.datetime(2018, 8, 29, 7, 0, 0))]

Реальные данные не могут быть идеально выровнены.

Ответы [ 2 ]

0 голосов
/ 29 августа 2018

Ответ здесь очень полезен для того, что вы спрашиваете, поскольку он может сжимать массив перекрывающихся диапазонов: 

from operator import itemgetter

def consolidate(intervals):
    sorted_intervals = sorted(intervals, key=itemgetter(0))

    if not sorted_intervals:  # no intervals to merge
        return

    # low and high represent the bounds of the current run of merges
    low, high = sorted_intervals[0]

    for iv in sorted_intervals[1:]:
        if iv[0] <= high:  # new interval overlaps current run
            high = max(high, iv[1])  # merge with the current run
        else:  # current run is over
            yield low, high  # yield accumulated interval
            low, high = iv  # start new run

    yield low, high  # end the final run

Объединение l1 и l2 - это просто объединение всех диапазонов в l1 и l2: 

def union(l1, l2):
    return consolidate([*l1, *l2])

Пересечение l1 и l2 адекватно выполняется кодом AChampion (если есть какое-либо перекрытие между любым диапазоном в l1 и любым диапазоном в l2, это перекрытие заслуживает того, чтобы быть в результате), но это может привести к фрагментации диапазонов; мы можем использовать эту же функцию для объединения смежных или перекрывающихся диапазонов: 

from itertools import product

def intersection(l1, l2):
    result = ((max(s1, s2), min(e1, e2)) for (s1, e1), (s2, e2) in product(l1, l2) if s1 < e2 and e1 > s2)
    return consolidate(result)

Пример: 

l1 = [(1, 7), (4, 8), (10, 15), (20, 30), (50, 60)]
l2 = [(3, 6), (8, 11), (15, 20)]
print(list(union(l1, l2)))         # [(1, 30), (50, 60)]
print(list(intersection(l1, l2)))  # [(3, 6), (10, 11)]

(В примере для ясности используются целые числа, но он работает с любым сопоставимым типом. В частности, для OP l1 и l2, код дает желаемые результаты OP datetime.)

0 голосов
/ 29 августа 2018

Ваше определение объединения и пересечения для диапазона дат может быть просто описано как: -

Союз: 

In []:
from itertools import product
[(min(s1, s2), max(e1, e2)) for (s1, e1), (s2, e2) in product(l1, l2) if s1 <= e2 and e1 >= s2]

Out[]:
[(datetime.datetime(2018, 8, 29, 1, 0), datetime.datetime(2018, 8, 29, 4, 0)),
 (datetime.datetime(2018, 8, 29, 5, 0), datetime.datetime(2018, 8, 29, 9, 0))]

Пересечения: 

In []:
[(max(s1, s2), min(e1, e2)) for (s1, e1), (s2, e2) in product(l1, l2) if s1 <= e2 and e1 >= s2]

Out[]:
[(datetime.datetime(2018, 8, 29, 2, 0), datetime.datetime(2018, 8, 29, 3, 0)),
 (datetime.datetime(2018, 8, 29, 6, 0), datetime.datetime(2018, 8, 29, 7, 0))]

Вы можете заменить <= и >= на < и >, если они строго перекрываются, а не просто касаются.

...