Eficiente recorrido de una lista de cambios.

Question

Tengo una lista de cambios en una lista - Agregar y eliminar. La lista podría ser enorme, digamos 10,000 artículos.

Quiero saber el estado de la lista después del cambio 9'000.

Podría recorrer la lista desde el principio hasta el cambio de 9'000. Eso me parece un poco largo.

Podría mantener una lista de elementos y registrar cuándo se agregan y cuándo se eliminan, luego recorra esta lista para ver qué hay en la lista con respecto a un cambio en particular. Si las Adiciones y eliminaciones fueran igualmente probables, reduciría a la mitad la cantidad de elementos de la lista que tendría que revisar ...

Pero la notación Big O dice que reducir a la mitad el tamaño del problema no hace que las cosas sean más eficientes (si lo he entendido correctamente).

Podría almacenar en caché el estado de la lista cada 100 o 1000 cambios ... pero, una vez más, la gran O dice que dividir el número de elementos entre 'n' no hace que las cosas sean más eficientes.

Entonces, ¿cuál es la forma eficiente de hacer esto? ¿Hay una forma eficiente de hacer esto?

Más detalles: Específicamente, estoy rastreando las asignaciones de memoria / desasignaciones en un asignador personalizado. Cada asignación / desasignación es un evento en la lista. Cada asignación tiene una identificación única. Me gustaría saber qué se asigna actualmente después de (por ejemplo) 9'000 eventos.

Mi primera idea fue almacenar, para cada ID, el evento que fue asignado y el evento que fue desasignado. Luego, recorra esta lista hasta la primera asignación cuyo evento de asignación sea mayor que 9000. Pero como dije, esto solo reduciría a la mitad la cantidad de elementos que tendría que revisar.

Me gusta el punto señalado por Mike F: caminar desde el artículo número 100 más cercano es tiempo constante ...

Answer 1

Si almacena en caché el estado de la lista cada X cambio, entonces puede hacer un corte binario para llegar a dos estados almacenados en la caché que limitan el cambio que está buscando, luego camina al menos X elementos para llegar al elemento sí mismo. Eso es O (registro N), más o menos.

Pero más generalmente, reducir la complejidad de O grande es el medio, no el fin. Si su lista es generalmente de 10,000 artículos, entonces debería preocuparse por hacerlo rápido para N = 10,000, ya sea reduciendo la complejidad o simplemente haciéndolo más rápido.

Editar: Vaya, acabo de leer tu pregunta con más cuidado. Si almacena en caché el estado de cada (por ejemplo) 100 elementos, no está buscando, por lo que ni siquiera necesita hacer un corte binario, simplemente salta directamente al estado de almacenamiento en caché más cercano y camina como máximo 100 elementos para llegar al elemento. sí mismo. Entonces, ¿ese es un algoritmo de tiempo constante no?

Answer 2

¿Con qué tipo de estructura estás trabajando? No hay una forma eficiente de recorrer una estructura de datos genérica, pero hay miles de métodos de optimización y métodos eficientes para estructuras específicas.

Y sí, si tiene un algoritmo que es O (n) de complejidad de tiempo, reducir a la mitad el número de elementos no lo cambiará de O (n) complejidad ... pero esto significará que cada nuevo elemento solo tiene la mitad El efecto que tenía originalmente. La notación Big O es una buena manera de clasificar los algoritmos, pero en realidad no es tan eficiente como en muchos casos (un buen ejemplo es la clasificación. Quicksort es peor que la combinación en el peor de los casos ... pero puede implementar quicksort más eficientemente que mergesort para casi cualquier aplicación distinta de las que se ocupan de clasificar millones de artículos)

Answer 3

'Marca de tiempo' o marque cada inserción y eliminación, luego se necesitaría un recorrido simple para encontrar cambios (O (n)).