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

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

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

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

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

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

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

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

Ответы на вопрос(2)

Ваш ответ на вопрос