Построение непрерывных отрезков времени по временным меткам
Предположим мы имеем набор (список, массив, набор записей в таблице) меток времени, которые указывают на время в которое были зафиксированы изменения некоторого файла на диске.
- 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 шт):
Я бы решал в лоб. Создать 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'))]
Не знаю, интересует-ли вас техническое или теоретическое решение. Ну например, могут ли ваши отрезки внутри "непрерывных" интервалов следовать через неравные, но короткие отрезки? Будут-ли например в вашем примере считаться, что если с некоторого момента все задержки стали равны 1 минуте, то это новый "непрерывный" участок, или это "разорванные интервалы"? Особенно неясно как быть, если за такой последовательностью вдруг потом будет задержка в 10 минут?
Что такое "непрерывность должна указываться (в константном/процентном эквиваленте)"??
В общем, наиболее общий алгоритм для такого случая - считать среднюю задержку в режиме скользящего окна на несколько предыдущих поступлений и смотреть существенно-ли отличается новая задержка от этого среднего. Если да - считаем что произошел "разрыв непрерывности".
Такой подход решает большинство из поставленных вопросов (и с неравными интервалами поступления и с изменением такта поступления), а для остальных случаев настраивается легким тюнингом.
По крайней мере примерно на таком подходе решают аналогичные задачи в технической диагностики. Только там для более каверзных случаев используют не только среднее, но и другие характеристики ряда задержек поступления сигнала.