Algoritmo di riduzione della coda?

Question

Ho una coda di attività condivisa tra i client, che acquisisce attività dell'utente ed eseguita da un robot sull'altro sito. Un esempio di attività potrebbe essere:

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

Spesso ci sono attività che possono essere ridotte a una singola o nessuna. Per esempio:

CREATE FOLDER /docs 
RENAME FOLDER /docs /documents 

può essere semplicemente modificato in:

CREATE FOLDER /documents 

E qualcosa di simile:

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

può eliminare dalla coda.

Questo tipo di riduzione/ottimizzazione sembra un problema molto generico e prima di attaccarlo vorrei provare qualche soluzione generica. Sembra un problema di ottimizzazione del pathfinder.

Qualche idea?

Answer 1

Non conosco alcuna libreria o framework che possa fare questo per voi. D'altra parte, dovresti specificare la logica dietro di te e, a mio avviso, quella sarebbe comunque la maggior parte del lavoro.

Ecco l'approccio vorrei prendere:

1. fare una sorta topologica delle azioni (rinominare la cartella "dipende da" creare la cartella e così via ...)

2. Ogni comando senza le dipendenze rappresentano una "radice" in un albero delle dipendenze.

3. Comprimi questi alberi in modo ricorsivo a partire da ogni radice.

Answer 2

Una possibilità (anche se un po 'un peso massimo) sarebbe quella di camminare sopra i record di coda e simulare le operazioni che vengono eseguite sul file system su una rappresentazione ad albero che si crea all'interno del programma. È possibile tenere traccia, per ciascuna directory a cui viene fatto riferimento, di quali operazioni finali vengono eseguite su di essa. Una volta terminato, è possibile passare sulla struttura ad albero modificata e generare una serie di comandi che rappresentano la trasformazione netta applicata a ciascuna directory e sottodirectory.

Spero che questo aiuti!

Answer 3

1. definire tutte le operazioni (creare, rinominare, spostare)
   
2. definire una classe di comando che contiene l'operazione + parametri per l'operazione.
   
3. Implementare qualcosa che indichi se è possibile combinare due comandi e quale sarà il risultato di tale combinazione.

Devo supporre che si possano combinare solo comandi che si susseguono immediatamente oppure si potrebbero introdurre effetti collaterali indesiderati. Quindi, quando si va ad eseguire un comando dalla coda yoru, iniziare a fare il peeking/popping/costruire un comando finché non si incontra un comando che non può essere combinato in esso.