Структура данных для обновления значений и запроса состояния значений за один раз в прошлом

Question

Предположим, вы заинтересованы в наборе независимых переменных, изменяющихся во времени, каждое из которых представляет текущее состояние чего-либо.Значения не меняются ни в одном фиксированном расписании, и новые значения нельзя предсказать из старых.В качестве конкретного примера, скажем, у вас есть куча акций, и вы заинтересованы в отслеживании их стоимости, и вы получаете обновленную информацию об отдельной акции, когда совершается сделка по этой акции.(Моя настоящая проблема не в акциях, но, надеюсь, они делают то, что я получаю, более понятным.)

Помимо того, что вы просто знаете текущую цену каждой акции, вы также хотели бы иметь возможностьвыбрать произвольную точку в прошлом и получить «снимок», который скажет вам, какой была самая последняя торговая цена для каждой акции в то время.Так, например, вы должны быть в состоянии сказать: «Какова была самая последняя стоимость каждой акции, которую я отслеживаю по состоянию на 16:53 в прошлый вторник?»и получить точный ответ эффективно.

Я могу придумать три способа сделать это, но я не очень доволен ни одним из них.

1.Вести журнал. Вести список всех сделок в порядке временной последовательности.Обновление - это просто добавление в список, а запрос - это линейное сканирование назад во времени, начиная с первой записи, чья временная метка включена или раньше указанной метки времени.Это может привести к обновлению в режиме постоянного времени, но вам, возможно, придется сканировать весь журнал, чтобы найти значение для всех сделок, поэтому значение «Обновление» равно O (1), а «Снимок» равно O (u), где «u» - общее количество обновлений.Требуемая память - O (u) по очевидным причинам.

2.Напишите контрольные точки. Поддерживайте отдельный журнал, как и раньше, но вместо каждой записи, содержащей только новую цену акций, обновление содержит текущую цену (по состоянию на это обновление) для каждой акции.Это дешево подсчитать: поскольку последнее обновление также содержит всю эту информацию, вы просто копируете ее полностью, за исключением одной акции, цена которой фактически изменилась.Теперь снимок можно сделать с помощью операции O (log u) (используя двоичный поиск в журнале, чтобы найти последнюю запись, которая предшествует указанной временной отметке или находится на ней).Однако Update становится O (s), где s - это количество акций в системе, и, кроме того, общая требуемая память переходит от O (u) в первой стратегии к O (s * u) - обе проблемы, еслии s, и вы большие.

3.Отдельные журналы. Ведение отдельного журнала для каждой акции и запись обновлений для каждой акции в свой собственный журнал, опять же в хронологическом порядке.Чтобы сделать снимок, просмотрите каждый журнал и используйте двоичный поиск, чтобы найти правильное обновление.Для этого требуется память O (u), обновление - операция O (1), а моментальный снимок может быть выполнен за время O (s * log u).Это мой любимый метод из трех, но я чувствую, что, возможно, его можно улучшить, так как он игнорирует любые отношения между сроками обновления для разных акций.

Есть ли лучший способ, по которому я скучаю?Это проблема, которая была изучена и имеет общепринятое решение?

Answer 1

Ознакомьтесь с литературой по Постоянным структурам данных . В частности, в этой ранней статье описывается построение постоянного двоичного дерева поиска, которое поддерживает логарифмические операции, но к которому можно получить доступ в любой версии (например, в определенный момент времени). Доступ к частям структуры, которые не были обновлены в какой-либо конкретной версии, естественно, выглядит как предыдущая предыдущая. Таким образом, ваши естественные операции будут выполняться за время O (log s), и структура может занимать пространство O (u), если вы знаете все свои ключи заранее, и вам никогда не придется балансировать, или пространство O (u * log s), если каждое обновление изменяло указатели O (log s).

Эти примечания к классу , кажется, описывают то, что вам нужно реализовать, в довольно простых терминах.

Answer 2

Идея постоянных структур данных, представленная Новелократом, представляется наилучшим решением для общего случая.Полагаю, в вашем случае все будет хорошо.

Я только что подумал о вариации (2).Управление динамическим массивом, упорядоченным по меткам времени модификации.Каждая запись соответствует версии и состоит из массива s элементов.Вместо того, чтобы хранить все записи о запасах для каждой версии, делайте это лениво;при создании версии новой записи будет присвоен только один товар, чье значение изменилось.Другие элементы s-1 указывают на ноль.

При выполнении поиска по времени T и запасу S следует линейно сканировать версии в обратном направлении, начиная с самой последней до времени T. Сканирование продолжается до тех пор, пока вы не найдете ненулевое значение для S. Затем выпродолжайте, исправляя все нулевые указатели для S, которые вы нашли на своем пути, чтобы последующие запросы к ним были эффективными.

Это решение обеспечивает O (1) время добавления и амортизированный запросвремя O (log u).Полные запросы моментальных снимков занимают O (s + log u), что лучше, чем реализация (4).Пространство по-прежнему равно O (u * s).

Амортизированная стоимость запросов следует из того факта, что всякий раз, когда мы запрашиваем элемент S версии V, все значения S версий <= V являются фиксированными.Таким образом, последовательность из u уникальных запросов выполняет 2 * u посещения массивов (независимо от их порядка!), Что приводит в среднем к 2 посещениям на запрос.Поэтому мы остаемся с начальным временем поиска O (log u). </p>

Answer 3

Я сомневаюсь, что вы найдете решение, превосходное во всех отношениях. То, что вы выбираете, во многом зависит от того, какие компромиссы вы готовы сделать. Если снимки встречаются редко, № 3 - отлично; если они часты, вероятно, нет: O ( S log U ) может быть убийцей, например, для хранилища контроля версий.

Вот еще несколько идей, которые мне нравятся:

4. Периодические контрольные точки. В указанный интервал (каждые x часов, каждые y обновления, независимо от того, что) создает контрольную точку, содержащую текущую цену для каждой акции. Выяснение данных в определенный момент времени означает поиск самого последнего снимка до этого времени, а затем добавление отдельных обновлений. Это будет иметь ту же асимптотическую производительность, что и # 2, но константа умножения для обновлений и использования памяти будет намного ниже, так как вы будете делать гораздо меньше снимков.

5. Контрольные точки только для дельты. То же, что и # 4, но не делайте снимок всей системы. Вместо этого сохраняйте только те элементы, которые изменились с предыдущей контрольной точки. Неизменные записи будут найдены в предыдущих контрольных точках. Это экономит много времени при написании контрольной точки и значительно уменьшает использование памяти. Если & Delta; U - это среднее число обновлений между контрольными точками, то оба значения теперь равны O (& Delta; U ). Это фактически будет фиксированная сумма; со временем база данных будет расти, но не среднее число обновлений на контрольную точку. Время обновления можно считать амортизированным O (1), а использование памяти - O ( U ), затем.

Для чего это стоит, несколько лет назад я написал клон вики. Одна из проблем, с которыми я столкнулся, заключалась в том, как хранить дельты страниц. Я сохраняю только различия или я сохраняю полный текст страницы при каждом обновлении? Как мне сбалансировать скорость и использование памяти? Применение десятков или сотен различий в строке для восстановления страницы может быть слишком медленным, но хранение всей страницы, если кто-то только изменит одно предложение, будет весьма расточительным.

Я хотел что-то, что хорошо бы масштабировалось даже для больших, часто обновляемых страниц.

Я закончил с гибридным подходом, похожим на # 5. Я храню различия с периодическими снимками полной страницы. Чтобы выяснить, когда делать снимки, я сравниваю текст новой страницы с текстом самого последнего снимка. Если размер различий больше, чем вдвое больше, чем текст всей страницы, я сохраняю полный текст страницы вместо различий. Таким образом, если люди делают небольшие обновления, я могу сохранять различия, но в конце концов, как только страница изменится достаточно, я сделаю новый снимок.