Сообщение Re[7]: Описание расписаний от 17.01.2024 5:39
Изменено 17.01.2024 6:02 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>
Согласен, просто. Вот только это слишком "регулярное событие". Если бы все они были такими или иными, но столь же регулярными, то было бы просто. А если на это "ежедневно в 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#
Да и множества , возможно, тоже не нужны. Тебе же один элемент нужен , хватит и первый элемент брать.
В общем, резюме ИМХО простое.
Либо то, что я предлагаю, либо хранить список элементов в исходном виде, искать "интеллектуально" минимальный по каждому элементу и минимум этих минимумов. Тоже решение, может быть, и неплохое. Медленнее, конечно, но тут уж надо мерять.
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) будет миллион строк, а не миллиард.
Строк будет больше, верно. Но тут решать надо, можно такое себе позволить или нет.
Вообще-то миллион на одного человека за 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>
Согласен, просто. Вот только это слишком "регулярное событие". Если бы все они были такими или иными, но столь же регулярными, то было бы просто. А если на это "ежедневно в 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#
Да и множества , возможно, тоже не нужны. Тебе же один элемент нужен , хватит и первый элемент брать.
В общем, резюме ИМХО простое.
Либо то, что я предлагаю, либо хранить список элементов в исходном виде, искать "интеллектуально" минимальный по каждому элементу и минимум этих минимумов. Тоже решение, может быть, и неплохое. Медленнее, конечно, но тут уж надо мерять.
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#
Да и множества , возможно, тоже не нужны. Тебе же один элемент нужен , хватит и первый элемент брать.
В общем, резюме ИМХО простое.
Либо то, что я предлагаю, либо хранить список элементов в исходном виде, искать "интеллектуально" минимальный по каждому элементу и минимум этих минимумов. Тоже решение, может быть, и неплохое. Медленнее, конечно, но тут уж надо мерять.