¿Algoritmo de reducción de cola?

Question

Tengo una cola de actividades compartidas entre clientes, capturando la actividad del usuario y ejecutada por un robot en el otro sitio. Un ejemplo de actividades podría ser:

CREATE FOLDER /docs 
CREATE FILE /docs/journal.txt 
DELETE FILE /docs/blog.txt 
MOVE FOLDER /docs/images /docs/photos 
... 

A menudo hay actividades que se pueden reducir a una sola, o ninguna. Por ejemplo:

CREATE FOLDER /docs 
RENAME FOLDER /docs /documents 

¿Se puede cambiar simplemente:

CREATE FOLDER /documents 

Y algo como:

CREATE FOLDER /docs 
RENAME FOLDER /documents 
DELETE FOLDER /documents 

Puede ser quitado por completo de la cola.

Este tipo de reducción/optimización parece ser un problema muy genérico, y antes de atacar quiero probar una solución genérica. Parece un problema de optimización de ruta de acceso.

¿Alguna idea?

Answer 1

No conozco ninguna biblioteca o marco que pueda hacer esto por usted. Por otro lado, tendrías que especificar la lógica detrás de ti mismo, y como yo lo veo, esa sería la mayor parte del trabajo de todos modos.

Aquí es el enfoque me gustaría tener:

1. Haz una ordenación topológica de las acciones (cambiar el nombre de la carpeta "depende de" crear carpeta y así sucesivamente ...)

2. Cada comando sin dependencias representa una "raíz" en un árbol de dependencias.

3. Contraiga estos árboles de forma recursiva desde cada raíz.

Answer 2

Una opción (aunque sea un poco pesado) sería caminar a través de los registros de cola y simular las operaciones que se realizan en el sistema de archivos en un árbol de representación que se crea dentro del programa. Puede rastrear, para cada directorio al que se hace referencia, qué operaciones netas se realizan en él. Una vez que haya terminado, podrá recorrer la estructura de árbol modificada y generar una serie de comandos que representen la transformación de red aplicada a cada directorio y subdirectorio.

Espero que esto ayude!

Answer 3

1. Definir todas sus operaciones (crear, renombrar, mover)
   
2. definir una clase de comandos que contiene los parámetros de funcionamiento + para la operación.
   
3. Implementa algo que te dirá si se pueden combinar dos comandos y cuál es el resultado de esa combinación.

Debo asumir que solo puede combinar comandos que se siguen inmediatamente o de lo contrario podría introducir efectos secundarios no deseados. Entonces, cuando vaya a ejecutar un comando fuera de su cola, comience a leer/abrir/construir un comando hasta que encuentre un comando que no se pueda combinar.