Вопрос:
Я создаю приложение Django, предназначенное для поддержания расписания (расписание) для 10K + лиц (и многое другое в будущем). В основном, проблема заключается в следующем: у каждого человека есть отдельное расписание со свободными слотами на следующий год. Он дискретный с шагом 15 минут. Мне нужно разработать архитектуру моделей (которая будет подразумевать структуру базы данных внизу), чтобы сделать следующее:
- Запросить все свободные временные интервалы для данного человека.
- Запросить всех лиц, которые свободны в течение определенного времени.
Например, у меня есть Джон, который свободен от 8 AM-14PM 14 ноября и Сара, которая свободна с 10 утра до 11 утра 14 ноября. Если я запрошу у Джона свободные временные интервалы, я хочу получить “8 AM-14PM 14 ноября”. Если я запрошу “свободных лиц с 8 утра до 11 утра”, я получаю Джона, поскольку Сара не свободна до 10 утра. Если я запрошу “свободных лиц с 10 утра до 11 утра”, я хочу получить как Джона, так и Сару.
Я думал об этой проблеме, и мои идеи ниже.
Решение №1: Мы создаем модель FreeTimeSlot, которая будет хранить информацию о каждом 15-минутном интервале времени и строить по отношению к нему от человека.
class Person(models.Model): name = models.CharField(max_length=32, null=False, blank=False) free_slots = models.ManyToManyField(FreeTimeSlot, related_name=’tutor_set’, null=True, blank=True, through=’PersonSlot’) class TimeSlot(models.Model): time = models.DateTimeField(db_index=True) #perhaps other field type class PersonSlot(models.Model): person = models.ForeignKey(Person) timeslot = models.ForeignKey(Slot) class Meta: db_table = ‘person_free_slots’ unique_together = ((‘timeslot’, ‘person’))
Мы создаем модели TimeSlot 365 * 24 * 4 для каждых 15-минутного интервала в предстоящем году, и если человек укажет в своем расписании свободное время, мы добавим отношение к этому TimeSlot.
С такой архитектурой получение бесплатных временных интервалов для человека так же просто, как и управление менеджером: person.free_time_slots
Получение всех людей бесплатно в определенное время (например, 10-10: 45) также довольно легко, сглаживание, например:
timeslots = TimeSlot.objects.filter(time__in=[’10:00′, ’10:15′, ’10:30′]) PersonSlot.objects.filter(timeslot__in=timeslots).values(‘person’)
Решение №2:
Мы избегаем создания модели для каждого временного интервала, но сохраняем дату в самой модели PersonTime:
class Person(models.Model): name = models.CharField(max_length=32, null=False, blank=False) class TimeSlot(models.Model): person = models.ForeignKey(Person, related_name=’slots’) time_start = models.DateTimeField(db_index=True) time_end = models.DateTimeField(db_index=True)
Получение списка бесплатных временных интервалов также легко (person.slots). Получение всех свободных лиц в определенное время (например, 10-10: 45) было бы следующим:
TimeSlot.objects.filter(time_start__gte=»10:00″, time_end__lte=»10:45″).values(‘person’)
Это решение не будет работать с пересекающимися интервалами, и я не уверен, что запрос на индексированное время для интервала (с использованием сопоставлений gte и lte в одном и том же поле) будет работать и будет работать быстро. Я использую Postgres, если это может иметь значение. Я также писал временные запросы в псевдокоде, чтобы сделать код более простым.
Итак, мой вопрос заключается в следующем: как хорошие разработчики django могли бы реализовать эту функцию, чтобы обеспечить скорость для обоих запросов на больших данных? Я был бы признателен за советы по возможным оговоркам/преимуществам моих текущих решений или новых идей.
Ответ №1
Разделим этот вопрос на две части.
Содержание
Часть 1 – Кодирование данных
Рассмотрим кодирование данных, относящихся к временным интервалам. Если вам нужна точность в 15 минут, у вас есть 96 слотов (4 слота в 1 час * 24 часа в день) с продолжительностью 15 минут в любой день. Каждый слот может иметь одно из двух возможных состояний: 1 – слот свободен, 0 – слот занят (или наоборот, если хотите). Таким образом, вы можете представлять ежедневное расписание со строкой 0 и 1 s. Например, строка (пробелы, добавленные только для удобства чтения) 0000 0000 0000 0000 0000 0000 0000 0000 0000 1110 0000 … представляет собой занятый временной интервал между 00:00 и 09:00 (никто не работает ночью), а затем свободный промежуток времени между 9:00 и 9: 45AM (три 1 подряд), за которым следует загруженный временной интервал, начинающийся с 9:45 утра.
Итак, вы можете написать свои модели следующим образом:
class Person(models.Model): name = models.CharField(max_length=32) class DailySchedule(models.Model): person = models.ForeignKey(Person, related_name=’day_schedule’) date = models.DateField() schedule = models.CharField(max_length=96)
Часть 2 – Запрос
Итак, мы закодировали информацию о доступных слотах времени ожидания/занятости, но как мы можем извлечь ее из базы данных? К счастью, Django имеет возможность поиска полей regex! И, к счастью, он поддерживается в Django 1.4!!
Таким образом, чтобы найти того, кто доступен в течение определенного временного интервала, вы можете использовать DailySchedule.objects.filter(date=date, schedule__regex=r'<expression>’). Поскольку не очевидно, какое выражение использовать для извлечения разных таймфреймов, нам понадобится вспомогательная функция:
def time_slot_to_regex(start_time, end_time): # times should be in HH:MM format start_hour, start_minutes = start_time.split(‘:’) end_hour, end_minutes = end_time.split(‘:’) slots_before_needed_time = (int(start_hour)*4 + int(start_minutes)/15) # compute how many hours are between given times and find out nr of slots hour_duration_slots = (int(end_hour) — int(start_hour)) * 4 # 4 slots in each hour # adjust nr of slots according to minutes in provided times. # e.g. 9:30 to 10:45 — we have 10-9=1 hour, which is 4 time slots, # but we need to subtract 2 time slots, because we don’t have 9:00 to 10:00, # but 9:30 to 10:00 so we subtract 30/15=2 timeslots and add what is left # from the incomplete hour of 10:45 time, which is 45/15 minutes = 3 slots minute_duration_slots = int(end_minutes)/15 — int(start_minutes)/15 total_duration = hour_duration_slots + minute_duration_slots regular_expression = r’^[01]{%d}1{%d}’ % (slots_before_needed_time, total_duration) return regular_expression
Определите, как работает эта функция
Предположим, мы хотим узнать, кто доступен между 9:15 и 9:45. Назовем slots_expression = time_slot_to_regex(‘9:15’, ‘9:45’), который вычисляет:
- slots_before_needed_time = 37, который мы получили, умножив 9 на 4 + 15/15. Это количество слотов, которые нам не нужны, которые войдут в первую часть нашей строки regular_expression – ‘^[01]{37}’
- hour_duration_slots = 0, потому что час в обоих значениях времени одинаковый
- minute_duration_slots = 2, который мы получили путем вычитания 15/15 из 45/15
- previous 2 добавляет вместе 2 слота, которые нам нужно установить в 1 в нашем regular_expression, получив ‘^[01]{37}1{2}’
Теперь мы можем предоставить это регулярное выражение нашему фильтру, получив DailySchedule.objects.filter(schedule__regex=slots_expression) и voila!, результат получим.
Сохранение процесса обработки данных
Я описал принцип кодирования данных, но не упомянул процесс его кодирования. Это можно сделать легко, используя другую функцию поддержки, которая берет строку существующих занятых/доступных слотов и start_date и end_date, для которых необходимо обновить существующее расписание. Если вам также нужен этот метод, сообщите мне.
Pros
- нет отношения M2M, что приводит к более быстрым запросам
- может искать несколько свободных временных интервалов в течение дня, используя другое регулярное выражение (например, ^[01]{36}1{4}[01]{24}1{4} будет искать людей, которые доступны с 9AM до 10AM и с 4PM до 5PM
- относительно простая реализация
- в качестве побочного эффекта у вас будет более легкий доступ, чтобы узнать занятые временные интервалы, поскольку у вас будет необходимая информация в базе данных, и для этого не потребуется выполнять вычисления
Против
- не многословный, а для некоторых это может ввести в заблуждение
- требуется больше места в базе данных, так как вы собираетесь сохранять как свободные, так и занятые временные интервалы
