Здравствуйте, 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>TimeStamp GetNextOccurence(TimeStamp start, TimeZone zone) 
S>{
S>  return Min(s1.GetNextOccurence(start, zone), s2.GetNextOccurence(start, zone));
S>}
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 раз, а потом сколько раз не делай поиск, вычислять функцию не надо

Так что выбирай.

Здравствуйте, Alekzander, Вы писали:


A>А если человек путешествует через таймзоны вслед за солнцем с устройством, адаптирующимся под таймзоны по сети? У него НГ будет в расписании столько раз, сколько он зон пересёк?
Конечно. Вы так говорите, как будто ни разу в новый год не летали
A> Может я, конечно, что-то не понимаю, но передача таймзоны параметром выглядит для меня как алярм.
A>Конкретно, мне интересно, что будет, если мы используем такую функцию в банк-клиенте для запланированных платежей, если событие случится перед вылетом и после.
Ну, в таком случае разработчика нужно будет пожурить на пост-мортеме.
Потому что
а) запланированные платежи должен делать банк-сервер, а не банк-клиент. Банк-клиент — штука ненадёжна. А если у него батарейка села? Или интернета нет? Пока я в самолёте летел, значит, мало того, что часовой пояс сменился, так и запланированный платёж за билайн не прошёл, и я теперь остался без связи (а, заодно, и без возможности воспользоваться банк-клиентом для ручного проведения платежа)
б) планирование платежей в часовом поясе устройства — не очень годная идея. Там будет часовой пояс банка.

Здравствуйте, Sinclair, Вы писали:

S>б) расход места. Банальное "рабочиеДни" превратится в ~1000 строк, даже если ограничиться 30 годами в будущее.

Банальное "рабочиеДни" должно зависеть от страны пребывания, если событие ориентировано/связано с этой страной, в общем случае должна быть связь со страной, где событие происходит — например, ты из России, находишься в ОАЭ, но тебе надо каждый первый рабочий день месяца пречислять деньги мобильному оператору в Зимбабве, то рабочие дни надо учитывать по зимбабвийскому трудовому календарю.

И да, на 30 лет я хз как расчитать, у нас трудовой календарь выпускают только на следующий год незадолго до окончания текущего

Здравствуйте, Pavel Dvorkin, Вы писали:


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>>TimeStamp GetNextOccurence(TimeStamp start, TimeZone zone) 
S>>{
S>>  return Min(s1.GetNextOccurence(start, zone), s2.GetNextOccurence(start, zone));
S>>}
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) и искать в нем.
Теперь понятно. Неверное решение следует из неверной аналогии.

Здравствуйте, Sinclair, Вы писали:

A>>А если человек путешествует через таймзоны вслед за солнцем с устройством, адаптирующимся под таймзоны по сети? У него НГ будет в расписании столько раз, сколько он зон пересёк?
S>Конечно. Вы так говорите, как будто ни разу в новый год не летали
A>> Может я, конечно, что-то не понимаю, но передача таймзоны параметром выглядит для меня как алярм.
A>>Конкретно, мне интересно, что будет, если мы используем такую функцию в банк-клиенте для запланированных платежей, если событие случится перед вылетом и после.
S>Ну, в таком случае разработчика нужно будет пожурить на пост-мортеме.
S>Потому что
S>а) запланированные платежи должен делать банк-сервер, а не банк-клиент. Банк-клиент — штука ненадёжна. А если у него батарейка села? Или интернета нет? Пока я в самолёте летел, значит, мало того, что часовой пояс сменился, так и запланированный платёж за билайн не прошёл, и я теперь остался без связи (а, заодно, и без возможности воспользоваться банк-клиентом для ручного проведения платежа)
S>б) планирование платежей в часовом поясе устройства — не очень годная идея. Там будет часовой пояс банка.

Ну а если банк-сервер переедет в другой часовой пояс? (Не физически, понятно, а федеральным законом). Аккурат с той даты, когда платёж.

А если на клиенте я запланировал дорогую операцию не финансового, а технологического характера, и в результате попал на расходы?

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

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

Ещё, как вариант, таймзону сделать advanced-параметром при создании ивента, и пусть ответственность будет на юзере. Или совместить этот вариант с предыдущим, сделав по дефолту значение таймзоны "current", но давая выбрать самому.

Здравствуйте, Sinclair, Вы писали:


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), но только С будет не такой уж малой.
Ну так у тебя точно так же, не получится обойтись безо всех вариантов календаря, только они у тебя перенесены на этап генерации расписания. Будет ли поиск в БД быстрее, чем арифметические операции — вопрос спорный.

Здравствуйте, Sinclair, Вы писали:

Ладно, пора заканчивать. Точки зрения выяснены, по второму круг идти незачем.

Только маленький комментарий

>Это оттого, что в реальности расписания самолётов и существуют только в "растеризованном" виде. Авиакомпания сразу пишет полный список всех вылетов.
То, что они летают типа "каждый вторник и четверг" — это упрощённое представление для пользователей.

Вот в этом сомневаюсь. По описанию типа "каждый вторник и четверг" сформировать все даты — очень просто.
По набору дат сформировать определение типа "каждый вторник и четверг" — в общем случае невозможно.

Январь 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 в секунду получится ? Устроит такое быстродействие ?

Здравствуйте, 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 при работе чтении файлов. Если делается запрос, то она читает нужное и еще несколько кластеров в кеш, так что следующие запросы будут реализованы из кеша. Ну а если возникнет кеш-промах, то читает из файла и опять несколько кластеров.
Все отличие от твоей задачи, что у тебя вместо чтения — вычисление по формуле, а кеш реализован как таблица растра.

Здравствуйте, Sinclair, Вы писали:

S>Всем привет.

В любом непонятном случае -- нормальная форма БД и SQL.

Здравствуйте, Sinclair, Вы писали:

S>Ищу наиболее удобную, полноценную и эффективную реализацию описания расписаний…
S>Под расписанием понимается то же, что обычно — регулярное событие, со всякими плюшками: "третий четверг апреля", "первый рабочий день каждого месяца", "последняя пятница августа", "каждый вторник", "каждый 256й день года", и так далее.
S>Эффективно нужно уметь выполнять одну операцию: GetNextOccurence(TimeStamp start, TimeZone zone) — найти следующее срабатывание после заданного момента времени.

Привет, встречный вопрос такой: а что потом с этим результатом делать?
Про то, что время должен расчитывать "сервер" уже упомянули и я с этим тоже согласен, но есть куча ньюансов: там может, например, случиться переход с "зимнего" времени на "летнее" и заранее узнать (правильно понять), когда же "оно наступит" клиенту не просто (будет ли достаточно выдать точный, но не понятный ответ?). Какой результат ожидается:

• Такого-то числа в такое-то время по клиентскому времени ("TimeZone zone")
  
• Такого-то числа в такое-то время по серверному времени? Не ясно, как это внятно описать клиенту (время которого может меняться как угодно).
  
• Через столько-то часов/минут/секунд он данного момента? А если интервал месяцы, будет ли такой ответ иметь смысл?

То есть, для точного ответа на "GetNextOccurence" кажется нужно ещё и понимать, что с этим самым "NextOccurence" будут делать, что от него тожидают, как его будут интерпретировать и как обрабатывать.

Мой опыт работы (основанный на опыте старших коллег) с расписаниями говорит о том, что самое эффективное:

• Задать некоторую точность срабатывания
  
• Периодически, в зависимости от указанной выше точности (делённой на два или даже на e или π для пущей точности), на "серверной" стороне проверять: не пора ли?
  
• Далее уже дело техники (контракта) обеспечить, чтобы событие не сработало повторно (при переводе часов или смене часового пояса). Тут можно, например, запоминать дату последнего срабатывания и считать, что если в расписании стоит "каждая пятница в 08:00", то отработанное час назад событие можно пропустить (потому что "пятница", как и "08:00" два раза в день не случается).

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

Здравствуйте, _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 процента на остаток, но из-за тонкостей округления это может оказаться не всегда применимым)