Как правильно сгруппировать данные по временным границам?

Question

[kyckos]

Добрый день.
У нас есть модель с примерными данными

id  DateTime                  Value
133 "2015-04-17 12:12:54 +04" 23
134 "2015-04-17 12:13:54 +04" 23
135 "2015-04-17 12:23:54 +04" 23
136 "2015-04-17 12:44:54 +04" 25
137 "2015-04-17 14:52:54 +04" 42
138 "2015-04-17 15:45:54 +04" 42

Нам нужно запросить все записи чей DateTime не пересекается с ближайшими записями в пределах 15 минут.
Т.е 133 подходит
136 подходит так как 44 - 23 > 15 минут
137 и 138 да остальные нет.
Наверное это задача кластеризации, т.е нужно сформировать группы записей с границами в 15 минут. Если более 15 минут то это новый кластер. Проблема в том что я не знаю как это реализовать в виде корректного алгоритма :/.

Наверное нужно что то вроде этого.
Псевдопитонокод

last_row_date_time = datetime.datetime()
groups = [] #Distinct groups
for row in Data.objects.all().order_by('datetime')
     if (row.datetime - last_row_date_time) > datetime.timedelta(minutes=15)
         groups.append(row)
         print "New group"
     else:
         print "Old group"

Но я не понимаю насколько это корректное решение. Возможно есть какие-то более оптимальные способы решения задачи?

Comments

[Евгений Петров]

А хранить в UNIX-формате (миллисекунды) невозможно?)

[kyckos]

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

Answer 1

[Максим Кудрявцев]

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

Решение в лоб - организовать перебор. По шагам:

1. Берем элемент N
   
2. Проверяем существует ли элемент N-1(обработка первого элемента)
   
3. Берете dataTime элемента N и вычитайте из него 15 минут(переменная time_minus)
   
4. Берем dataTime элемента N-1 и сравниваем с time_minus. Если он меньше - ставите некий флаг, пусть semi_result_minus, в истину
   
5. Проверяем существует ли элемент N+1(обработка последнего элемента)
   
6. Берете dataTime элемента N и прибавляйте к нему 15 минут(переменная time_plus)
   
7. Берем dataTime элемента N+1 и сравниваем с time_plus. Если он меньше - ставите некий флаг, пусть semi_result_plus, в истину
   
8. Если обе переменные semi_result_minus и semi_result_plus имеют истинное значение - текущий элемент N соответствует Вашим критериям, значит включайте его в результат
   

Вам отдельно нужно будет подумать как быть, если Вы работайте с первым и последним элементом, т.к. в этом случае одна из Ваших semi_ переменных точно будет иметь ложное значение.

Answer 2

[sakuradaj]

Если переменная -+15 минут меняться не будет и у вас сейчас в базе не огромное количество данных и вы можете переписать их добавление то:

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

А новые записи кластеризовать при добавлении:
перед добавлением новой записи сделать выборку записей которые "+-15 минут от now".
Проверить найденные записи на наличие групп:
Если группы есть то искать те в которых все записи "+-15 минут от now", если не нашли то создаем новую и привязываем запись.
Группа - это M2M связь.
Возможно понадобятся какие-то блокировки в момент добавления и поиска групп.
Решение которое тут же пришло в голову, может что-то упустил.