Умеет даже такие штуки как
"каждый второй четверг месяца санитарный день", "по субботам с 9pm до последнего клиента", "от заката до рассвета", "в зимнее время года в будни по предварительной записи если не государственный праздник". Есть формальная грамматика, есть библиотеки примерно для всего, есть онлайн редактор/валидатор.
Здравствуйте, Sinclair, Вы писали:
S>Эффективно нужно уметь выполнять одну операцию: GetNextOccurence(TimeStamp start, TimeZone zone) — найти следующее срабатывание после заданного момента времени.
S>В общем, кто имел дело с библиотеками кода для подобной задачи — накидайте ссылок на то, что вам понравилось.
Здравствуйте, Sinclair, Вы писали:
A>>А если человек путешествует через таймзоны вслед за солнцем с устройством, адаптирующимся под таймзоны по сети? У него НГ будет в расписании столько раз, сколько он зон пересёк? S>Конечно. Вы так говорите, как будто ни разу в новый год не летали A>> Может я, конечно, что-то не понимаю, но передача таймзоны параметром выглядит для меня как алярм. A>>Конкретно, мне интересно, что будет, если мы используем такую функцию в банк-клиенте для запланированных платежей, если событие случится перед вылетом и после. S>Ну, в таком случае разработчика нужно будет пожурить на пост-мортеме. S>Потому что S>а) запланированные платежи должен делать банк-сервер, а не банк-клиент. Банк-клиент — штука ненадёжна. А если у него батарейка села? Или интернета нет? Пока я в самолёте летел, значит, мало того, что часовой пояс сменился, так и запланированный платёж за билайн не прошёл, и я теперь остался без связи (а, заодно, и без возможности воспользоваться банк-клиентом для ручного проведения платежа) S>б) планирование платежей в часовом поясе устройства — не очень годная идея. Там будет часовой пояс банка.
Ну а если банк-сервер переедет в другой часовой пояс? (Не физически, понятно, а федеральным законом). Аккурат с той даты, когда платёж.
А если на клиенте я запланировал дорогую операцию не финансового, а технологического характера, и в результате попал на расходы?
А если я настроил запрос на сервис по авторассылке уникальных открыток, и ВСЕ контакты получили по паре разных якобы-от-души поздравлений, показав, что мне на самом деле на них наплевать? (Такой запрос нельзя запланировать на стороннем открыточно-генерирующем сервере, по аналогии с переносом из банк-клиента, т.к. отправка сообщений должна быть с клиентского мессенджера).
В общем, если бы я проектировал такие штуки, я бы подумал о том, чтобы при создании ивента изначально учитывать таймзону и записывать абсолютное время срабатывания, а при смене таймзоны на девайсе перерасчитывать все ивенты. И таким образом гарантировать, что ежемесячно это ежемесячно, а НГ состоится один раз в году, а не 17. Для всех применений, от малозначительных до критических.
Ещё, как вариант, таймзону сделать advanced-параметром при создании ивента, и пусть ответственность будет на юзере. Или совместить этот вариант с предыдущим, сделав по дефолту значение таймзоны "current", но давая выбрать самому.
Здравствуйте, Sinclair, Вы писали:
S> б) расход места. Банальное "рабочиеДни" превратится в ~1000 строк, даже если ограничиться 30 годами в будущее.
По-моему персиситить такие данные неверно. Оно же меняется постоянно. Скажем, емнип, в последние несколько лет таймзоны в России, переходы на летнее-зимнее время менялись раз пять. Или внезапно организованные выходные дни (королева умерла — побыстрому организовали государственный выходной). Так что тут не только функцию расчёта надо сочинить, но и правильную инфраструктуру, которая следит за изменениями в календарях и таймзонах.
Здравствуйте, Sinclair, Вы писали:
S>Всем привет. S>Ищу наиболее удобную, полноценную и эффективную реализацию описания расписаний. S>Язык можно более-менее любой — всё равно будем переписывать на целевой язык. S>Под расписанием понимается то же, что обычно — регулярное событие, со всякими плюшками: "третий четверг апреля", "первый рабочий день каждого месяца", "последняя пятница августа", "каждый вторник", "каждый 256й день года", и так далее.
S>Эффективно нужно уметь выполнять одну операцию: GetNextOccurence(TimeStamp start, TimeZone zone) — найти следующее срабатывание после заданного момента времени.
S>В общем, кто имел дело с библиотеками кода для подобной задачи — накидайте ссылок на то, что вам понравилось.
S>Язык можно более-менее любой — всё равно будем переписывать на целевой язык.
Синтаксис крон, есть либы минимум под дотнет и джаву.
S>Под расписанием понимается то же, что обычно — регулярное событие, со всякими плюшками: "третий четверг апреля", "первый рабочий день каждого месяца", "последняя пятница августа", "каждый вторник", "каждый 256й день года", и так далее.
Ну вроде все это +- можно.
S>Эффективно нужно уметь выполнять одну операцию: GetNextOccurence(TimeStamp start, TimeZone zone) — найти следующее срабатывание после заданного момента времени.
Тут я хз, сам не впихувал, но использовал, вижу что коллеги в разработке заиспользовали.
A>>А если человек путешествует через таймзоны вслед за солнцем с устройством, адаптирующимся под таймзоны по сети? У него НГ будет в расписании столько раз, сколько он зон пересёк? S>Конечно. Вы так говорите, как будто ни разу в новый год не летали
Будто — не будто, но я сам однажды+давно прошляпил географическую разницу в наступлении DST например, как раз в похожей задачке для расписаний ) Ну да, на постпортем разобрались потом )
Здравствуйте, Sinclair, Вы писали:
S>Ищу наиболее удобную, полноценную и эффективную реализацию описания расписаний… S>Под расписанием понимается то же, что обычно — регулярное событие, со всякими плюшками: "третий четверг апреля", "первый рабочий день каждого месяца", "последняя пятница августа", "каждый вторник", "каждый 256й день года", и так далее. S>Эффективно нужно уметь выполнять одну операцию: GetNextOccurence(TimeStamp start, TimeZone zone) — найти следующее срабатывание после заданного момента времени.
Привет, встречный вопрос такой: а что потом с этим результатом делать?
Про то, что время должен расчитывать "сервер" уже упомянули и я с этим тоже согласен, но есть куча ньюансов: там может, например, случиться переход с "зимнего" времени на "летнее" и заранее узнать (правильно понять), когда же "оно наступит" клиенту не просто (будет ли достаточно выдать точный, но не понятный ответ?). Какой результат ожидается:
Такого-то числа в такое-то время по клиентскому времени ("TimeZone zone")
Такого-то числа в такое-то время по серверному времени? Не ясно, как это внятно описать клиенту (время которого может меняться как угодно).
Через столько-то часов/минут/секунд он данного момента? А если интервал месяцы, будет ли такой ответ иметь смысл?
То есть, для точного ответа на "GetNextOccurence" кажется нужно ещё и понимать, что с этим самым "NextOccurence" будут делать, что от него тожидают, как его будут интерпретировать и как обрабатывать.
Мой опыт работы (основанный на опыте старших коллег) с расписаниями говорит о том, что самое эффективное:
Задать некоторую точность срабатывания
Периодически, в зависимости от указанной выше точности (делённой на два или даже на e или π для пущей точности), на "серверной" стороне проверять: не пора ли?
Далее уже дело техники (контракта) обеспечить, чтобы событие не сработало повторно (при переводе часов или смене часового пояса). Тут можно, например, запоминать дату последнего срабатывания и считать, что если в расписании стоит "каждая пятница в 08:00", то отработанное час назад событие можно пропустить (потому что "пятница", как и "08:00" два раза в день не случается).
Последний пункт сильно зависит от того, что ожидается от срабатывания и на сколько клиент ожидает/понимает (при составлении расписания) особенностей изменения линейного течения времени.
Help will always be given at Hogwarts to those who ask for it.
A>А если человек путешествует через таймзоны вслед за солнцем с устройством, адаптирующимся под таймзоны по сети? У него НГ будет в расписании столько раз, сколько он зон пересёк?
Конечно. Вы так говорите, как будто ни разу в новый год не летали A> Может я, конечно, что-то не понимаю, но передача таймзоны параметром выглядит для меня как алярм. A>Конкретно, мне интересно, что будет, если мы используем такую функцию в банк-клиенте для запланированных платежей, если событие случится перед вылетом и после.
Ну, в таком случае разработчика нужно будет пожурить на пост-мортеме.
Потому что
а) запланированные платежи должен делать банк-сервер, а не банк-клиент. Банк-клиент — штука ненадёжна. А если у него батарейка села? Или интернета нет? Пока я в самолёте летел, значит, мало того, что часовой пояс сменился, так и запланированный платёж за билайн не прошёл, и я теперь остался без связи (а, заодно, и без возможности воспользоваться банк-клиентом для ручного проведения платежа)
б) планирование платежей в часовом поясе устройства — не очень годная идея. Там будет часовой пояс банка.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>В общем, кто имел дело с библиотеками кода для подобной задачи — накидайте ссылок на то, что вам понравилось.
Функционала CRON будет достаточно? Если да, то можно посмотреть на существующие движки.
edit: кстати, насколько я знаю, никто там с оптимизацией не заморачивается, текущая дата-время просто сверяется с паттернами каждую секунду. Это дешевая операция, тем более на нескольких десятках правил.
Здравствуйте, Sinclair, Вы писали:
PD>>В getNext — требуется небольшая память и можно на неопределенный период, но вычислять будешь столько раз, сколько раз она будет вызываться. Может быть, много раз с одними и теми же данными. S>Ну вот да. В моей ментальной модели getNext вызывается много-много-много раз, даже для одного и того же start.
Вчера вечером придумал вот такое. Позволит избежать много вызовов одного и того же.
Во-первых, дадим каждому ивенту свой id
Что-то вроде
class Event {
String formula;
String description;
int id;
}
Каждому Event ассоциируется свой массив массивов (или не массив, скорее, это детали) "растра" этого Event. Но пока он пустой.
Введем единицу растеризации. Скажем, 1 год. А может, 1 месяц. А может, для каждого Event свою. Дальше буду считать, что год.
User будет иметь List или Set из этих Event.
И вот нужно getNext
Ищем этот ивент в его растре в году start. Естественно, не находим.
Вычисляем getNext по формуле . Задача решена.
Одновременно фоновому потоку даем задание растеризовать этот Event на годы от года start до года getNext. Если технически возможно, можно этот поток реализовать в микросервисе, который будет выполняться на другой машине и тем самым не отнимать процессорное время на основной машине. Первое уже найденное значение ему можно тут же и передать, а он пусть найдет остальные в этом году. Естественно, в растре будут только моменты, >= getNext, а предыдущие годы будут пустыми.
Теперь, допустим, понадобилось еще раз получить getNext для этого же ивента с тем же start. Поиск по массиву его вернет.
Теперь, допустим, понадобилось еще раз получить getNext для этого же ивента с большим start. Поиск по массиву либо его вернет, либо нет. Если нет — вычисляем его по формуле, он гарантированно попадет на год, больший года первого вызова (иначе бы мы его нашли в массиве) и фоновому потоку даем задание растеризовать и эти годы.
И т.д.
Добавление юзера к ивенту — добавить к списку ивентов юзера
Удаление юзера из ивента — удалить из списка ивентов юзера. Если у ивента не останется юзеров, можно и сам ивент удалить
Изменение ивента — заменить формулу, возможно и описание заменить и очистить его растр.
Пример
Event.formula : "в полнолуние" // чтобы было "под покровом ночной темноты"
Event.description : "Случайно встретиться с гражданином Корейко на улице.Не бить его ни под каким видом и вообще не применять физического воздействия.Отобрать все, что будет обнаружено в карманах поименованного гражданина".
Event.id = 12345
Юзеры — А. Балаганов и М. Паниковский.
start = 20.11.1928
Первый вызов getNext по формуле потребует провести вычисления по астрономическим формулам, чтобы найти первое полнолуние , начиная с 20.11.1928. Допустим, это 15.12.1928.
Фоновый поток растеризует 1928 год. Скорее всего там будет один элемент — 15.12.1928
Еще раз getNext со start , скажем, 30.11.1928 его вернет
Еще раз getNext со start , скажем, 10.12.1928 его же вернет
Еще раз getNext со start 16.12.1928 ничего не вернет. Значит, надо найти по формуле. Получим, скажем, 15.01.1929. Фоновому потоку дается задание растеризовать 1929 год. Теперь все поиски в 1929 году пойдут через таблицу, и только когда дело дойдет до 1930 года, опять понадобится вычисление по формуле.
Ну и заключительный момент. Еще один фоновый поток работает раз в год 1 января в 0.00 и удаляет растры всех ивентов за прошедший год.
В общем, кеширование с кластеризацией. Этот алгоритм использует Windows при работе чтении файлов. Если делается запрос, то она читает нужное и еще несколько кластеров в кеш, так что следующие запросы будут реализованы из кеша. Ну а если возникнет кеш-промах, то читает из файла и опять несколько кластеров.
Все отличие от твоей задачи, что у тебя вместо чтения — вычисление по формуле, а кеш реализован как таблица растра.
Всем привет.
Ищу наиболее удобную, полноценную и эффективную реализацию описания расписаний.
Язык можно более-менее любой — всё равно будем переписывать на целевой язык.
Под расписанием понимается то же, что обычно — регулярное событие, со всякими плюшками: "третий четверг апреля", "первый рабочий день каждого месяца", "последняя пятница августа", "каждый вторник", "каждый 256й день года", и так далее.
Эффективно нужно уметь выполнять одну операцию: GetNextOccurence(TimeStamp start, TimeZone zone) — найти следующее срабатывание после заданного момента времени.
В общем, кто имел дело с библиотеками кода для подобной задачи — накидайте ссылок на то, что вам понравилось.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Эффективно нужно уметь выполнять одну операцию: GetNextOccurence(TimeStamp start, TimeZone zone) — найти следующее срабатывание после заданного момента времени.
Здравствуйте, Alekzander, Вы писали: A>А можно подробнее про эту функцию?
Ну, идея понятна — расписание это цепочка событий.
Можно рассматривать его API как один енумератор — типа "дай мне все инстансы всех событий".
Но нас как правило интересуют события в каком-то диапазоне — например, мы рисуем страничку календаря; или там ставим таймер ожидания "разбуди меня когда наступит момент Ч".
В этих случаях неудобно итерировать все события из предыстории. Поэтому удобно не просто GetFirst()/GetNext(), а сразу сказать "покажи мне первый запланированный визит на спорт после 8:00 субботы, 20 января".
Ну, и колхозить енумератор, имея такую функцию, смысла не имеет. Зная occurence X, я всегда могу получить следующий за ним при помощи вызова GetNextOccurence(X.Start+X.Duration, ...).
Информация о таймзоне будет нужна для событий, которые "плавают". Например, Новый Год начинается в 0:00 по местному времени, а не по UTC.
Поэтому вопрос "когда чокаться шампанским" не имеет смысла без указания таймзоны.
Может быть, это можно обойти с обратной стороны — считать таймзону частью расписания; тогда в РФ у нас будет 11 комплектов государственных праздников.
Но, имхо, это не очень удобно — удобнее считать, что праздник один, просто у него момент срабатывания зависит от точки зрения.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Всем привет. S>Ищу наиболее удобную, полноценную и эффективную реализацию описания расписаний. S>Язык можно более-менее любой — всё равно будем переписывать на целевой язык. S>Под расписанием понимается то же, что обычно — регулярное событие, со всякими плюшками: "третий четверг апреля", "первый рабочий день каждого месяца", "последняя пятница августа", "каждый вторник", "каждый 256й день года", и так далее.
S>Эффективно нужно уметь выполнять одну операцию: GetNextOccurence(TimeStamp start, TimeZone zone) — найти следующее срабатывание после заданного момента времени.
S>В общем, кто имел дело с библиотеками кода для подобной задачи — накидайте ссылок на то, что вам понравилось.
На вскидку мыслится набор классов каждый из которых представляет конкретный тип расписания(ежегодное, ежедневное, ежемесячное и т.д. плюс способ создания новых расписаний через композицию этих классов, например что бы можно было создать новое расписание объединив месячное и ежедневное расписание. В общем наверху должен быть один экземпляр расписания, который объединяет все. В общем где-то так.
Здравствуйте, Qulac, Вы писали: S>>В общем, кто имел дело с библиотеками кода для подобной задачи — накидайте ссылок на то, что вам понравилось.
Q>На вскидку мыслится набор классов каждый из которых представляет конкретный тип расписания(ежегодное, ежедневное, ежемесячное и т.д. плюс способ создания новых расписаний через композицию этих классов, например что бы можно было создать новое расписание объединив месячное и ежедневное расписание. В общем наверху должен быть один экземпляр расписания, который объединяет все. В общем где-то так.
Ну, у меня проблема не столько в том, чтобы спроектировать это : )
А в том, что
а) покрыть нужное количество сценариев.
б) предусмотреть все неожиданные косяки и частные случаи. Возможно, я что-то упускаю (как обычно бывает, когда начинаешь с наскоку решать "простую и очевидную" задачу. См. например строки в С, С++ или даты в Java)
Поэтому всегда полезно посмотреть на существующие реализации — они лучше любого нового проекта как минимум тем, что их кто-то уже пытался применять в продакшне, и есть опыт, на который можно опереться.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Всем привет. S>Ищу наиболее удобную, полноценную и эффективную реализацию описания расписаний. S>Язык можно более-менее любой — всё равно будем переписывать на целевой язык. S>Под расписанием понимается то же, что обычно — регулярное событие, со всякими плюшками: "третий четверг апреля", "первый рабочий день каждого месяца", "последняя пятница августа", "каждый вторник", "каждый 256й день года", и так далее.
S>Эффективно нужно уметь выполнять одну операцию: GetNextOccurence(TimeStamp start, TimeZone zone) — найти следующее срабатывание после заданного момента времени.
S>В общем, кто имел дело с библиотеками кода для подобной задачи — накидайте ссылок на то, что вам понравилось.
С библиотеками не имел, а студентам нечто подобное давал ("расписание рейсов самолетов"). Правда, без getNext, но с getBetween и т.п. Насчет getNext как-то не подумал, можно добавить, если дам еще раз.
1. Расписание одно на все про все или же для каких-то объектов, которых может быть много ? Например, у каждого юзера свое.
2. Его точно нужно хранить в ОП или можно в БД ?
Студентам давал в варианте хранения в БД. Все эти "третий четверг апреля", "первый рабочий день каждого месяца", "последняя пятница августа", "ежедневно", "по четным", "по нечетным" и т.д. конвертируются в одну или набор DateTime на стадии добавления, а в БД хранятся упорядоченно по времени. А для поиска SELECT WHERE <далее по потребности>
Здравствуйте, Pavel Dvorkin, Вы писали: PD>1. Расписание одно на все про все или же для каких-то объектов, которых может быть много ? Например, у каждого юзера свое.
Может быть много. Возможно, потребуется какая-нибудь алгебра расписаний вроде объединения, пересечения, и т.п.
PD>2. Его точно нужно хранить в ОП или можно в БД ?
Хранение в БД — вторично. Если есть решение в памяти, то записать его в БД можно тривиально. Необходимости уметь искать следующий слот через SQL у меня нет.
PD>Студентам давал в варианте хранения в БД. Все эти "третий четверг апреля", "первый рабочий день каждого месяца", "последняя пятница августа", "ежедневно", "по четным", "по нечетным" и т.д. конвертируются в одну или набор DateTime на стадии добавления, а в БД хранятся упорядоченно по времени. А для поиска SELECT WHERE <далее по потребности>
Ну, это тоже вариант. Но
а) несколько затруднено редактирование такой штуки. Вот мы хотим перенести встречи по четвергам с 14:00 на 17:00. Начиная со следующего четверга. А встречи по вторникам не трогать.
б) расход места. Банальное "рабочиеДни" превратится в ~1000 строк, даже если ограничиться 30 годами в будущее.
Хотя эта идея не так уж и плоха; надо над ней подумать. Возможно, сведение всех манипуляций к генерации списка и будет верным решением.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Студентам давал в варианте хранения в БД. Все эти "третий четверг апреля", "первый рабочий день каждого месяца", "последняя пятница августа", "ежедневно", "по четным", "по нечетным" и т.д. конвертируются в одну или набор DateTime на стадии добавления, а в БД хранятся упорядоченно по времени. А для поиска SELECT WHERE <далее по потребности>
Ещё забыл спросить — а есть полное задание со списком всех вариантов?
Вот оно-то как раз крайне полезно. А как там оно внутри будет устроено — сразу материализовывать, или на ходу вычислять — это уже дело другое.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Вот оно-то как раз крайне полезно. А как там оно внутри будет устроено — сразу материализовывать, или на ходу вычислять — это уже дело другое.
Ну оно далеко не полное. Все же это была учебная задача, и я должен был сообразоваться с временнЫми лимитами на нее.
Могу прислать задание целиком. Сюда выкладывать не буду. Адрес мой в личных.
Здравствуйте, Sinclair, Вы писали:
S>Может быть много. Возможно, потребуется какая-нибудь алгебра расписаний вроде объединения, пересечения, и т.п.
Ну тогда для одного клиента WHERE ... AND id =
А для объединений и перечеений — ИМХО проще брать в Set, а потом его средствами. Хотя, наверное, можно и на SQL.
PD>>2. Его точно нужно хранить в ОП или можно в БД ? S>Хранение в БД — вторично. Если есть решение в памяти, то записать его в БД можно тривиально. Необходимости уметь искать следующий слот через SQL у меня нет.
Ну если выбор из памяти по произвольному условию по DateTime не проблема — можно и в ОП. Но тогда придется хранить в ОП отсортированно по DateTime, а дальше бинарный поиск.
S>а) несколько затруднено редактирование такой штуки. Вот мы хотим перенести встречи по четвергам с 14:00 на 17:00. Начиная со следующего четверга. А встречи по вторникам не трогать.
Просто их все удалить и новые добавить.
S>б) расход места. Банальное "рабочиеДни" превратится в ~1000 строк, даже если ограничиться 30 годами в будущее.
В варианте БД — ну и что ? 1000 строк в таблице — это много ?
S>Хотя эта идея не так уж и плоха; надо над ней подумать. Возможно, сведение всех манипуляций к генерации списка и будет верным решением.
Если в ОП, то скорее массива с бинарным поиском и индексом в виде DateTime. Или дерева. В списке линейный поиск будет медленным.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ну тогда для одного клиента WHERE ... AND id =
Для каждого экземпляра расписаний. PD>А для объединений и перечеений — ИМХО проще брать в Set, а потом его средствами. Хотя, наверное, можно и на SQL.
Это очень дорогая алгебра выходит. На каждую операцию строить множество, а потом снова его сортировать. PD>Ну если выбор из памяти по произвольному условию по DateTime не проблема — можно и в ОП. Но тогда придется хранить в ОП отсортированно по DateTime, а дальше бинарный поиск.
У меня нет задачи по произвольному условию. Есть задача находить ближайшее после указанного timestamp.
PD>Просто их все удалить и новые добавить.
Непонятно, в какой момент добавлять новые.
PD>В варианте БД — ну и что ? 1000 строк в таблице — это много ?
Нет, не много. А вот, скажем, миллион расписаний (а это — ничего особенного. Просто даты начисления процентов для всего-то миллиона накопительных счетов) потребует уже миллиарда строк. PD>Если в ОП, то скорее массива с бинарным поиском и индексом в виде DateTime. Или дерева. В списке линейный поиск будет медленным.
Ну вот я бы всё же хотел получить реализацию с O(1) памяти, а не O(∞).
PD>Но это делать надо, а БД сама сделает.
Не во все задачи можно втащить БД.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Сорри, по класса C# уже не помню, давно с ними не имел дела,искать лень. Имена из Java
PD>>Ну тогда для одного клиента WHERE ... AND id = S>Для каждого экземпляра расписаний.
Ну да, это если для одного
Если для нескольких — WHERE условие AND id IN [...] Но тут уже надо определить, в чем условие заключается и написать его корректно, а то можно вместо O(logN) получить O(N)
PD>>А для объединений и перечеений — ИМХО проще брать в Set, а потом его средствами. Хотя, наверное, можно и на SQL. S>Это очень дорогая алгебра выходит. На каждую операцию строить множество, а потом снова его сортировать.
Зачем его сортировать ? На это TreeSet есть, сразу его и строить, он SortedSet
PD>>Ну если выбор из памяти по произвольному условию по DateTime не проблема — можно и в ОП. Но тогда придется хранить в ОП отсортированно по DateTime, а дальше бинарный поиск. S>У меня нет задачи по произвольному условию. Есть задача находить ближайшее после указанного timestamp.
Тогда в SQL совсем просто : SELECT where timestamp> table.timestamp AND id = ... TOP 1.
При индексе по DateTime будет именно то, что надо
PD>>Просто их все удалить и новые добавить. S>Непонятно, в какой момент добавлять новые.
Трансакцией "удаление — добавление", если БД.
PD>>В варианте БД — ну и что ? 1000 строк в таблице — это много ? S>Нет, не много. А вот, скажем, миллион расписаний (а это — ничего особенного. Просто даты начисления процентов для всего-то миллиона накопительных счетов) потребует уже миллиарда строк.
Для миллиона расписаний будет немало, согласен. Но все равно их хранить надо. Ну и при O(logN) это все же лишь 20 операций.
PD>>Если в ОП, то скорее массива с бинарным поиском и индексом в виде DateTime. Или дерева. В списке линейный поиск будет медленным. S>Ну вот я бы всё же хотел получить реализацию с O(1) памяти, а не O(∞).
Насчет O(1) я сомневаюсь, а вот O(LogN) пока получается.
O(1) можно на HashMap, но у него нет порядка и вряд ли он тут годится.
PD>>Но это делать надо, а БД сама сделает. S>Не во все задачи можно втащить БД.
Ну БД тут только для того, чтобы проще было объяснить идею. Ничего же БД нового в плане алгоритма не вносит. Просто вместо таблицы с INDEX по timestamp дерево с ним же в качестве компаратора
В Java — TreeSet или TreeMap с Comparator
А потом для объединения / пересечения сетов addAll/retainAll
Впрочем, едва ли это понадобится. getNext вернет же не Set, а один элемент. Пересечение их всегда даст либо 0, либо 1 элемент. Объединение — от 1 до миллиона, верно, но тебе точно нужно объединить полученные от getNext DateTime для миллиона расписаний ? .
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ну да, это если для одного PD>Если для нескольких — WHERE условие AND id IN [...] Но тут уже надо определить, в чем условие заключается и написать его корректно, а то можно вместо O(logN) получить O(N)
PD>Зачем его сортировать ? На это TreeSet есть, сразу его и строить, он SortedSet
Ну, так тоже можно. На самом деле всё чуть сложнее, т.к. события — это не точки, а интервалы. И надо строить алгебру интервалов. Но, вроде бы, там непринципиальное изменение сложности.
PD>Тогда в SQL совсем просто : SELECT where timestamp> table.timestamp AND id = ... TOP 1. PD>При индексе по DateTime будет именно то, что надо
Ну, если хочется поговорить об индексах, то индекс по timestamp тут не поможет. Нужен будет индекс по (id, timestamp).
PD>>>Просто их все удалить и новые добавить. S>>Непонятно, в какой момент добавлять новые.
PD>Трансакцией "удаление — добавление", если БД.
Вопрос был не "при помощи чего", а "в какой момент".
Вот я взял и добавил в расписание рабочие дни на ближайшие 5 лет. Потом в какой то момент мне нужно пойти и добавить их ещё на следующие 5 лет.
Или, к примеру, если у нас появился новый государственный праздник, мне нужно догадаться удалить и перегенерировать рабочие дни от сейчас и до какой-то даты.
PD>Для миллиона расписаний будет немало, согласен. Но все равно их хранить надо. Ну и при O(logN) это все же лишь 20 операций.
Нет, не "всё равно". Для O(1) будет миллион строк, а не миллиард.
PD>>>Если в ОП, то скорее массива с бинарным поиском и индексом в виде DateTime. Или дерева. В списке линейный поиск будет медленным. S>>Ну вот я бы всё же хотел получить реализацию с O(1) памяти, а не O(∞). PD>Насчет O(1) я сомневаюсь, а вот O(LogN) пока получается.
Вопрос не в вычислительной сложнности, а в расходе памяти. Так что тут никакого O(LogN). Ну, и вычислительная сложность тут далеко не всегда потребует O(LogN).
Например банальное ежедневное событие, наступающее в 8:00, описывается O(1) функцией вида
TimeStamp GetNextOccurence(TimeStamp start, TimeZone zone)
{
var t = Date(start).AddHours(8);
if (Time(start) > Time.FromHours(8))
t = t.AddDays(1);
return t;
}
PD>Ну БД тут только для того, чтобы проще было объяснить идею.
Тогда утверждение "БД сама сделает" нерелевантно.
PD>Впрочем, едва ли это понадобится. getNext вернет же не Set, а один элемент. Пересечение их всегда даст либо 0, либо 1 элемент. Объединение — от 1 до миллиона, верно, но тебе точно нужно объединить полученные от getNext DateTime для миллиона расписаний ? .
Для миллиона — нет. Но вместо того, чтобы сначала объединять множества, а потом выбирать из них наименьший элемент, больший заданного, можно просто вернуть Min(GetNext(s1), GetNext(s2)). Тогда комбинация двух O(1) расписаний останется O(1).
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Ну, так тоже можно. На самом деле всё чуть сложнее, т.к. события — это не точки, а интервалы. И надо строить алгебру интервалов. Но, вроде бы, там непринципиальное изменение сложности.
Наверное, да.
PD>>Тогда в SQL совсем просто : SELECT where timestamp> table.timestamp AND id = ... TOP 1. PD>>При индексе по DateTime будет именно то, что надо S>Ну, если хочется поговорить об индексах, то индекс по timestamp тут не поможет. Нужен будет индекс по (id, timestamp).
+1
PD>>Трансакцией "удаление — добавление", если БД. S>Вопрос был не "при помощи чего", а "в какой момент". S>Вот я взял и добавил в расписание рабочие дни на ближайшие 5 лет. Потом в какой то момент мне нужно пойти и добавить их ещё на следующие 5 лет.
Ну и добавить новый элемент. Если он не пересекается по датам со старыми, никакой проблемы нет. Если пересекается — создать объединение, удалить старый, добавить новый.
S>Или, к примеру, если у нас появился новый государственный праздник, мне нужно догадаться удалить и перегенерировать рабочие дни от сейчас и до какой-то даты.
Так когда появился, тогда и сделать.
Я не пойму вопрос "в какой момент". По-моему, в тот, когда это изменение актуализируется.
PD>>Для миллиона расписаний будет немало, согласен. Но все равно их хранить надо. Ну и при O(logN) это все же лишь 20 операций. S>Нет, не "всё равно". Для O(1) будет миллион строк, а не миллиард.
Строк будет больше, верно. Но тут решать надо, можно такое себе позволить или нет.
Вообще-то миллион на одного человека за 5 лет — это более 500 событий в день на этого человека .
PD>>>>Если в ОП, то скорее массива с бинарным поиском и индексом в виде DateTime. Или дерева. В списке линейный поиск будет медленным. S>>>Ну вот я бы всё же хотел получить реализацию с O(1) памяти, а не O(∞). PD>>Насчет O(1) я сомневаюсь, а вот O(LogN) пока получается. S>Вопрос не в вычислительной сложнности, а в расходе памяти. Так что тут никакого O(LogN). Ну, и вычислительная сложность тут далеко не всегда потребует O(LogN).
По памяти согласен. В сущности то, что я предлагаю, это "растеризация". То есть вместо "по вторникам в течение 5 лет" будет 5*52 записи. Ну тут надо решать, можно такое себе позволить или нет. Зато потом искать будет просто, а искать по записям типа "по вторникам" или "после дождичка в четверг" сомнительное удовольствие.
S>Например банальное ежедневное событие, наступающее в 8:00, описывается O(1) функцией вида S>
S>TimeStamp GetNextOccurence(TimeStamp start, TimeZone zone)
S>{
S> var t = Date(start).AddHours(8);
S> if (Time(start) > Time.FromHours(8))
S> t = t.AddDays(1);
S> return t;
S>}
S>
Согласен, просто. Вот только это слишком "регулярное событие". Если бы все они были такими или иными, но столь же регулярными, то было бы просто. А если на это "ежедневно в 8.00" наложится еще хотя бы одно такое типа "ежедневно в 18.00" , то все станет менее просто. А если еще и добавится "по нечетным в 13.00", то станет совсем весело искать следующий. Хотя теоретически возможно.
PD>>Ну БД тут только для того, чтобы проще было объяснить идею. S>Тогда утверждение "БД сама сделает" нерелевантно.
Оно лишь означает, что для того, чтобы в БД был O(logN) поиск, достаточно INDEX в таблицу добавить, а если в ОП, то придется это дерево (Set, Map) самому делать. Разница небольшая, конечно, но с БД проще. В конце концов можно же и БД в ОП взять.
PD>>Впрочем, едва ли это понадобится. getNext вернет же не Set, а один элемент. Пересечение их всегда даст либо 0, либо 1 элемент. Объединение — от 1 до миллиона, верно, но тебе точно нужно объединить полученные от getNext DateTime для миллиона расписаний ? . S>Для миллиона — нет. Но вместо того, чтобы сначала объединять множества, а потом выбирать из них наименьший элемент, больший заданного, можно просто вернуть Min(GetNext(s1), GetNext(s2)). Тогда комбинация двух O(1) расписаний останется O(1).
Ну можно и проще. В Java у SortedSet есть метод first, возвращающий минимальный элемент, так что можно и не объединять, а найти минимум из этих first. Должен быть и в C#
Да и множества , возможно, тоже не нужны. Тебе же один элемент нужен , хватит и первый элемент брать.
В общем, резюме ИМХО простое.
Либо то, что я предлагаю, либо хранить список элементов в исходном виде, искать "интеллектуально" минимальный по каждому элементу и минимум этих минимумов. Тоже решение, может быть, и неплохое. Медленнее, конечно, но тут уж надо мерять.
Здравствуйте, Pavel Dvorkin, Вы писали: PD>>>Трансакцией "удаление — добавление", если БД. S>>Вопрос был не "при помощи чего", а "в какой момент". S>>Вот я взял и добавил в расписание рабочие дни на ближайшие 5 лет. Потом в какой то момент мне нужно пойти и добавить их ещё на следующие 5 лет.
PD>Ну и добавить новый элемент. Если он не пересекается по датам со старыми, никакой проблемы нет. Если пересекается — создать объединение, удалить старый, добавить новый.
Ты упорно игнорируешь вопрос. В какой момент мне надо это сделать?
Первичная инициализация — понятно: вот мы конструируем расписание. Например, по запросу пользователя, или по API сервиса такой запрос пришёл.
После этого идут запросы только к GetNext. Ну и как мне понять, что наступил момент для "удалить старый, добавить новый"?
PD>Так когда появился, тогда и сделать.
И? Каков будет алгоритм работы? "Как-то" найти в системе все экземпляры расписаний, которые зависят от расписания государственных праздников, и их перегенерировать?
PD>Я не пойму вопрос "в какой момент". По-моему, в тот, когда это изменение актуализируется.
Вижу, что не понимаешь. Что значит "актуализируется"? Вот пример выше — у нас есть 500к расписаний, которые зависят от расписания государственных праздников. В архитектуре вычисляемых событий мы просто изменяем один экземпляр, на который ссылаются все эти полмиллиона остальных экземпляров, и за O(1) получаем 500к обновлённых расписаний.
Для случая материализации у нас полмиллиарда "строчек", которые нужно
а) найти по какому-то признаку (по какому? как мы вообще поймём, что расписание с ID = 1472 было построено с учётом расписания государственных праздников?)
б) удалить
в) нагенерировать новых.
Ладно, чёрт с ним с обновлением. Просто у нас есть расписание начисления процентов, в котором было 1000 строк.
Как мы поймём, что пора добавить в него ещё 1000 строк? По какому критерию?
Как мы будем "догенерировать" строчки к существующему расписанию? Ну вот была у нас некая функция CreateDailySchedule(Time timeOfDay). Она вернула нам ID сгенерированного расписания (или там ссылку на экземпляр таблицы событий в памяти). Она нам наплодила сколько-то строчек (сколько? даже это пока непонятно). Как будет выглядеть сигнатура функции, которая должна к этой таблице добавить продолжение? Как она будет устроена внутри? В какой момент и кто будет её вызывать?
PD>А тут пока что нет O(1). Дерево же.
У дерева размер O(N).
PD>Согласен, просто. Вот только это слишком "регулярное событие". Если бы все они были такими или иными, но столь же регулярными, то было бы просто. А если на это "ежедневно в 8.00" наложится еще хотя бы одно такое типа "ежедневно в 18.00" , то все станет менее просто.
Нет, не станет. Потому, что у нас появляется Union(Schedule s1, Schedule s2), у которого GetNextOccurence устроен вот так:
Имеем O(1) по памяти, O(1) по времени работы. Вроде ж не rocket science, не?
PD>А если еще и добавится "по нечетным в 13.00", то станет совсем весело искать следующий. Хотя теоретически возможно.
Добавление чего угодно работает ровно так, как я показал. Ну будет Union(Union(dailyAt0800, dailyAt1800), evensAt1300).
Остаётся вопрос, как реализовать evensAt1300. Но пока что у нас получалось сделать всё за O(1) и по времени, и по памяти, в связи с чем есть искушение продолжать думать в эту сторону.
Вместо того, чтобы моментально сдаться и перейти к O(log(N)) по времени и O(N) по памяти.
PD>Оно лишь означает, что для того, чтобы в БД был O(logN) поиск, достаточно INDEX в таблицу добавить, а если в ОП, то придется это дерево (Set, Map) самому делать. Разница небольшая, конечно, но с БД проще. В конце концов можно же и БД в ОП взять.
Пока что получается, что мы сначала берём неэффективный алгоритм, а потом в него добавляем накладные расходы от самой СУБД. Асимптотика-то не поменяется, а вот коэффициенты перед O будут примерно 1000 — это для СУБД в памяти. Не очень понятен ход мысли, который приводит к таким архитектурным решениям.
PD>Да и множества , возможно, тоже не нужны. Тебе же один элемент нужен , хватит и первый элемент брать.
Вот то-то и оно.
Но тут дело не в Java и не в C# — всё это будет вообще ни на одном из этих языков. Первична сама архитектура, а реализацию потом напилим как надо.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
A>>А можно подробнее про эту функцию? S>Ну, идея понятна — расписание это цепочка событий. S>Можно рассматривать его API как один енумератор — типа "дай мне все инстансы всех событий". S>Но нас как правило интересуют события в каком-то диапазоне — например, мы рисуем страничку календаря; или там ставим таймер ожидания "разбуди меня когда наступит момент Ч". S>В этих случаях неудобно итерировать все события из предыстории. Поэтому удобно не просто GetFirst()/GetNext(), а сразу сказать "покажи мне первый запланированный визит на спорт после 8:00 субботы, 20 января". S>Ну, и колхозить енумератор, имея такую функцию, смысла не имеет. Зная occurence X, я всегда могу получить следующий за ним при помощи вызова GetNextOccurence(X.Start+X.Duration, ...).
S>Информация о таймзоне будет нужна для событий, которые "плавают". Например, Новый Год начинается в 0:00 по местному времени, а не по UTC. S>Поэтому вопрос "когда чокаться шампанским" не имеет смысла без указания таймзоны. S>Может быть, это можно обойти с обратной стороны — считать таймзону частью расписания; тогда в РФ у нас будет 11 комплектов государственных праздников. S>Но, имхо, это не очень удобно — удобнее считать, что праздник один, просто у него момент срабатывания зависит от точки зрения.
А если человек путешествует через таймзоны вслед за солнцем с устройством, адаптирующимся под таймзоны по сети? У него НГ будет в расписании столько раз, сколько он зон пересёк? Может я, конечно, что-то не понимаю, но передача таймзоны параметром выглядит для меня как алярм.
Конкретно, мне интересно, что будет, если мы используем такую функцию в банк-клиенте для запланированных платежей, если событие случится перед вылетом и после.
Здравствуйте, Sinclair, Вы писали:
S>Вижу, что не понимаешь. Что значит "актуализируется"? Вот пример выше — у нас есть 500к расписаний, которые зависят от расписания государственных праздников. В архитектуре вычисляемых событий мы просто изменяем один экземпляр, на который ссылаются все эти полмиллиона остальных экземпляров, и за O(1) получаем 500к обновлённых расписаний. S>Для случая материализации у нас полмиллиарда "строчек", которые нужно S>а) найти по какому-то признаку (по какому? как мы вообще поймём, что расписание с ID = 1472 было построено с учётом расписания государственных праздников?) S>б) удалить S>в) нагенерировать новых.
Вот теперь понял. Да, в таком виде легко не получится. Я-то полагал, что элемент расписания самодостаточен, и полностью описывает время и дату. Например, "по вторникам" с... по ... — это фиксированный набор дат, ни от чего не завмсящий. Если элементы могут зависеть от каких-то прочих факторов, которые могут изменяться, то легко не получится — разве только удалить растр по всем таким элементам и создать заново.
S>Ладно, чёрт с ним с обновлением. Просто у нас есть расписание начисления процентов, в котором было 1000 строк. S>Как мы поймём, что пора добавить в него ещё 1000 строк? По какому критерию? S>Как мы будем "догенерировать" строчки к существующему расписанию? Ну вот была у нас некая функция CreateDailySchedule(Time timeOfDay). Она вернула нам ID сгенерированного расписания (или там ссылку на экземпляр таблицы событий в памяти). Она нам наплодила сколько-то строчек (сколько? даже это пока непонятно). Как будет выглядеть сигнатура функции, которая должна к этой таблице добавить продолжение? Как она будет устроена внутри?
Теперь опять не понимаю. Она наплодила не неизвестно сколько строчек, а столько строчек, сколько дней в интервале, в котором она наплодила. Скажем, с 1 марта по 31 марта — 31 строчку. Если нужно добавить новые , скажем, с 1 апреля по 30 апреля, то добавить новое расписание, которое растеризуется в 30 строк.
>В какой момент и кто будет её вызывать?
По-видимому, в тот момент, когда нужно добавить данные на апрель. А кто будет вызывать для исходного расписания и когда ?
PD>>А тут пока что нет O(1). Дерево же. S>У дерева размер O(N).
PD>>Согласен, просто. Вот только это слишком "регулярное событие". Если бы все они были такими или иными, но столь же регулярными, то было бы просто. А если на это "ежедневно в 8.00" наложится еще хотя бы одно такое типа "ежедневно в 18.00" , то все станет менее просто. S>Нет, не станет. Потому, что у нас появляется Union(Schedule s1, Schedule s2), у которого GetNextOccurence устроен вот так: S>
S>Имеем O(1) по памяти, O(1) по времени работы. Вроде ж не rocket science, не?
Верно. Только вот GetNextOccurence будет намного сложнее. И более того, ее придется, возможно, вызывать много раз для одних и тех же данных. А она внутри должна не просто взять минимальный элемент, а по фразе "после дождичка в четверг" найти этот ближайший четверг, в который ожидается дождик, проверить, что после него, а не до, и если не выйдет — брать следующий четверг и для него то же самое. И в следующий раз опять то же. Как тут кешировать — я не очень понимаю.
PD>>А если еще и добавится "по нечетным в 13.00", то станет совсем весело искать следующий. Хотя теоретически возможно. S>Добавление чего угодно работает ровно так, как я показал. Ну будет Union(Union(dailyAt0800, dailyAt1800), evensAt1300).
Будет, будет. С перевычислением их всех на каждом GetNext
S>Остаётся вопрос, как реализовать evensAt1300. Но пока что у нас получалось сделать всё за O(1) и по времени, и по памяти, в связи с чем есть искушение продолжать думать в эту сторону.
S>Пока что получается, что мы сначала берём неэффективный алгоритм, а потом в него добавляем накладные расходы от самой СУБД. Асимптотика-то не поменяется, а вот коэффициенты перед O будут примерно 1000 — это для СУБД в памяти. Не очень понятен ход мысли, который приводит к таким архитектурным решениям.
Ход мысли простой. Либо решать в векторной форме, либо в растровой.
Представь себе, что тебе нужно найти некую точку на экране (то есть в дискретном пространстве), через которую проходит некая y=f(x) при x1<x<x2. Ну хотя бы с min(y). Аналитически задача не решается.
Решений 2
1. Когда это нужно, найти y для всех x из (x1, x2) и минимум
2. предварительно записать в массив Point все точки (x,y) и искать в нем.
Плюс для (1) — намного меньше памяти.
Минус — если это понадобится делать 100500 раз, то и вычмслять y придется 100500 раз. А если еще и кривых 100500, то совсем весело.
Минус для (2) — намного больше памяти
Плюс для (2) — вычислять придется 1 раз, а потом сколько раз не делай поиск, вычислять функцию не надо
Здравствуйте, Sinclair, Вы писали:
S>б) расход места. Банальное "рабочиеДни" превратится в ~1000 строк, даже если ограничиться 30 годами в будущее.
Банальное "рабочиеДни" должно зависеть от страны пребывания, если событие ориентировано/связано с этой страной, в общем случае должна быть связь со страной, где событие происходит — например, ты из России, находишься в ОАЭ, но тебе надо каждый первый рабочий день месяца пречислять деньги мобильному оператору в Зимбабве, то рабочие дни надо учитывать по зимбабвийскому трудовому календарю.
И да, на 30 лет я хз как расчитать, у нас трудовой календарь выпускают только на следующий год незадолго до окончания текущего
PD>Вот теперь понял. Да, в таком виде легко не получится. Я-то полагал, что элемент расписания самодостаточен, и полностью описывает время и дату. Например, "по вторникам" с... по ... — это фиксированный набор дат, ни от чего не завмсящий. Если элементы могут зависеть от каких-то прочих факторов, которые могут изменяться, то легко не получится — разве только удалить растр по всем таким элементам и создать заново.
Дело не только в том, чтобы удалить и создать. Если бы это была БД, как ты предлагаешь, это всё ещё те же самые delete и insert.
Вопрос — в том, когда и что удалять.
PD>Теперь опять не понимаю. Она наплодила не неизвестно сколько строчек, а столько строчек, сколько дней в интервале, в котором она наплодила. Скажем, с 1 марта по 31 марта — 31 строчку.
Что такое "интервал"? Откуда он взялся?
Вот, допустим, мы хотим создать расписание для того, чтобы поздравлять Павла Дворкина с днём рождения. Сколько нужно строчек сгенерировать? Две? Пять? Десять? Тысячу? Когда именно ты планируешь прекратить их праздновать? PD>Если нужно добавить новые , скажем, с 1 апреля по 30 апреля, то добавить новое расписание, которое растеризуется в 30 строк.
Что такое "новое"? У тебя нет никакого нового расписания дня рождений. Это всё то же самое расписание. PD>По-видимому, в тот момент, когда нужно добавить данные на апрель. А кто будет вызывать для исходного расписания и когда ?
Как определить момент, когда "нужно добавить данные на апрель"? Получается, расписание должно быть не пассивной сущностью, которая просто отвечает на вопрос "когда ближайший День Космонавтики", но ещё и чуть ли не активной штукой (потоком), которая раз в X просыпается и добавляет новые данные.
PD>>>Согласен, просто. Вот только это слишком "регулярное событие". Если бы все они были такими или иными, но столь же регулярными, то было бы просто. А если на это "ежедневно в 8.00" наложится еще хотя бы одно такое типа "ежедневно в 18.00" , то все станет менее просто. S>>Нет, не станет. Потому, что у нас появляется Union(Schedule s1, Schedule s2), у которого GetNextOccurence устроен вот так: S>>
S>>Имеем O(1) по памяти, O(1) по времени работы. Вроде ж не rocket science, не?
PD>Верно. Только вот GetNextOccurence будет намного сложнее.
Намного сложнее, чем что? Чем функция CreateXXX()? А почему? PD>И более того, ее придется, возможно, вызывать много раз для одних и тех же данных. А она внутри должна не просто взять минимальный элемент, а по фразе "после дождичка в четверг" найти этот ближайший четверг, в который ожидается дождик, проверить, что после него, а не до, и если не выйдет — брать следующий четверг и для него то же самое. И в следующий раз опять то же. Как тут кешировать — я не очень понимаю.
А зачем и что кэшировать? Давай посмотрим, как будет устроена функция, которая генерирует набор строк для "после дождичка в четверг". И почему в ней генерация второй строки будет драматически дешевле, чем генерация первой.
PD>Будет, будет. С перевычислением их всех на каждом GetNext
Ну так там "перевычисление" стоит O(1). Что всё ещё гораздо лучше, чем O(Log(N)) в "оптимизированном" случае.
PD>Представь себе, что тебе нужно найти некую точку на экране (то есть в дискретном пространстве), через которую проходит некая y=f(x) при x1<x<x2. Ну хотя бы с min(y). Аналитически задача не решается.
Зачем мне представлять себе аллегорию, которая не является удачным аналогом моей задачи? В расписаниях никогда не бывает так, чтобы событие с номером n+1 случилось бы раньше события с номером n.
PD>2. предварительно записать в массив Point все точки (x,y) и искать в нем.
Теперь понятно. Неверное решение следует из неверной аналогии.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
PD>>По-видимому, в тот момент, когда нужно добавить данные на апрель. А кто будет вызывать для исходного расписания и когда ? S>Как определить момент, когда "нужно добавить данные на апрель"? Получается, расписание должно быть не пассивной сущностью, которая просто отвечает на вопрос "когда ближайший День Космонавтики", но ещё и чуть ли не активной штукой (потоком), которая раз в X просыпается и добавляет новые данные.
Ты не ответил на вопрос "кто будет вызывать для исходного расписания и когда". Поскольку ответа нет, домыслю сам.
Если ты хочешь расписание на неопределенный период, то так, конечно, не получится. Вечную иглу Остапа Бендера так не сделать. Вот только боюсь, что он был прав — он не собирался жить вечно.
Напомню, что исходным для меня было расписание авиарейсов. А оно меняется кардинально раз в полгода, по крайней мере в Омском аэропорту. Есть зимнее и есть летнее. Плюс точечные коррекции и того и другого во время сезона.
Кстати, в моем варианте для студентов был и такой способ задания дат предумотрен. Просто фиксированный набор дат, как это с самолетами и бывает нередко. Не по вторникам или ежедневно, а просто "1, 4, 12 и 23 января". Тут растеризация не нужна, данные уже растеризованы, нужно лишь их проверить на дубликаты. И вечное такое расписание сделать никак нельзя.
Расписание, скажем, занятий на курсе тоже меняется раз в полгода. В следующем семестре его делают заново.
Слишком много факторов, которые в итоге не позволяют делать такие вещи на более или менее длительный период. Все равно придется что-то удалять, что-то добавлять, что-то заменять.
А если нужно продлить — просто отредактировать его, изменив срок окончания.
И все это будет делать человек. Больше некому.
Что за ивенты в конце концов , если это не такой уж большой секрет ? Сколько их в день может максимум быть на одного, скажем, юзера ? При миллионе записей в год, я уже писал, будет >500 в день. Увольте меня от таких ивентов, я не i7.
Ну а если тебе и впрямь нужно вечное расписание — поищи иную идею. Создавать таблицы БД с бесконечным числом строк я не предлагаю.
PD>>Верно. Только вот GetNextOccurence будет намного сложнее. S>Намного сложнее, чем что? Чем функция CreateXXX()? А почему?
Чем взятие SELECT TOP или аналогичный поиск по дереву.
Почему — ну напиши ее для варианта (ладно, дождичек оставим в покое и внешнюю зависимость тоже) — "в первый вторник ноября 2035 года в 0.00.". Код будет несложным, по под капотом будет лежать весь Григорианский календарь, да еще и наличие летнего времени, так как 0.00 12 ноября может оказаться и 23.00 11 ноября, а это уже не вторник.
S>Ну так там "перевычисление" стоит O(1). Что всё ещё гораздо лучше, чем O(Log(N)) в "оптимизированном" случае.
Вот только при этом будут опять же задействованы все алгоритмы календаря под капотом, которые, конечно, CO(n), но только С будет не такой уж малой.
PD>>Представь себе, что тебе нужно найти некую точку на экране (то есть в дискретном пространстве), через которую проходит некая y=f(x) при x1<x<x2. Ну хотя бы с min(y). Аналитически задача не решается. S>Зачем мне представлять себе аллегорию, которая не является удачным аналогом моей задачи? В расписаниях никогда не бывает так, чтобы событие с номером n+1 случилось бы раньше события с номером n.
PD>>2. предварительно записать в массив Point все точки (x,y) и искать в нем. S>Теперь понятно. Неверное решение следует из неверной аналогии.
Я не пойму, чего ради ты так агрессивно настроен. Я что, тебя заставляю делать так ? Я высказал свою точку зрения, можешь ее не принимать, бога ради.
Здравствуйте, Marty, Вы писали:
M>Банальное "рабочиеДни" должно зависеть от страны пребывания, если событие ориентировано/связано с этой страной, в общем случае должна быть связь со страной, где событие происходит — например, ты из России, находишься в ОАЭ, но тебе надо каждый первый рабочий день месяца пречислять деньги мобильному оператору в Зимбабве, то рабочие дни надо учитывать по зимбабвийскому трудовому календарю.
Ну так это и решается тем, что "рабочие дни" — это не одно расписание, а по одному на каждую юрисдикцию.
А посольства, соответственно, из "рабочих дней" вычитают гос.праздники обеих юрисдикций.
M>И да, на 30 лет я хз как расчитать, у нас трудовой календарь выпускают только на следующий год незадолго до окончания текущего
Ну, понедельники и пятницы можно рассчитать хоть на 3000 дней. А "рабочие дни" == "понедельники и пятницы" минус "праздники" плюс "переносы рабочих дней".
То есть сама формула остаётся неизменной, а вот её компоненты могут (и должны) меняться с ходом времени. Собсно, реализация "алгебры изменяемых расписаний" это хорошо покрывает, а "генерация списков в табличках СУБД" — плохо.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Ты не ответил на вопрос "кто будет вызывать для исходного расписания и когда".
Потерял часть ответа. Для исходного — известно кто: тот, кто создаёт экземпляр.
Вот мы создаём, к примеру, экземпляр сущности "сберегательный счёт". К нему добавляется атрибут "расписание начисления процентов". Оно для каждого вида счёта — своё: у кого-то — ежемесячно, в дату открытия; у кого-то — ежемесячно в "последний день месяца", у кого-то — ежедневно, у кого-то — "каждый рабочий день".
PD>Если ты хочешь расписание на неопределенный период, то так, конечно, не получится.
Ты ещё скажи, что не получится сделать бесконечную коллекцию случайных чисел
А расписание на определённый период вполне удобно делать как частный случай расписания на неопределённый период.
См. например в clojure функцию range.
PD>Кстати, в моем варианте для студентов был и такой способ задания дат предумотрен. Просто фиксированный набор дат, как это с самолетами и бывает нередко. Не по вторникам или ежедневно, а просто "1, 4, 12 и 23 января".
Это оттого, что в реальности расписания самолётов и существуют только в "растеризованном" виде. Авиакомпания сразу пишет полный список всех вылетов.
То, что они летают типа "каждый вторник и четверг" — это упрощённое представление для пользователей.
PD>Слишком много факторов, которые в итоге не позволяют делать такие вещи на более или менее длительный период. Все равно придется что-то удалять, что-то добавлять, что-то заменять. PD>А если нужно продлить — просто отредактировать его, изменив срок окончания.
Ну как же "просто". Ведь теперь
она внутри должна не просто взять минимальный элемент, а по фразе "после дождичка в четверг" найти этот ближайший четверг, в который ожидается дождик, проверить, что после него, а не до, и если не выйдет — брать следующий четверг и для него то же самое.
Это же вроде как неподъёмная сложность... PD>И все это будет делать человек. Больше некому.
Ну нет, так не пойдёт.
PD>Что за ивенты в конце концов , если это не такой уж большой секрет ?
В том-то и дело, что неизвестно, что за ивенты. Пишу платформу для бизнес-приложений. Расписания в бизнесе встречаются чуть менее, чем везде. Поэтому хочется изобрести достаточно универсальную библиотеку, которая бы приемлемо работала в широком классе случаев.
PD>Сколько их в день может максимум быть на одного, скажем, юзера ?
Да сколько угодно. Потому что расписание может использоваться, скажем, для проверки доступности хоста, и мы хотим его делать ежесекундно. А может — для описания дней рождения клиента, и мы будем ему открытку с уведомлением о скидке отправлять.
PD>Ну а если тебе и впрямь нужно вечное расписание — поищи иную идею. Создавать таблицы БД с бесконечным числом строк я не предлагаю.
Ну, вот я и ищу.
PD>>>Верно. Только вот GetNextOccurence будет намного сложнее. S>>Намного сложнее, чем что? Чем функция CreateXXX()? А почему?
PD>Чем взятие SELECT TOP или аналогичный поиск по дереву.
Не, тут какая-то подмена предмета разговора. У нас всё равно есть функция порождения этого расписания. Этот код сам себя не напишет. Функция, которая делает GetNext для произвольной комбинации расписаний, устроена очень просто — я показал основы. А для собственно специфического расписания я не вижу никакой причины, которая бы сделала GetNextOccurence сложнее, чем Create.
Это примерно то же самое, что превратить энергичный генератор коллекций в ленивый итератор:
public IEnumerable<int> GetAllRandoms(int seed, int n)
{
var l = new List<int>();
var r = new Random(seed);
while(--n>0)
l.Add(r.Next());
return l;
}
public IEnumerable<int> GetAllRandoms(int seed) // n не нужен
{
var r = new Random(seed);
while(true)
yield return r.Next();
}
PD>Почему — ну напиши ее для варианта (ладно, дождичек оставим в покое и внешнюю зависимость тоже) — "в первый вторник ноября 2035 года в 0.00.". Код будет несложным, по под капотом будет лежать весь Григорианский календарь, да еще и наличие летнего времени, так как 0.00 12 ноября может оказаться и 23.00 11 ноября, а это уже не вторник. S>>Ну так там "перевычисление" стоит O(1). Что всё ещё гораздо лучше, чем O(Log(N)) в "оптимизированном" случае.
PD>Вот только при этом будут опять же задействованы все алгоритмы календаря под капотом, которые, конечно, CO(n), но только С будет не такой уж малой.
Ну так у тебя точно так же, не получится обойтись безо всех вариантов календаря, только они у тебя перенесены на этап генерации расписания. Будет ли поиск в БД быстрее, чем арифметические операции — вопрос спорный.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Ладно, пора заканчивать. Точки зрения выяснены, по второму круг идти незачем.
Только маленький комментарий
>Это оттого, что в реальности расписания самолётов и существуют только в "растеризованном" виде. Авиакомпания сразу пишет полный список всех вылетов.
То, что они летают типа "каждый вторник и четверг" — это упрощённое представление для пользователей.
Вот в этом сомневаюсь. По описанию типа "каждый вторник и четверг" сформировать все даты — очень просто.
По набору дат сформировать определение типа "каждый вторник и четверг" — в общем случае невозможно.
Январь 2024. Вылеты 1,3, 5, 8, 12, 19 и 24.
Попробуй дать определение типа "каждый вторник и четверг". Не дашь. Так по датам его и дают в расписании.
PD>>Вот только при этом будут опять же задействованы все алгоритмы календаря под капотом, которые, конечно, CO(n), но только С будет не такой уж малой. S>Ну так у тебя точно так же, не получится обойтись безо всех вариантов календаря, только они у тебя перенесены на этап генерации расписания. Будет ли поиск в БД быстрее, чем арифметические операции — вопрос спорный.
Все верно. Суть -то простая : я предлагаю это делать на вводе данных, а getNext брать по этим данным. А ты предлагаешь в getNext это делать.
На вводе данных — делается 1 раз, и время тут не лимитировано, но требуется большая память и не получится на неопределенный период
В getNext — требуется небольшая память и можно на неопределенный период, но вычислять будешь столько раз, сколько раз она будет вызываться. Может быть, много раз с одними и теми же данными.
Здравствуйте, Pavel Dvorkin, Вы писали:
>>Это оттого, что в реальности расписания самолётов и существуют только в "растеризованном" виде. Авиакомпания сразу пишет полный список всех вылетов. PD>То, что они летают типа "каждый вторник и четверг" — это упрощённое представление для пользователей.
PD>Вот в этом сомневаюсь. По описанию типа "каждый вторник и четверг" сформировать все даты — очень просто. PD>По набору дат сформировать определение типа "каждый вторник и четверг" — в общем случае невозможно.
Ну так это делают люди, а не программы по предопределённому алгоритму.
PD>Январь 2024. Вылеты 1,3, 5, 8, 12, 19 и 24.
PD>Попробуй дать определение типа "каждый вторник и четверг". Не дашь.
Запросто. "C 1 по 24 января летаем трижды в неделю: понедельник, среда, пятница. Вылетов 10го, 15го, и 22го нет".
В реале оно именно так. Просто у регулярных рейсов стараются делать расписания попроще (и то периодически рейсы отменяют). А у чартеров "дырки" в расписаниях — сплошь и рядом.
PD>Все верно. Суть -то простая : я предлагаю это делать на вводе данных, а getNext брать по этим данным. А ты предлагаешь в getNext это делать.
Да, верно. Я понял, в чём беда — я неверно сформулировал вопрос в начале топика. Я имел в виду, что функция getNext не должна иметь шибко плохую асимптотику — например, получение Nго события не должно быть O(N). Иначе можно было бы взять твою идею с порождением всех дат подряд, и наложить на неё фильтр в виде currentCandidate >= start.
А получилось, что попросил я оптимизировать именно getNext любой ценой — в том числе и переносом затрат в create().
PD>В getNext — требуется небольшая память и можно на неопределенный период, но вычислять будешь столько раз, сколько раз она будет вызываться. Может быть, много раз с одними и теми же данными.
Ну вот да. В моей ментальной модели getNext вызывается много-много-много раз, даже для одного и того же start.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
PD>>По набору дат сформировать определение типа "каждый вторник и четверг" — в общем случае невозможно. S>Ну так это делают люди, а не программы по предопределённому алгоритму.
PD>>Январь 2024. Вылеты 1,3, 5, 8, 12, 19 и 24.
PD>>Попробуй дать определение типа "каждый вторник и четверг". Не дашь. S>Запросто. "C 1 по 24 января летаем трижды в неделю: понедельник, среда, пятница. Вылетов 10го, 15го, и 22го нет".
Сумел . Ну а если так
1,3, 5, 8, 12, 16, 21 и 25.
S>В реале оно именно так. Просто у регулярных рейсов стараются делать расписания попроще (и то периодически рейсы отменяют). А у чартеров "дырки" в расписаниях — сплошь и рядом.
У них не дырки, а порой просто фиксированные дни. Единственное правило, которое можно вывести — если туристов забросили на N дней, то через N будет новый рейс, вывезет их обратно и скорее всего забросит новую партию. Но N сплошь и рядом меняется на 1-2 дня : сегодня на 12, через 12 дней на 10, потом через 10 на 11 и т.д. Почему так — черт знает.
PD>>Все верно. Суть -то простая : я предлагаю это делать на вводе данных, а getNext брать по этим данным. А ты предлагаешь в getNext это делать. S>Да, верно. Я понял, в чём беда — я неверно сформулировал вопрос в начале топика. Я имел в виду, что функция getNext не должна иметь шибко плохую асимптотику — например, получение Nго события не должно быть O(N). Иначе можно было бы взять твою идею с порождением всех дат подряд, и наложить на неё фильтр в виде currentCandidate >= start.
Я не думаю, что у нее будет асимптотика O(N), но и при хорошей асимптотике если коэффициент при O(1) большой, хорошего будет мало. А тут довольно тяжелый алгоритм работы с DateTime и его методами. Тяжелый не в смысле асимптотики, а просто в пусть в фиксированном, но довольно большом количестве действий.
S>А получилось, что попросил я оптимизировать именно getNext любой ценой — в том числе и переносом затрат в create().
PD>>В getNext — требуется небольшая память и можно на неопределенный период, но вычислять будешь столько раз, сколько раз она будет вызываться. Может быть, много раз с одними и теми же данными. S>Ну вот да. В моей ментальной модели getNext вызывается много-много-много раз, даже для одного и того же start.
В общем, при столь неопределенных требованиях к быстродействию и памяти трудно сказать, что будет лучше. Возможно, ты напишешь свой алгоритм, а он не даст нужной производительности. DateTime же не оптимизируешь.
Я бы вот что сделал. Простенький тест по одному условию вроде "каждый нечетный". И getNext с произвольной start. И в цикл все это.
Сколько getNext в секунду получится ? Устроит такое быстродействие ?
Здравствуйте, _FRED_, Вы писали:
_FR>Привет, встречный вопрос такой: а что потом с этим результатом делать?
Очень хороший вопрос, спасибо.
Я пока себе это представляю так:
1. Вычисления вроде "сколько событий произойдет в интервале от T1 до T2". Например, в Excel есть такая функция WORKDAY. Будет нужен её аналог.
2. Шедулинг событий (показать нотификацию в UI, отправить письмо, начислить деньги, инициировать онлайн-сессию и т.п.). Тут важна однократность срабатывания — для чего надо как-то идентифицировать экземпляры событий, а также персистентно хранить факт срабатывания.
_FR>Про то, что время должен расчитывать "сервер" уже упомянули и я с этим тоже согласен, но есть куча ньюансов: там может, например, случиться переход с "зимнего" времени на "летнее" и заранее узнать (правильно понять), когда же "оно наступит" клиенту не просто (будет ли достаточно выдать точный, но не понятный ответ?). Какой результат ожидается: _FR>
_FR>Такого-то числа в такое-то время по клиентскому времени ("TimeZone zone") _FR>Такого-то числа в такое-то время по серверному времени? Не ясно, как это внятно описать клиенту (время которого может меняться как угодно). _FR>Через столько-то часов/минут/секунд он данного момента? А если интервал месяцы, будет ли такой ответ иметь смысл? _FR>
Пока идея такая, что нам надо превращать "расписание", которое может быть сформулировано в терминах различных часовых поясов, в конкретные "абсолютные" моменты в UTC. Перевод в "клиентское" или "серверное" время — это уже вопрос в некотором смысле локальный.
Характерный пример — еженедельная встреча, назначенная в часовом поясе Нью-йорка, шедулится в соответствии с daylight saving policy США. При этом с точки зрения пользователя, эта встреча будет происходить по его локальному (скажем, Московскому) времени — просто полгода она будет в 20:00, а полгода — в 21:00.
_FR>То есть, для точного ответа на "GetNextOccurence" кажется нужно ещё и понимать, что с этим самым "NextOccurence" будут делать, что от него тожидают, как его будут интерпретировать и как обрабатывать.
Это верно. _FR>Мой опыт работы (основанный на опыте старших коллег) с расписаниями говорит о том, что самое эффективное: _FR>
_FR>Задать некоторую точность срабатывания _FR>Периодически, в зависимости от указанной выше точности (делённой на два или даже на e или π для пущей точности), на "серверной" стороне проверять: не пора ли? _FR>Далее уже дело техники (контракта) обеспечить, чтобы событие не сработало повторно (при переводе часов или смене часового пояса). Тут можно, например, запоминать дату последнего срабатывания и считать, что если в расписании стоит "каждая пятница в 08:00", то отработанное час назад событие можно пропустить (потому что "пятница", как и "08:00" два раза в день не случается). _FR>
Интуитивно кажется, что этот алгоритм должен работать как-то так:
1. Читаем из persistent storage информацию о последних обработанных событиях
2. Находим список событий, которые "прошли" с момента последнего обработанного до момента T (в простом случае T = now()), вызываем их срабатывание по очереди
3. Сохраняем в persistent storage информацию о сработавших событиях.
То есть если нас "разбудили" через месяц после последнего срабатывания, то мы должны запустить все "будильники", которые были пропущены за этот месяц.
_FR>Последний пункт сильно зависит от того, что ожидается от срабатывания и на сколько клиент ожидает/понимает (при составлении расписания) особенностей изменения линейного течения времени.
Ну, и от семантики события тоже зависит. Некоторые события, наверное, должны "склеиваться". Ну, вот как винда клеит все WM_PAINT так, чтобы в очереди всегда было не больше одного такого события.
Если мы, к примеру, решили мониторить репозиторий git, делая pull раз в минуту, то нет никакого смысла делать 60 pull в том случае, если наш процесс "проспал" целый час.
А если мы, к примеру, собирались начислять 0.1% в день на депозит, то надо выполнить все начисления. (Иногда можно свести этот случай к предыдущему, сразу начислив (0.1)N процента на остаток, но из-за тонкостей округления это может оказаться не всегда применимым)
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Всем привет. S>Ищу наиболее удобную, полноценную и эффективную реализацию описания расписаний. S>Язык можно более-менее любой — всё равно будем переписывать на целевой язык. S>Под расписанием понимается то же, что обычно — регулярное событие, со всякими плюшками: "третий четверг апреля", "первый рабочий день каждого месяца", "последняя пятница августа", "каждый вторник", "каждый 256й день года", и так далее.
S>Эффективно нужно уметь выполнять одну операцию: GetNextOccurence(TimeStamp start, TimeZone zone) — найти следующее срабатывание после заданного момента времени.
S>В общем, кто имел дело с библиотеками кода для подобной задачи — накидайте ссылок на то, что вам понравилось.
В принципе что есть расписание в общем виде? Это предикат, который получает дату и возвращает true если дата "попадает" в расписание. Используя логические операции из одних предикатов можно собирать другие. В общем имеем дело с простым формальным языком. Вот это нужно и реализовать. Тогда можно будет сделать любое расписание.
