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