Mantenimento di un elenco di nodi con requisiti impegnativi

Naviga le tue risposte
5

Questa è una domanda riguardante la progettazione di una collezione di nodi ordinati che hanno alcuni requisiti che sto cercando di soddisfare.

Nell'area problematica con cui ho a che fare abbiamo percorsi che sono una raccolta ordinata di nodi. Un percorso sarà compreso tra 1000 e 25000 nodi. Un nodo stesso è un oggetto complesso.

Devo essere in grado di mantenere i nodi, idealmente in un database relazionale (dato che l'applicazione più ampia è attualmente distribuita usando un'architettura che usa un database relazionale per la persistenza). Ho due requisiti separati che presentano una difficoltà nel modellare i dati.

  1. Devo essere in grado di inserire nodi (o puntatori ai nodi) al centro dell'elenco e riorganizzare l'elenco al volo.
  2. Devo essere in grado di recuperare l'elenco nel suo ordine sequenziale corretto con un indice efficiente e la possibilità di accesso casuale.

L'unico modo in cui penso di poter soddisfare il primo requisito è quello di modellare i dati come una lista concatenata in cui ogni nodo punta al nodo successivo nell'elenco, il che consentirebbe di modificare e riorganizzare l'elenco al volo.

L'unico modo in cui penso di poter soddisfare il secondo requisito sarebbe quello di ordinare in sequenza l'elenco in modo che ogni nodo abbia un riferimento alla sua posizione nell'elenco e ordini / acceda all'elenco per la posizione.

C'è qualche altro metodo che potrei usare che possa soddisfare i due requisiti o sono bloccato con la costruzione di un ibrido che impiega entrambi i metodi in momenti diversi a seconda del contesto operativo e che mantiene sincronizzati i due tipi di referenziamento?

    
posta AlexC 06.10.2011 - 10:55
fonte

3 risposte

2

Un ibrido in forma di matrici collegate sembra un compromesso tra le due strutture. Ancora veloce accesso all'indice, sovraccarico relativamente basso con inserimenti casuali e molto basso quando si inserisce in lotti.

Wikipedia nomina questa lista collegata non compilata

    
risposta data 06.10.2011 - 12:41
fonte
1

Puoi soddisfare entrambi i requisiti modellando le rotte come array. In un RDBMS, potresti impostare una tabella come questa: 

-- Table "route_steps"
id         NUMERIC   -- ID for this row
route      NUMERIC   -- FK:  Which route?
position   NUMERIC   -- Relative position of this step in the route
node       NUMERIC   -- FK:  Which node?

L'inserimento di un passo nel percorso verrà eseguito da INSERT in una nuova riga e con un BEFORE trigger incrementa il position in tutte le righe con un position maggiore o uguale a quello della nuova riga . La cancellazione sarebbe l'opposto: DELETE la riga che contiene il passaggio che vuoi eliminare e avere un AFTER trigger decrementa il position di qualsiasi passo nella stessa rotta con un position maggiore rispetto a quello appena eliminato. Poiché tutto ciò accade in una transazione, l'intera operazione diventa atomica.

L'accesso casuale diventa una riga da route_steps di position : 

SELECT node FROM route_steps
  WHERE route = id_of_route_of_interest
  AND position = position_of_interest

L'intero percorso può essere recuperato in sequenza con: 

SELECT position, node FROM route_steps
  WHERE route = id_of_route_of_interest
  ORDER BY position ASC

L'indicizzazione corretta renderà entrambe queste operazioni molto veloci e aiuterà anche il UPDATE s eseguito dai trigger INSERT e DELETE a trovare le righe che devono essere aggiornate.

Ci sono alcuni problemi di integrità che dovrai gestire, ma una volta che avrai acquisito più di una caviglia, probabilmente scoprirai di cosa si tratta.

Personalmente, non riesco a vedere alcun rialzo in un modello ibrido. Dovrai comunque mantenere qualcosa simile a un array per accelerare l'accesso casuale usando i metodi descritti sopra. Con quello già in atto, non sembra esserci molto da fare nello svolgere il lavoro aggiuntivo di mantenere l'elenco collegato solo perché è efficiente.

    
risposta data 06.10.2011 - 14:34
fonte
0

Vorrei dare un'occhiata a Boost.graph per far fronte a questo. Può sembrare eccessivo a prima vista, ma a lungo termine dovresti vedere sempre più benefici.

    
risposta data 06.10.2011 - 11:54
fonte

Leggi altre domande sui tag

ASP.Net MVC metodi di azione ambigui - perché il percorso scelto VPN o TLSv1 per la protezione di un protocollo di programmi dal dispositivo di campo al mainframe