Построение непрерывных отрезков времени по временным меткам

Предположим мы имеем набор (список, массив, набор записей в таблице) меток времени, которые указывают на время в которое были зафиксированы изменения некоторого файла на диске.

  • 2019-11-20 11:00:00
  • 2019-11-20 11:00:20
  • 2019-11-20 11:00:40
  • 2019-11-20 11:00:50
  • 2019-11-20 11:01:00
  • 2019-11-20 11:01:20
  • 2019-11-20 11:01:40
  • 2019-11-20 11:01:50
  • 2019-11-20 11:02:00
  • 2019-11-20 11:03:00
  • 2019-11-20 11:04:00
  • 2019-11-20 11:04:20
  • 2019-11-20 11:04:40
  • 2019-11-20 11:04:50
  • 2019-11-20 11:05:00

Какой алгоритм можно применить для поиска отрезков времени (с началом и концом), которые идут непрерывно, учитывая то что непрерывность должна указываться (в константном/процентном эквиваленте) в алгоритме?

В данном случае видим что временные метки, идут с шагом в 20 секунд, а потом идет разрыв в 2 минуты, а далее опять с шагом в 20 секунд, вот этот разрыв надо как то в алгоритме указывать (а каком виде не знаю). Нужен совет.


Ответы (2 шт):

Автор решения: Pak Uula

Я бы решал в лоб. Создать in-memory таблицу и выбрать из таблицы все интервалы больше заданной длины. У вас в тегах есть пайтон, в нём эту задачу можно решить вот так:

import numpy as np
import pandas as pd

times=np.array(["2019-11-20 11:00:00", "2019-11-20 11:00:20", "2019-11-20 11:00:40", "2019-11-20 11:00:50", "2019-11-20 11:01:00", "2019-11-20 11:01:20", "2019-11-20 11:01:40", "2019-11-20 11:01:50", "2019-11-20 11:02:00", "2019-11-20 11:03:00", "2019-11-20 11:04:00", "2019-11-20 11:04:20", "2019-11-20 11:04:40", "2019-11-20 11:04:50", "2019-11-20 11:05:00"], dtype='datetime64')

df=pd.DataFrame()
df["start"] = times[:-1]
df["end"] = times[1:]
df["dt"] = df.end - df.start

# 20 seconds
threshold = np.timedelta64("20","s")
# Keep intervals that are longer than the thresold
long = df.loc[df["dt"] > threshold]

print(long)

В примере я взял данные из вашего поста, порог установил равным 20 секундам. Результат:

                start                 end       dt
8 2019-11-20 11:02:00 2019-11-20 11:03:00 00:01:00
9 2019-11-20 11:03:00 2019-11-20 11:04:00 00:01:00

Но в вашей постановке это всё баловство. Достаточно один раз пройти по массиву дат и отфильтровать длинные интервалы:

import numpy as np

times=np.array(["2019-11-20 11:00:00", "2019-11-20 11:00:20", "2019-11-20 11:00:40", "2019-11-20 11:00:50", "2019-11-20 11:01:00", "2019-11-20 11:01:20", "2019-11-20 11:01:40", "2019-11-20 11:01:50", "2019-11-20 11:02:00", "2019-11-20 11:03:00", "2019-11-20 11:04:00", "2019-11-20 11:04:20", "2019-11-20 11:04:40", "2019-11-20 11:04:50", "2019-11-20 11:05:00"], dtype='datetime64')
# 20 seconds
threshold = np.timedelta64("20","s")

def filter_longs(times, threshold):
    for i in range(0,len(times)-1):
        dt = times[i+1] - times[i]
        if dt > threshold:
            yield (i, times[i], dt)

print(list(filter_longs(times, threshold)))

Результат:

[(8, numpy.datetime64('2019-11-20T11:02:00'), numpy.timedelta64(60,'s')), (9, numpy.datetime64('2019-11-20T11:03:00'), numpy.timedelta64(60,'s'))]
→ Ссылка
Автор решения: passant

Не знаю, интересует-ли вас техническое или теоретическое решение. Ну например, могут ли ваши отрезки внутри "непрерывных" интервалов следовать через неравные, но короткие отрезки? Будут-ли например в вашем примере считаться, что если с некоторого момента все задержки стали равны 1 минуте, то это новый "непрерывный" участок, или это "разорванные интервалы"? Особенно неясно как быть, если за такой последовательностью вдруг потом будет задержка в 10 минут?

Что такое "непрерывность должна указываться (в константном/процентном эквиваленте)"??

В общем, наиболее общий алгоритм для такого случая - считать среднюю задержку в режиме скользящего окна на несколько предыдущих поступлений и смотреть существенно-ли отличается новая задержка от этого среднего. Если да - считаем что произошел "разрыв непрерывности".

Такой подход решает большинство из поставленных вопросов (и с неравными интервалами поступления и с изменением такта поступления), а для остальных случаев настраивается легким тюнингом.

По крайней мере примерно на таком подходе решают аналогичные задачи в технической диагностики. Только там для более каверзных случаев используют не только среднее, но и другие характеристики ряда задержек поступления сигнала.

→ Ссылка