Структура данных для обновления значений и запросов состояния значений за один раз в прошлом
Предположим, что Вы интересуетесь набором независимых изменяющихся во времени значений, каждое из которых представляет текущее состояние чего-то. Значения не изменяются ни по какому установленному графику, и новые значения не могут быть предсказаны от старых. Ради конкретного примера скажем, у Вас есть набор запасов, и Вы интересуетесь отслеживанием их значений, и Вы получаете обновление об отдельном запасе каждый раз, когда торговля сделана на том запасе. (Моя фактическая проблема не о запасах, но надо надеяться они делают то, что я достигаю более понятный.)
В дополнение только к знанию текущей цены каждого запаса также требуется смочь выбрать произвольную точку в прошлом и получить "снимок", который сказал Вам, чем новая торговая цена за каждый запас была в то время. Так, например, необходимо ли смочь сказать, "Каково было новое значение каждого запаса, который я отслеживаю по состоянию на 16:53 в прошлый вторник?" и получите точный ответ эффективно.
Я могу думать о трех способах сделать это, но я не очень доволен ни одним из них.
1. Ведите дневник. Ведите список всех отраслей в порядке последовательности времени. Обновление просто добавляет к списку, и запрос является линейным сканированием назад во время, запускающееся с первой записи, метка времени которой идет или ранее, чем штамп требуемого времени. Это сделало бы обновление постоянной операцией времени, но Вам, возможно, потенциально придется просканировать весь журнал для нахождения значения для всех отраслей, таким образом, Обновление является O (1), и Снимок является O (u), где u является общим количеством обновлений. Требуемая память является O (u) по очевидным причинам.
2. Запишите контрольные точки. Поддержите единственный журнал как прежде, но вместо каждой записи, содержащей просто новый курс акций, обновление содержит текущую цену (с того обновления) для каждого запаса. Это дешево для вычисления: так как последнее обновление имеет всю эту информацию также, Вы просто копируете все это за исключением одного запаса чья цена, на самом деле измененная. Теперь Снимок может быть сделан с O (зарегистрируйте u), операция (использующий двоичный поиск на журнале для определения местоположения последней записи, которая происходит прежде или в указанную метку времени). Однако Обновление становится O (s), где s является количеством запасов в системе, и кроме того требуемая общая память идет от O (u) в первой стратегии к O (s*u)---, оба из которых являются проблемами, если и s и Вы являетесь большими.
3. Разделенные журналы. Поддержите отдельный журнал для каждого запаса и обновления записи для каждого запаса в его собственный журнал, снова в хронологическом порядке. Для создания снимков пробегитесь через каждый журнал и используйте двоичный поиск для нахождения корректного обновления. Это требует O (u) память, Обновление является O (1) операция, и Снимок может быть сделан в O (s *, регистрируют u), время. Это - мой любимый метод этих трех, но я чувствую, что он мог, вероятно, быть улучшен, так как он игнорирует любые отношения между синхронизацией обновлений через различные запасы.
Существует ли лучший способ, которым я отсутствую? Действительно ли это - проблема, которая была изучена и имеет общепринятое решение?
3 ответа
Я сомневаюсь, что вы найдете решение, превосходное по всем параметрам. То, что вы выберете, во многом зависит от того, на какие компромиссы вы готовы пойти. Если снимки делаются нечасто, подойдет №3; если они часты, то, вероятно, нет: O ( S log U ) может быть убийцей, например, для репозитория системы управления версиями.
Вот еще несколько идей, которые мне непонятно:
4. Периодические контрольно-пропускные пункты. Через определенный интервал (каждые x часов, каждые y обновления, независимо от того) создайте контрольную точку, содержащую текущую цену для каждой акции. Выявление данных в прошлый момент времени означает поиск самого последнего снимка до этого времени и последующее добавление отдельных обновлений. Это будет иметь ту же асимптотическую производительность, что и №2, но постоянная умножения для обновлений и использования памяти будет намного ниже, поскольку вы будете делать намного меньше снимков.
5. Контрольно-пропускные пункты только для дельты. То же, что и №4, но не делайте снимок всей системы. Вместо этого сохраните только те элементы, которые изменились с момента предыдущей контрольной точки. Неизмененные записи будут найдены в предыдущих контрольных точках. Это экономит много времени при написании контрольной точки и значительно сокращает использование памяти. Если Δ U - это среднее количество обновлений между контрольными точками, то оба они теперь равны O (Δ U ). Фактически это будет фиксированная сумма; база данных со временем будет расти, но не среднее количество обновлений на контрольную точку.Тогда вы можете рассматривать время обновлений как амортизированное O (1), а использование памяти - как O ( U ).
Как бы то ни было, несколько лет назад я написал клон вики. Одна из проблем, с которыми я столкнулся, заключалась в том, как хранить дельты страниц. Могу ли я хранить только различия или хранить полный текст страницы при каждом обновлении? Как мне сбалансировать скорость и использование памяти? Применение десятков или сотен различий подряд для реконструкции страницы может быть слишком медленным, но сохранение всей страницы, если кто-то изменяет только одно предложение, было бы довольно расточительным.
Я хотел что-то, что хорошо масштабировалось бы даже для больших, часто обновляемых страниц.
Я остановился на гибридном подходе, подобном # 5. Я храню различия с периодическими снимками полной страницы. Чтобы понять, когда делать снимки, я сравниваю текст новой страницы с текстом самого последнего снимка. Если размер разницы более чем наполовину меньше размера полной страницы, я сохраняю полный текст страницы вместо разницы. Таким образом, если люди делают небольшие обновления, я могу хранить различия, но в конечном итоге, когда страница достаточно изменится, я сделаю новый снимок.
Идея постоянных структур данных, представленная Новелократом, кажется лучшим решением для общего случая. Полагаю, в вашем случае это сработает.
Я только что придумал вариант (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).
Посмотрите литературу по Постоянным структурам данных. В частности, эта ранняя статья описывает построение постоянного двоичного дерева поиска, которое поддерживает логарифмические операции, но к которому можно получить доступ в любой версии (например, в момент времени). Доступ к частям структуры, которые не были обновлены в какой-то конкретной версии, естественно, обращается к последней предшествующей версии. Таким образом, вы можете выполнять естественные операции за время O(log s), а структура может занимать O(u) места, если вы заранее знаете все ключи и никогда не должны перебалансировать, или O(u * log s) места, если каждое обновление изменяет O(log s) указателей.
Эти заметки о классе, кажется, описывают то, что вам нужно реализовать в довольно простых терминах.