Описание расписаний - Философия программирования

Здравствуйте, 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. Или дерева. В списке линейный поиск будет медленным.

Но это делать надо, а БД сама сделает.

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

S> б) расход места. Банальное "рабочиеДни" превратится в ~1000 строк, даже если ограничиться 30 годами в будущее.
По-моему персиситить такие данные неверно. Оно же меняется постоянно. Скажем, емнип, в последние несколько лет таймзоны в России, переходы на летнее-зимнее время менялись раз пять. Или внезапно организованные выходные дни (королева умерла — побыстрому организовали государственный выходной). Так что тут не только функцию расчёта надо сочинить, но и правильную инфраструктуру, которая следит за изменениями в календарях и таймзонах.

avalon/3.0.0

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

S>В общем, кто имел дело с библиотеками кода для подобной задачи — накидайте ссылок на то, что вам понравилось.

Opening Hours из OpenStreetMap https://wiki.openstreetmap.org/wiki/Key:opening_hours

Умеет даже такие штуки как
"каждый второй четверг месяца санитарный день", "по субботам с 9pm до последнего клиента", "от заката до рассвета", "в зимнее время года в будни по предварительной записи если не государственный праздник". Есть формальная грамматика, есть библиотеки примерно для всего, есть онлайн редактор/валидатор.

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

S>В общем, кто имел дело с библиотеками кода для подобной задачи — накидайте ссылок на то, что вам понравилось.

Функционала CRON будет достаточно? Если да, то можно посмотреть на существующие движки.

edit: кстати, насколько я знаю, никто там с оптимизацией не заморачивается, текущая дата-время просто сверяется с паттернами каждую секунду. Это дешевая операция, тем более на нескольких десятках правил.

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

PD>Ну тогда для одного клиента WHERE ... AND id =
Для каждого экземпляра расписаний.
PD>А для объединений и перечеений — ИМХО проще брать в Set, а потом его средствами. Хотя, наверное, можно и на SQL.
Это очень дорогая алгебра выходит. На каждую операцию строить множество, а потом снова его сортировать.
PD>Ну если выбор из памяти по произвольному условию по DateTime не проблема — можно и в ОП. Но тогда придется хранить в ОП отсортированно по DateTime, а дальше бинарный поиск.
У меня нет задачи по произвольному условию. Есть задача находить ближайшее после указанного timestamp.

PD>Просто их все удалить и новые добавить.
Непонятно, в какой момент добавлять новые.

PD>В варианте БД — ну и что ? 1000 строк в таблице — это много ?
Нет, не много. А вот, скажем, миллион расписаний (а это — ничего особенного. Просто даты начисления процентов для всего-то миллиона накопительных счетов) потребует уже миллиарда строк.
PD>Если в ОП, то скорее массива с бинарным поиском и индексом в виде DateTime. Или дерева. В списке линейный поиск будет медленным.
Ну вот я бы всё же хотел получить реализацию с O(1) памяти, а не O(∞).

PD>Но это делать надо, а БД сама сделает.
Не во все задачи можно втащить БД.

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

Сорри, по класса 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

https://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html#TreeSet-java.util.Comparator-
https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html

А потом для объединения / пересечения сетов addAll/retainAll

Впрочем, едва ли это понадобится. getNext вернет же не Set, а один элемент. Пересечение их всегда даст либо 0, либо 1 элемент. Объединение — от 1 до миллиона, верно, но тебе точно нужно объединить полученные от getNext DateTime для миллиона расписаний ?

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

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

S>В общем, кто имел дело с библиотеками кода для подобной задачи — накидайте ссылок на то, что вам понравилось.

`GetNextOccurence()` выглядит как задача срабатывания следующего таймера. Может быть стоит посмотреть в сторону Timing Wheels: https://paulcavallaro.com/blog/hashed-and-hierarchical-timing-wheels/

Здравствуйте, 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 устроен вот так:

TimeStamp GetNextOccurence(TimeStamp start, TimeZone zone) 
{
  return Min(s1.GetNextOccurence(start, zone), s2.GetNextOccurence(start, zone));
}

Имеем 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	https://github.com/evilguest/
Дата:	16.01.24 08:46
Оценка:

	От:	Alekzander
	Дата:	16.01.24 09:22
	Оценка:

От:	Sinclair	https://github.com/evilguest/
Дата:	16.01.24 10:07
Оценка:

	От:	Qulac
	Дата:	16.01.24 10:30
	Оценка:

От:	Sinclair	https://github.com/evilguest/
Дата:	16.01.24 11:05
Оценка:

От:	gandjustas	http://blog.gandjustas.ru/
Дата:	16.01.24 13:38
Оценка:	120 (1)

	От:	Miroff
	Дата:	16.01.24 13:44
	Оценка:	159 (4)