Имеется задача написать класс для учета кол-ва добавления и потребления какого-либо продукта в течении времени. Для примера можно взять муку на складе. Сначала мы ее два дня завозим туда, потом неделю потребляем. И делаем это одновременно.
Основные необходимые методы:
void Add(DateTime start, DateTime end, double quantity) // quantity может быть как положительным, так и отрицательным.
double GetQuantity(DateTime time); // возвращает кол-во сырья в любой момент времени
var store = new Store();
// для упрощения примера я заменил DateTime на integer
// |----|----|----|----|----|----|----|----|----|----|----|
// 0 1 2 3 4 5 6 7 8 9 10 11
//
// Add:
//1 |---------| -10
//2 |------------------------| 10
//3|-------------------------------------------------| 10
store.Add(4, 6, -10); // 1. с 4го по 6й день, расходуем 10 единиц
store.Add(2, 7, 10); // 2. со 2го по 7й день добавляем 10 единиц
store.Add(0, 10, 10); // 3. с 0го по 10й день добавляем 10 единиц
Получаем такой результат:
//
// Объяснение (цифрами указано кол-во продукта, которое добавляется за период времени):
// -10
//1 |---------|
// 4 4 2
//2 |---------|---------|----|
// 2 2 2 1 3
//3|---------|---------|---------|----|--------------|
//
// Result
// 0 2 8 4 7 10
// |---------|---------|---------|----|--------------|
//
// |----|----|----|----|----|----|----|----|----|----|----|
// 0 1 2 3 4 5 6 7 8 9 10 11
Assert.AreEqual(0.0, store.GetValue(0));
Assert.AreEqual(1.0, store.GetValue(1));
Assert.AreEqual(2.0, store.GetValue(2));
Assert.AreEqual(8.0, store.GetValue(4));
Assert.AreEqual(4.0, store.GetValue(6));
Assert.AreEqual(7.0, store.GetValue(7));
Assert.AreEqual(10.0, store.GetValue(10));
Assert.AreEqual(10.0, store.GetValue(20)); // все так же 10 единиц
Т.е. по сути, нам всего лишь нужно сложить все эти прямые, идущие под разным углом. Просто groupBy. Все было бы просто, если бы данные были статические. С динамической структурой (т.е. с возможностью добавлять и удалять новые элементы) все гораздо сложнее.
Мои мысли:
Я предполагаю, что можно хранить результирующий график (то, что на картинке помечено как result) как дерево отрезков. Каждый отрезок будет иметь начало, конец и список прямых, которые на него влияют. В таком случае при добавлении нового элемента, который пересекает другие отрезки нам прийдется:
1. Разделить уже существующий отрезок результирующего графика, который пересекается с началом на два отрезка.
2. Разделить уже существующий отрезок результирующего графика, который пересекается с концом на два отрезка.
3. Обновить кол-во во всех отрезках результирующиего графика, начиная с начала интервала, который вставляем и до конца дерева.
Если мы будет хранить отрезки в дереве, то единственная возможность сделать разделить отрезок на 2 (split) — это удалить из дерева старый отрезок и добавить два новых.
В итоге получаем ужасающую производительность: добавление сырья в середину требует
а. 2 удаления и 4 вставки в дерево отрезков (пункты 1 и 2)
б. Обновления всех последущих интервалов в дерево (пункт 3)
Хотелось бы услышать идеи о том, в каком направлении двигаться, чтобы эту задачу решить. Ссылки на статьи книги или исходники очень приветствуются.
NH>Т.е. по сути, нам всего лишь нужно сложить все эти прямые, идущие под разным углом.
Ну раз у тебя количество продукта является непрерывной кусочно-линейной функцией, то построй структуру данных, которая по точке вернёт тебе линейную функцию, реализованную в данной точке. Потом подставляешь в полученную функцию время и тут же получаешь ответ.
Я бы заменил каждую твою сглаженную ступеньку на сумму двух таких функций:
Тогда для решения достаточно будет обычного дерева поиска, где ключами выступают параметры t, а в вершинах хранится сумма функций с данным параметром t.
Добавление нового интервала будет сводится к паре вставок в дерево (либо к обновлению данных в вершине, если такой ключ уже есть).
А запрос на получение функции по ключу z будет требовать суммирование всех значений из дерева с ключами t ≤ z (ибо по построению вклад всех функций с ключами t > z будет нулевым). Ну а запрос суммы на полуинтервале (∞, z] — это классическая задача на хранение дополнительной информации в дереве (см. аugmented trees).
Итого, по сложности получается, что добавление или удаление интервала потребует двух логарифмических вставок или удалений соответственно. А получение значения — одного логарифмического же поиска.
Здравствуйте, NoHate, Вы писали:
NH>Имеется задача написать класс для учета кол-ва добавления и потребления какого-либо продукта в течении времени. Для примера можно взять муку на складе. Сначала мы ее два дня завозим туда, потом неделю потребляем. И делаем это одновременно.
Хотелось бы знать требования к этой базе данных.
Какова глубина истории назад-вперёд. Можно ли редактировать прошлое. Ожидаемое количество нахлёстов. Размеры отрезков времени. Точность запросов по времени (до дня, до секунды). И т.п.
Какие требования к скорости доступа на чтение и на запись.
Возможное практическое решение может быть таким: вести журнал ежедневных остатков.
Тут будет проблема в накоплении вычислительной ошибки, конечно.
Другой вариант: журнал стоп-кадров (остаток, градиент) с точками — датами начала-конца операций. Количество записей будет меньше, доступ на изменение быстрее, доступ на чтение медленнее.
При ежедневных правках выродится в журнал ежедневных остатков.
Третий вариант: ежемесячный журнал остатков, плюс ежемесячные коллекции ломаных линий. Естественно, что ломаные, пересекающие начало месяца, приводятся к суперпозиции: градиент на начало месяца.
Доступ на чтение — суперпозиция (т.е. суммирование) всех ломаных от начала месяца.
Для удобства, как заметил watchmaker, можно наклонную ступеньку _/- представить в виде суперпозиции двух передних фронтов с положительным и отрицательным градиентом _/ и -\
Тогда двоичным поиском отфильтровываем и суммируем лишь те ломаные, у которых излом находится между началом месяца и датой запроса.
Здравствуйте, watchmaker, Вы писали:
W>Я бы заменил каждую твою сглаженную ступеньку на сумму двух таких функций:
Общую идея я понял, но вот детали реализации до меня не дошли. t — это точка начала интервала сглаженной функции, так? А что означает коэффициент k в функции? Почему первая функция = 0?
W>Добавление нового интервала будет сводится к паре вставок в дерево (либо к обновлению данных в вершине, если такой ключ уже есть).
Почему к паре? Какие будут вставки?
W>А запрос на получение функции по ключу z будет требовать суммирование всех значений из дерева с ключами t ≤ z (ибо по построению вклад всех функций с ключами t > z будет нулевым). Ну а запрос суммы на полуинтервале (∞, z] — это классическая задача на хранение дополнительной информации в дереве (см. аugmented trees).
Это хорошая идея, так и сделаю, спасибо.
Здравствуйте, Кодт, Вы писали:
К>Хотелось бы знать требования к этой базе данных.
Это скорее не база данных, а структура данных в памяти, которая служит для того, чтобы мы могли быстро узнать, в какой момент времени мы можем взять со склада Х единиц продукта.
К>Какова глубина истории назад-вперёд. Можно ли редактировать прошлое. Ожидаемое количество нахлёстов. Размеры отрезков времени. Точность запросов по времени (до дня, до секунды). И т.п. К>Какие требования к скорости доступа на чтение и на запись.
Прошлого как такого нет, это просто временная шкала. Все, что мы рассчитываем — в будущем. Поэтому вставки в начало ожидаемы.
Размер отрезка времени и точность не очень важны, потому что время — это всего лишь long.
Ожидаемое кол-во нахлестов около 5.
По поводу требований — требуется частый поиск и реже — вставка. Кол-во интервалов от 500 до 10000.
К>Возможное практическое решение может быть таким: вести журнал ежедневных остатков.
Наверное тут будет проблема, если нам понадобится отредактировать записи, которые в начале. Потому что тогда нужно будет обновить все последующие остатки.
К>Для удобства, как заметил watchmaker, можно наклонную ступеньку _/- представить в виде суперпозиции двух передних фронтов с положительным и отрицательным градиентом _/ и -\
Вот именно этот момент я не понял. Есть ли какая-то статья на wiki или более подробное описание?
Здравствуйте, wildwind, Вы писали:
W>Простое решение: поквантовать шкалу времени с нужной точностью. Хранить и считать все дискретно.
А что делать при вставке в начало? Пересчитывать все?
W>P.S. Любопытно, а какой практический смысл такой задачи? Или реальная задача другая?
Да нет, задача самая реальная. Есть склад готовой продукции. Несколько раз в день мы его пополняем (увеличиваем кол-во). Несколько раз в день у нас с него забирают товар (уменьшаем кол-во). Размер склада ограничен. Нам нужно уметь ответить на вопросы:
— можно ли в день X1 взять со склада кол-во Y1? Если нельзя в X1, то когда можно?
— можно ли в день X2 добавить на склад Y2 продукции (т.е. влезет ли)?
NH>Общую идея я понял, но вот детали реализации до меня не дошли. t — это точка начала интервала сглаженной функции, так? А что означает коэффициент k в функции? Почему первая функция = 0?
Если ты добавил quantity единиц за интервал [start, end]. То эффективное количество от этого действия описывается функцией
Но суммировать такие функции неудобно — ведь если было бы удобно, то сам бы и сделал безо всякого форума
А вот с функциями Uk,t работать проще. Ну и любая ненулевая ступенька раскладывается единственным образом в сумму двух U с разными параметрами.
NH> Почему первая функция = 0?
Нет таких нулевых функций нигде (ну пока quantity ≠ 0, но это совсем уж неинтересный случай).
Uk,t(x) — это вся функция целиком. Да, на полубесконечности она нулевая. Почему? Так удобнее. Не нравится? Ну можешь тогда разложить свою ступеньку в сумму других функций
W>>Добавление нового интервала будет сводится к паре вставок в дерево (либо к обновлению данных в вершине, если такой ключ уже есть). NH>Почему к паре?
А куда больше? NH>Какие будут вставки?
Одна вставка для времени start, другая — для end.
Здравствуйте, NoHate, Вы писали:
NH> W>Простое решение: поквантовать шкалу времени с нужной точностью. Хранить и считать все дискретно.
NH> А что делать при вставке в начало? Пересчитывать все?
Если данных немного, то можно и все пересчитать. Если много, то обычно хранят остатки и/или обороты с некоторой периодичностью, и пересчитывают их. Это стандартная задача для учетных систем.
NH> Да нет, задача самая реальная. Есть склад готовой продукции. Несколько раз в день мы его пополняем (увеличиваем кол-во). Несколько раз в день у нас с него забирают товар (уменьшаем кол-во). Размер склада ограничен. Нам нужно уметь ответить на вопросы: NH> — можно ли в день X1 взять со склада кол-во Y1? Если нельзя в X1, то когда можно? NH> — можно ли в день X2 добавить на склад Y2 продукции (т.е. влезет ли)?
А, логистика. Привозят и забирают товар ведь дискретными порциями, а не непрерывно. Так и нужно моделировать. Если планируете оборот X в месяц, то раскладываете на X1, X2, ..., X31 и в таком виде вносите в базу. И, кстати, раскладывается не обязательно равномерно, бывают сезонные колебания и т.п. Также вносите приход. Затем ежедневно заменяете план на факт. Или не заменяете, а вносите параллельно, для возможности сравнения.
Итого, API будет примерно таким:
void Add(DateTime time, double quantity) // quantity может быть как положительным, так и отрицательным.void Withdraw(DateTime time, double quantity) // quantity может быть как положительным, так и отрицательным.double GetBalance(DateTime time); // возвращает остаток на момент времени
SomeStruct GetBalanceAndTurnover(DateTime start, DateTime end); // возвращает остатки на начало и конец и обороты за период
Вы обязательно захотите знать приход и расход за период, поэтому их нужно разделять.
Подумал тут за структуру данных.
(Всё равно, считаю, что база ежедневных остатков более практична в практической жизни. Исправления прошлого — ситуация нечастая, а для пакетного внесения изменений можно и отсортировать накладные по дате, чтобы в маляра Шлемюэля не играть).
Первое. Отказываемся от _/- в пользу пар одноломаных функций _/
v(t) = k*(t-t0)*H(t-t0), где H — единичная ступенька.
Производная, ясное дело, это просто отмасштабированная ступенька
v'(t) = k*H(t-t0)
где k — величина градиента, t0 — точка перелома
Второе. Строим балансированное дерево суммирования.
Каждый узел содержит ключ — некоторый момент времени t0, и значение (s,s') — суммарный остаток и суммарный градиент левого поддерева.
Каждому узлу также соответствует вычисляемое значение: остаток и градиент на момент времени t0 — (v(t0), v'(t0)) — равен сумме (s,s') предков при спуске вправо.
Нахождение v(t) — бежим по дереву, ищем узел с t0<=t, находим (суммируя спуски вправо) v(t0), v'(t0), ну а дальше тривиально: v(t) = v(t0) + v'(t0)*(t-t0)
Добавление нового узла (t,k) — бежим по дереву и всюду, где спускаемся влево, вносим поправки: (s,s') += (k*(t-t0),k). Наконец, добавляем левый узел ts=0,s'=k).
Таких правок будет логарифмическое количество.
Дерево может быть двоичным или страничным (Б-дерево, иерархия дни-недели-месяцы-годы и т.п.) В последних случаях мысленно представим себе страницу как двоичное дерево:
И что характерно, совсем необязательно, чтобы все ключи дерева соответствовали точкам переломов. Еженедельные, ежемесячные, ежегодные остатки вполне могут существовать сами по себе — только для инициализации такого дерева придётся сделать вид, что там фиктивные переломы с нулевым градиентом.
Всем спасибо за хорошие советы. Сейчас буду имплементить. Потом отпишусь и расскажу, что в итоге получилось.
P.S. Я уже спросил в ответе к watchmaker, навсякий случай продублирую тут. А как можно обработать мгновенные добавления? Т.е. добавления, которые выглядят на графике как вертикали. Мы не можем задать вертикали линейной функцией.
Во всем разобрался, большое спасибо. Это должно работать.
Есть одна проблема (о которой я вначале умолчал, потому что не хотел усложнять начальное условие). Как быть с "мгновенным" добавлением/удалением? Т.е. в момент времени 5 мы добавили 10 единиц сырья. Вертикальную линию нельзя задать функцией вида y=kx.
— Можно сделать, чтобы каждая вершина имела две величины: начальную и конечную, но они были бы одинаковыми для диагоналей и разными для вертикалей.
Здравствуйте, NoHate, Вы писали:
NH>Есть одна проблема (о которой я вначале умолчал, потому что не хотел усложнять начальное условие). Как быть с "мгновенным" добавлением/удалением?
Можно просто хранить мгновенные изменения рядом с линейными.
Если раньше в узле дерева хранилась пара (k,t), где k — скорость наполнения в ед./cут., а t — время начала наполнения (и эта же величина была ключом в дереве), то теперь можно хранить тройку чисел (k,t,b), где b — мгновенное изменение товара в момент t. Тогда у всех интервальных заполнений будет нулевым значение b, а у всех мгновенных заполнений будет нулевым значение k. И таким образом мгновенная вставка или расход будет сводится к вставке одной вершины в дерево (или модификации, если вершина с таким же ключом t уже была).
На реализацию запросам суммы через augmented trees эта модификация также никак негативно не повлияет. Даже в некотором смысле станет проще — все подряд объясняют аугментацию деревьев через суммирование b — можно просто брать готовую реализацию :)
Здравствуйте, NoHate, Вы писали:
NH> А как можно обработать мгновенные добавления? Т.е. добавления, которые выглядят на графике как вертикали. Мы не можем задать вертикали линейной функцией.
Для того, чтобы получить значение в точке, нам нужно знать сумму всех предыдущих k и сумму всех предыдущих значений.
Попробуем определить значение в точке 5, тут все ок:
k(5) = k(2) + k(4) = 2 - 5 = -3 // k = -3, это верное значение, мы можем это проверить на графике
Со значением выходит проблема. Значение чего нужно хранить в вершине?
— Мы можем хранить начальное изменения кол-ва, но т.к. первое значение из пары всегда 0, то мы получим неверное значение при пересечении нескольких отрезков.
Например, если попытаемся определить начальное значение для точки 5, то получим 0.
v(5) = v(2) + v(4) = 0 + 0 // это неверно
— Напрашивается решение при пересечении отрезков, обновлять значения для пересекаемых отрезков, в соответствии с добавляемым k. Но т.к. у нас дерево хранит доп. информацию, то обновление каждой вершины, приведет к обновлению значений всех вершин до самого корня (log(n)). Получается, что трудоемкость будет O(n) = 2log(n) + k * log(n), где k — кол-во пересечений
Может быть можно определить кол-во более красивым способом?
, то вставляются неправильные пары. Ибо сумма всех k не равна нулю, а значит операция разгрузки, будучи единожды начата, никогда не остановится.
Ступенька же store.Add(4, 6, -10.0) раскладывается в такую сумму: Uk=-5,t=4(x) + Uk=5,t=6(x). То есть в момент t=4 начинается расход со скоростью -5 ед./сутки и продолжается до бесконечности, а в момент времени t=6 начинается приход со скоростью +5 ед./сутки, который также продолжается до бесконечности. Очевидно, что в моменты времени ≥ 6 они друг-друга скомпенсируют, но из-за разницы во времени старта к этому моменту на складе как раз и накопится расход в 10 ед., который при отсутствии других операций более не будет изменяться.
Аналогично, нужны две вставки для Uk=2,t=2(x) и Uk=-2,t=7(x).
То бишь у тебя после двух операций в структуре будет 4 узла:
Uk=2,t=2;
Uk=-5,t=4;
Uk=5,t=6;
Uk=-2,t=7.
NH>Для того, чтобы получить значение в точке, нам нужно знать сумму всех предыдущих k и сумму всех предыдущих значений. NH>Попробуем определить значение в точке 5, тут все ок:
Мне почему-то удобнее рассуждать в терминах функций, а не суммировать компоненты по отдельности. В точке x=5 у нас есть две функции с ключами t ≤ x = 5, найдём их сумму: Uk=2,t=2(x) + Uk=-5,t=4(x) ≎ Uk=-3,t=16/3(x).
Тут нельзя поставить строгое равенство, так как в общем случае сумма двух U функций не будет сама U-функцией, но нас интересует лишь окрестность точки x = 5, а в ней все U можно просто заменить на линейные (без изломов), что, собственно, потребует лишь суммирования двух линейных функций. Ну а это уже тривиально проверяется, что 2(x – 2) + (–5)(x – 4) = (–3)(x – 16/3).
Собственно, теперь подставляем в Uk=-3,t=16/3(x) значение x = 5 и получаем: Uk=-3,t=16/3(5) = (–3)(5 – 16/3) = 1. То есть при условии изначально пустого склада в момент x = 5 на складе окажется ровно 1 ед. чего-то.
NH>Я опять нарисовал все это на картинке: NH>http://glui.me/?i=eotdh7ezy4bn8ph/2015-11-20_at_19.18_2x.png/
Если рассматривать ситуацию, когда склад был изначально заполнен на 2 ед., то это просто разрешается добавлением пятой вершины в коллекцию, например такой: {k=0, t=-∞, b=2} (во всех предыдущих операциях значение b было равно 0, так как они не были мнгновенными). И теперь полностью аналогично суммируя все функции с t ≤ x = 5 получаем, что количество в окрестности x = 5 теперь характеризуется выражением (–3)(x – 16/3) + 2, чего в общем-то и следовало ожидать.
Ну и замечу, что при реализации работы с функциями вида k(x – t) + b иногда бывает полезно раскрыть скобки для упрощения выражений :) Сделав это, ты наверняка получишь те же самые свои «суммы предыдущих ĸ» и «суммы предыдущих накоплений».
Здравствуйте, NoHate, Вы писали:
NH>Может быть есть какие-то более красивые решения?
В моей модели проблемы нет.
Как я уже предлагал, каждый узел хранит пару (s,s') — текущий остаток и текущий градиент.
Мы или добавляем новый градиент (+0,+k), — корректируя все правые узлы на том же ярусе: (s,s'+k)
Или добавляем новый остаток (+q,+0), — корректируя их (s+q,s')
Ну и для древовидной структуры, чтобы спроецировать лист на линию, надо суммировать верхние ярусы. Если из прошлого поста это было неочевидно, показываю:
Разобрался еще раз. И правда, в начале не до конца все понял. Сейчас все переделал, работает верно. Все тесты, которые я заранее написал, прошли.
Не знаю, может в универе меня плохо учили (или даже в школе), но идея с разложением ломанной на функции y=k(x-t) мне бы никогда в голову не пришла. Чувствую, что где-то я прохалявил, когда учился, но где — не пойму .
Здравствуйте, Кодт, Вы писали:
К>В моей модели проблемы нет. К>Как я уже предлагал, каждый узел хранит пару (s,s') — текущий остаток и текущий градиент.
Может быть я недостаточно разобрался с вашим решением, но я попробовал хранить текущий коэффициент и текущий остаток и встретился вот с такой проблемой: http://rsdn.ru/forum/alg/6252178.1
Здравствуйте, NoHate, Вы писали:
NH>Может быть я недостаточно разобрался с вашим решением, но я попробовал хранить текущий коэффициент и текущий остаток и встретился вот с такой проблемой: NH>http://rsdn.ru/forum/alg/6252178.1
Корректировка всех узлов на ярусе весьма накладная вещь, не так ли?
Блин, я там соврал. Корректировать надо не ярус, а только правых соседей в страницах от текущей вверх до корня. А это — логарифмическое время.
Для страничных деревьев (Б- и иерархические) это выглядит вот так
0 ------------------------------------------------------------------> t
0---------------------------------------------------------------Z в корневой странице можно держать итог от и до
\
o-----------------------------Y---Y---Y
/ | | | \
o---o-----------Y---Y----Y o----o----o----o
/ | | | | \ / | | | \
o-X-Y-Y oooo oooo oooo oooo oooo
/ | | | \
o - нетронутые
X - текущий
Y,Z - изменяемые вслед
страницы зрительно растянуты, чтобы упорядочить все ключи по времени
То есть, если у нас иерархия дни-месяцы-года, то нужно
— поменять остатки (и градиенты) в днях, начиная с текущего
— в месяцах, начиная со следующего (но не в днях внутри месяцев)
— в годах, начиная со следующего (но не в месяцах и днях там)
Для двоичных
0 --------------------> t
Y
________/ \
o o
/ \____
o Y
/ \
X o
/ \
o o
Если X — левый ребёнок, то родителя нужно корректировать (он "следующий" по времени), если правый — не нужно.
Корректировать вниз не нужно вообще, потому что, по правилам расчётов, итоговое значение — это сумма значений на узлах от корня до текущего. И правки будут учтены автоматически.
Для Б+ деревьев всё хуже, т.к. данные только в листьях, а в остальных страницах лишь ключи (метки времени).
Мы же с самого начала делаем augmented tree.
Перекуём баги на фичи!
s=0,s'=k).