0

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

  • 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 секунд, вот этот разрыв надо как то в алгоритме указывать (а каком виде не знаю). Нужен совет.

4
  • Что значит "непрерывно в процентном эквиваленте"?
    – tym32167
    22 фев 2020 в 0:32
  • @tym32167 А где сказано, "непрерывно в процентном эквиваленте"? 22 фев 2020 в 0:46
  • В процентном эквиваленте например задается, ситуация, когда отрезки времени считаются разорванными между собой, когда они достигают определенного значения. Но я не уверен что они должны быть в процентном, я не знаю в каком, поиск решения на он и поиск решения. 22 фев 2020 в 0:49
  • Вам нужна функция, которая принимает два значения времени и возвращает информацию о том, являются ли эти значения непрерывным отрезком или нет. Например bool isContinuous(DateTime start, DateTime end); ну и после вам надо запустить эту функцию для всех соседних времен у вас в списке. Так вы получите непрерывные интервалы.
    – tym32167
    22 фев 2020 в 1:10

2 ответа 2

2

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

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

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

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

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

3
  • Все промежутки больше определенного порога считаются разрывами, любое время, хоть год. Да конечно же промежутки будут идти неравномерно. 22 фев 2020 в 14:07
  • Нет ни о каких средних задержках речь не идет, суть проста, нужно понять когда человек перестал работать с файлом, а когда он его редактирует непрерывно (с перерывами не более нного времени, например в минуту и более) 22 фев 2020 в 14:09
  • 1
    @Дмитрий Гвоздь - в таком случае что мешает просто считать разницу между двумя последующими событиями и принимать решение в зависимости от того, больше или меньше оно выбранного вами порога ("например в минуту и более") ?
    – passant
    23 фев 2020 в 16:11
1

Я бы решал в лоб. Создать 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'))]

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.