Suponga que está interesado en un montón de valores independientes que varían en el tiempo, cada uno de los cuales representa el estado actual de algo. Los valores no cambian en ningún horario fijo y los valores nuevos no se pueden predecir a partir de los antiguos. En aras de un ejemplo concreto, supongamos que tiene un montón de acciones y está interesado en realizar un seguimiento de sus valores, y recibe una actualización sobre una acción individual cada vez que se realiza una operación en esa acción. (Mi problema real no es sobre las existencias, pero espero que hagan que lo que obtengo sea más comprensible).

Además de solo conocer el precio actual de cada acción, también le gustaría poder elegir un punto arbitrario en el pasado y obtener una "instantánea" que le indicara cuál era el precio de cotización más reciente para cada acción en ese momento . Entonces, por ejemplo, debería poder decir "¿Cuál fue el valor más reciente de cada acción que estoy rastreando a las 4:53 PM del martes pasado?" y obtenga una respuesta precisa de manera eficiente.

Puedo pensar en tres formas de hacer esto, pero no estoy muy contento con ninguna de ellas.

1. Mantenga un diario. Mantenga una lista de todas las operaciones en orden de secuencia de tiempo. La actualización solo se agrega a la lista, y la consulta es una exploración lineal hacia atrás en el tiempo que comienza con la primera entrada cuya marca de tiempo está activada o antes de la marca de tiempo especificada. Esto haría que la actualización sea una operación de tiempo constante, pero es posible que tenga que escanear todo el diario para encontrar un valor para todos los intercambios, por lo que Actualizar es O (1) e Instantánea es O (u) donde u es el número total de actualizaciones. La memoria requerida es O (u) por razones obvias.

2. Escribir puntos de control. Mantenga un diario único como antes, pero en lugar de que cada entrada contenga solo el precio de las acciones nuevas, la actualización contiene el precio actual (a partir de esa actualización) paracada valores. Esto es barato de calcular: dado que la última actualización también tiene toda esa información, simplemente copie todo excepto la acción cuyo precio realmente cambió. Ahora Snapshot se puede hacer con una operación O (log u) (usando la búsqueda binaria en el diario para localizar la última entrada que viene antes o en la marca de tiempo especificada). Sin embargo, la actualización se convierte en O (s) donde s es el número de existencias en el sistema y, además, la memoria total requerida va de O (u) en la primera estrategia a O (s * u), los cuales son problemas si ambos sois grandes.

3. Revistas separadas. Mantenga un diario separado para cada stock y escriba actualizaciones para cada stock en su propio diario, nuevamente en orden cronológico. Para obtener una instantánea, revise cada diario y use una búsqueda binaria para encontrar la actualización correcta. Requiere memoria O (u), la actualización es una operación O (1) y la instantánea se puede hacer en tiempo O (s * log u). Este es mi método favorito de los tres, pero creo que probablemente podría mejorarse, ya que ignora cualquier relación entre el momento de las actualizaciones en diferentes acciones.

¿Hay una mejor manera que me estoy perdiendo? ¿Es este un problema que ha sido estudiado y tiene una solución generalmente aceptada?