Suponha que você esteja interessado em vários valores independentes de variação de tempo, cada um dos quais representa o estado atual de algo. Os valores não mudam em nenhuma programação fixa e novos valores não podem ser previstos a partir dos antigos. Para um exemplo concreto, digamos que você tenha vários estoques e esteja interessado em acompanhar seus valores, além de obter uma atualização sobre um estoque individual sempre que uma negociação for feita sobre esse estoque. (Meu problema real não é sobre ações, mas espero que elas tornem o que eu estou conseguindo mais compreensível.)

Além de apenas saber o preço atual de cada ação, você também gostaria de poder escolher um ponto arbitrário no passado e obter um "instantâneo" que informava qual era o preço de negociação mais recente de cada ação naquele momento. . Por exemplo, você deve poder dizer "Qual foi o valor mais recente de todas as ações que estou rastreando a partir das 16:53 da última terça-feira?" e obtenha uma resposta precisa com eficiência.

Posso pensar em três maneiras de fazer isso, mas não estou muito feliz com nenhuma delas.

1. Mantenha um diário. Mantenha uma lista de todas as negociações na ordem da sequência temporal. A atualização está apenas adicionando à lista e a consulta é uma varredura linear para trás no tempo, iniciando com a primeira entrada cujo carimbo de data / hora está ativado ou anterior ao carimbo de data / hora especificado. Isso tornaria a atualização uma operação de tempo constante, mas talvez você precise varrer todo o diário para encontrar um valor para todas as negociações, portanto, Atualização é O (1) e Instantâneo é O (u), em que u é o número total de atualizações. A memória necessária é O (u) por razões óbvias.

2. Escreva pontos de verificação. Mantenha um único diário como antes, mas, em vez de cada entrada contendo apenas o novo preço das ações, a atualização contém o preço atual (a partir dessa atualização) paracada estoque. É barato calcular: como a última atualização também contém todas essas informações, basta copiá-las, exceto a única ação cujo preço realmente mudou. Agora, o Snapshot pode ser feito com uma operação O (log u) (usando a pesquisa binária no diário para localizar a última entrada que vem antes ou no carimbo de data / hora especificado). No entanto, a atualização se torna O (s) onde s é o número de estoques no sistema e, além disso, a memória total necessária vai de O (u) na primeira estratégia para O (s * u) --- ambos os problemas se ambos são grandes.

3. Revistas separadas. Mantenha um diário separado para cada material e escreva atualizações para cada material em seu próprio diário, novamente em ordem cronológica. Para capturar instantâneos, examine cada diário e use uma pesquisa binária para encontrar a atualização correta. Requer memória O (u), Atualização é uma operação O (1) e o Snapshot pode ser feito em O (s * log u). Esse é o meu método favorito dos três, mas acho que provavelmente poderia ser melhorado, pois ignora qualquer relação entre o tempo das atualizações em diferentes estoques.

Existe uma maneira melhor que eu estou perdendo? Esse é um problema que foi estudado e tem uma solução geralmente aceita?