Progettare un'implementazione efficiente di una coda di accesso casuale basata su una lista collegata

Attenzione: questo non è qualcosa che vorresti mai fare. Ma suppongo che sia nella sezione "Problemi creativi" (guardando la quarta versione non specifica di Java degli Algoritmi , sembra che potrebbe essere la domanda 1.2.38 - che rimanda al lettore al capitolo 3 per possibili soluzioni).

OK, con quello fuori mano, quali sono alcuni vincoli di base sul problema?

• Per trovare un elemento M in un elenco collegato di dimensioni N, devi cercare linearmente ogni elemento nell'elenco. Mentre M < = N, questo è ancora O (N).
• Per ridurre il runtime big-O, dobbiamo trovare un altro modo per accedere ai nodi nell'elenco.
• Un algoritmo di divisione e conquista è O (logN)
• Un array è O (1), ma se lo avessi, non avresti bisogno dell'elenco collegato.

Quindi, come dividi e vinci una lista concatenata? La risposta: ogni elemento non foglia nell'elenco contiene un altro elenco.

L0
+--L1
|  +--E0
|  +--E1
+--L2
   +--E2
   +--E3

Quindi, l'elenco di primo livello contiene due elenchi di figli e tali elenchi secondari contengono gli elementi effettivi. Abbiamo bisogno di un paio di altri vincoli:

• Qualsiasi lista L sa (1) se contiene sottoliste o elementi e (2) il numero totale di elementi detenuti da tutti i discendenti.
• Qualsiasi elenco L ha un numero limitato di bambini. In questo caso 2, ma potrebbe essere un qualsiasi numero. Questo è fondamentale per la valutazione big-O: qualsiasi insieme di operazioni che ha una dimensione fissa non dipendente da N è equivalente a O (1).

Quindi, vediamo come funziona per trovare l'elemento E2:

1. Inizia con il nodo L1, che sappiamo essere un elenco che contiene 2 elementi.
2. Poiché E2 è il terzo elemento, passa al nodo L2.
3. Sappiamo che L2 ha due figli e sono elementi, quindi possiamo restituire l'elemento E2.

Potrebbe non essere immediatamente evidente che la ricerca è un'operazione di logN. In questo caso, prendi un foglio di carta e disegna un elenco di 14 elementi.

L'aggiunta di elementi a questa lista è anche un'operazione O (logN), diversamente da una normale lista collegata (che è O (1) o O (N) a seconda che si tratti di una lista singola o doppia). Ecco come funziona:

1. Trova l'ultima sottolista discendente. Questa è di nuovo un'operazione ricorsiva (quindi logN), che per ogni elemento della lista segue il suo figlio destro.
2. Se la sottolista discendente ha solo 1 elemento, aggiungi il nuovo elemento e ricalcola le dimensioni di tutti i genitori.
3. Se la sottolista è piena, devi aggiungere un altro figlio a suo genitore; questa è anche un'operazione ricorsiva, sulla struttura degli elenchi.
4. Potrebbe essere necessario aggiungere un nuovo elemento radice, dove il figlio sinistro è la radice precedente e l'elemento giusto è il nuovo elemento.

Confuso? Ecco un passaggio per aggiungere gli elementi all'elenco mostrato sopra. Inizia con un singolo elemento, che è il figlio sinistro della radice (sto mantenendo la numerazione uguale a quella dell'elenco di 4 elementi).

L1
+-- E0

Quando aggiungiamo l'elemento successivo, possiamo memorizzarlo nel figlio destro della radice:

L1
+-- E0
+-- E1

A questo punto la nostra lista è piena, quindi dobbiamo aggiungere un altro livello. La radice originale dell'elenco è il figlio sinistro della nuova radice e aggiungiamo un altro elenco come figlio destro. Questo nuovo elenco (L2) è dove inseriamo l'elemento E2.

L
+-- L1
|   +-- E0
|   +-- E1
+-- L2
    +-- E2

Poiché un'operazione di inserimento aggiunge solo elementi alla fine della coda, è possibile implementarla facilmente ed efficientemente mantenendo un riferimento all'ultimo nodo della lista.

L'utilizzo degli array può aiutarti a ridurre il tempo necessario per accedere a un elemento casuale, ma divideranno solo questa volta di un fattore ~ costante. Quindi non riduce la complessità.

Vorrei provare un approccio basato su elenchi di accesso casuale binario disallineati . Tecnicamente, queste non sono più liste, ma alberi che rappresentano liste. Dato l'esercizio, vorrei introdurli come "liste rappresentate da nodi collegati".

La struttura dell'albero attraversato riflette le posizioni dei valori contenuti, in modo da poter convertire una posizione di valore arbitrario in una rappresentazione binaria e attraversare l'albero in base a questa rappresentazione per raggiungere / impostare il valore corrispondente al posizione specificata.

L'inserimento e il recupero del valore in una posizione particolare sono operazioni O (log n). Ancora meglio, l'inserimento e il recupero alla fine (o all'inizio) della lista sono operazioni O (1) .

Questo approccio potrebbe essere più efficiente solo per elenchi di link molto grandi che sono solo moderatamente dinamici. Se implementiamo la lista collegata usando una serie di Nodi (chiamata nodeArray), è possibile tenere traccia di tutti gli indici di nodeArray usando un secondo array int [] della lunghezza nodeArray.length * 2 (chiamato indexArray) insieme a l'int 'start' e int 'end'. Il nodeArray ha anche bisogno di un int 'listSize' che tenga traccia della lunghezza della linkedList (inizializzata a 0, incrementata se si chiama put (), decrementata se viene chiamato get ().

start è sempre l'indice della cella che contiene la testa dell'elenco collegato. end è sempre l'indice della cella dopo la coda della lista collegata. Una cella con un valore di indexArray.length tra "start" e "end" indica una cella che conteneva un indice in una cella in nodeArray, ma quel nodo è stato rimosso dal metodo get. Tutte le celle tra inizio e fine (incluso inizio indice, esclusa fine indice e celle con un valore di indexArray.length) sono tutti indici del nodeArray che compongono l'elenco collegato nell'ordine corretto.

Questo array richiede i seguenti metodi per accedervi:

1. Il metodo put, oltre a mettere un nuovo nodo contenente un valore alla fine dell'elenco collegato in nodeArray, ora deve anche inserire l'indice in cui il nuovo nodo viene inserito nel nodeArray in indexArray [fine] e incrementare 'fine' di 1.
2. Il metodo get genera un numero casuale rng tra 0 e listSize. Quindi itera su indexArray, iniziando da 'start' e passando attraverso iterazioni rng, senza contare le celle che incontra con un valore di indexArray.length - questo dovrebbe essere più veloce di iterare attraverso un normale elenco collegato basato su nodo.

Questo ha i seguenti problemi:

1. Il metodo put aumenta sempre la quantità di celle tra "inizio" e "fine" di 1 ogni volta che viene richiamata mentre nessun metodo le riduce (solo imposta una cella tra le due in indexArray.length). Questo alla fine causerà indexOutOfBoundsException, forzando l'inserimento di codice aggiuntivo che crea una nuova matrice di dimensioni doppie e quindi copiando il contenuto di tutte le celle in indexArray in questo nuovo array, ignorando tutte le celle con un valore di indexArray.length of course .
2. Dal momento che continui a scorrere un array, la complessità rimane la stessa. Quindi questo guadagna solo una certa velocità dal fatto che iterare tramite indexArray è più veloce che attraverso una normale lista collegata, ma si perde anche attraverso i metodi put e get più goffi oltre alla memoria che è necessario sacrificare per rendere indexArray.

Quindi questa soluzione potrebbe essere solo marginalmente migliore nel caso di elenchi di link enormi e sicuramente non se la dimensione di inizializzazione di indexArray sia stata scelta male.