Информация об изменениях

Сообщение Re[7]: Описание расписаний от 17.01.2024 5:39

Изменено 17.01.2024 5:50 Pavel Dvorkin

Re[7]: Описание расписаний
Здравствуйте, 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) будет миллион строк, а не миллиард.

А тут пока что нет O(1). Дерево же.

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#
Да и множества , возможно, тоже не нужны. Тебе же один элемент нужен , хватит и первый элемент брать.
Re[7]: Описание расписаний
Здравствуйте, 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) будет миллион строк, а не миллиард.

А тут пока что нет O(1). Дерево же.

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#
Да и множества , возможно, тоже не нужны. Тебе же один элемент нужен , хватит и первый элемент брать.


В общем, резюме ИМХО простое.

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