Эффективное определение, если бизнес открыт или нет, основываясь на часах работы магазина

Question

Учитывая время (например, в настоящее время 16:24 во вторник), я хотел бы иметь возможность выбрать все предприятия, которые в настоящее время открыты из набора предприятий.

• У меня есть время открытия и закрытия для каждого бизнеса на каждый день недели
• Предположим, что бизнес может открываться / закрываться только на 00, 15, 30, 45-минутных отметках каждого часа
• Я предполагаю одно и то же расписание каждую неделю.
• Меня больше всего интересует возможность быстрого поиска группы предприятий, которая открыта в определенное время, а не требований к объему данных.
• Имейте в виду, некоторые мои открыты в 11 вечера один день и закрываются в 1 час ночи на следующий день.
• Каникулы не имеют значения - я займусь этим отдельно

Какой самый эффективный способ хранения времени открытия / закрытия, чтобы с помощью одного кортежа времени / дня недели я мог быстро выяснить, какие предприятия открыты?

Я использую Python, SOLR и mysql. Я хотел бы иметь возможность делать запросы в SOLR. Но, честно говоря, я открыт для любых предложений и альтернатив.

Answer 1

Если вы хотите просто смотреть на одну неделю за раз, вы можете канонизировать все времена открытия / закрытия, чтобы установить количество минут с начала недели, скажем, в воскресенье 0 часов. Для каждого магазина вы создаете несколько кортежей в форме [startTime, endTime, storeId]. (Для часов, которые охватывали полночь воскресенья, вам нужно было бы создать два кортежа, один на конец недели, а другой на начало недели). Этот набор кортежей будет проиндексирован (скажем, с деревом, которое вы предварительно обработаете) как в startTime, так и в endTime. Кортежи не должны быть такими большими: в неделю есть всего ~ 10 тыс. Минут, которые могут уместиться в 2 байта. Эта структура была бы изящной в таблице MySQL с соответствующими индексами и была бы очень устойчивой к постоянным вставкам и удалениям записей при изменении информации. Ваш запрос будет просто «выбрать storeId, где startTime <= время и время окончания> = время», где время было канонизированными минутами с полуночи в воскресенье.

Если информация меняется не очень часто, и вы хотите, чтобы поиск выполнялся очень быстро, вы можете решить все возможные запросы заранее и кэшировать результаты. Например, в неделю есть только 672 четвертьчасовых периода. Имея список предприятий, у каждого из которых был список времени открытия и закрытия, например, решение Брэндона Роудса, вы можете просто перебирать каждый 15-минутный период в неделю, выяснять, кто открыт, и затем сохранять ответ в справочной таблице или список в памяти.

Answer 2

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

Вместо этого я бы попытался сохранить значения как datetime внутри списка:

openclosings = [ open1, close1, open2, close2, ... ]

Тогда я бы использовал функцию Python "bisect_right ()" во встроенном модуле "bisect", чтобы за короткое время O (log n) найти, где в этом списке "подходит" время вашего запроса. Затем посмотрите на индекс, который возвращается. Если это четное число (0, 2, 4 ...), то время находится между одним из «закрытых» и следующим «открытым» временем, поэтому магазин закрывается. Если вместо этого индекс деления пополам представляет собой нечетное число (1, 3, 5 ...), то время между временем открытия и закрытия и магазин открыт.

Не так быстро, как растровые изображения, но вам не нужно беспокоиться о разрешении, и я не могу придумать другое решение O (log n), которое столь же элегантно.

Answer 3

Вы говорите, что используете SOLR, не заботитесь о хранилище и хотите, чтобы поиск выполнялся быстро. Затем вместо хранения открытых / закрытых кортежей индексируйте запись для каждого открытого блока времени на необходимом уровне детализации (15 минут). Для самой кодировки вы можете использовать только совокупные часы: минуты.

Например, магазин, открытый с 16 до 17 часов в понедельник, будет иметь индексированные значения, добавленные для [40:00, 40:15, 40:30, 40:45]. Запрос в 16:24 в понедельник будет нормализован до 40:15 и, следовательно, соответствует этому документу хранилища.

На первый взгляд это может показаться неэффективным, но это относительно небольшой постоянный штраф за индексирование скорости и пространства. И делает поиск максимально быстрым.

Answer 4

Извините, у меня нет простого ответа, но я могу вам сказать, что, будучи менеджером команды разработчиков в компании в конце 90-х годов, нам было поручено решить эту проблему, и это было Сложно.

Это не жесткие часы в неделю, которые можно сделать с помощью относительно небольшой битовой маски (168 бит = 1 в час недели), дело в том, что предприятия закрываются каждый чередующийся вторник.

Начиная с битовой маски, затем переходя к полю исключений, является лучшим решением, которое я когда-либо видел.

Answer 5

В вашем индексе Solr вместо того, чтобы индексировать каждый бизнес как один документ с часами, индексируйте каждую «розничную сессию» для каждого бизнеса в течение недели.

Например, если кофе Джо открыт с понедельника по субботу с 6:00 до 21:00 и закрыт в воскресенье, вы должны проиндексировать шесть отдельных документов, каждый с двумя индексированными полями «открыть» и «закрыть». Если ваши единицы измерения - 15-минутные интервалы, то значения могут находиться в диапазоне от 0 до 7 * 24 * 4. Предполагая, что у вас есть уникальный идентификатор для каждой компании, сохраните его в каждом документе, чтобы можно было сопоставить сеансы с предприятиями.

Тогда вы можете просто выполнить поиск диапазона в Solr:

открыть: [* К N] И закрыть: [N + 1 К *]

где N вычисляется для N-го 15-минутного интервала, в который попадает текущее время. Например, если в среду 10:10, ваш запрос будет:

открыть: [* до 112] и закрыть: [113 до *]

aka «найти сеанс, который начинается в 10:00 или раньше и заканчивается в 10:15 или позже»

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

Answer 6

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

Answer 7

Если вы хорошо контролируете свои данные, я вижу простое решение, похожее на @ Sebastian's. Следуйте советам по созданию кортежей, за исключением того, что создайте их в форме [time = startTime, storeId] и [time = endTime, storeId], затем отсортируйте их в списке. Чтобы узнать, открыт ли магазин, просто сделайте запрос, например:

select storeId
from table
where time <= '@1'
group by storeId
having count(storeId) % 2 == 1

Чтобы оптимизировать это, вы можете построить справочную таблицу в каждый момент времени t, хранить магазины, открытые в t, и открытия / закрытия магазинов между t и t + 1 (для любой группировки t).

Однако этот недостаток заключается в том, что его сложнее поддерживать (перекрывающиеся отверстия / закрытия должны быть объединены в более длительный период открытия-закрытия).