View Full Version : (JAVA) Realizzare stack con complessita' O(1)...
Salve a tutti!
Ho scritto una classe Stack (relizzato con un array) ma nel farlo ho tralasciato un particolare: tutte le funzioni devono avere complessita' costante O(1).
Si tratta di:
push(Object);
pop();
top();
isEmpty();
reverse();
Per le prime 4 credo si possa fare con un campo dati che indica la posizione del prossimo oggetto: push diventa un'assegnazione, top un return, pop un return e un'assegnazione. isEmpty e' gia' O(1).
Il problema ce l'ho con reverse, che inverte a specchio tutti gli elementi dello stack :(
Questo non saprei farlo senza un for che mi fa salire la complessita' ad O(n).
Qualche idea?
Grazie in anticipo! :muro:
A naso direi che basti assegnare al riferimento (indice nel caso di un array) che punta al nodo di inserimento-estrazione il valore del nodo opposto. Il che è più o meno complicato a seconda di come hai realizzato i nodi perchè può richiedere un mutamento nel modo in cui ora realizzi le operazioni pop-peek-push, ferma la complessità O(1).
potresti tenerti un flag che indica se l'array è reversed oppure no, ma il problema è che se fai un push all'array reversed non hai spazio... potresti fare un array gestito "a ciclo": se l'array è di N locazioni, un "reversed push" oltre la 0 causa una scrittura alla N-1. ma ovviamente devi conoscere in anticipo la dimensione massima dello stack.
se non ha spazio può espandere l'array, è pesante ma sempre O(1).
se non ha spazio può espandere l'array, è pesante ma sempre O(1). se espande l'array ottiene delle locazioni oltre la fine, ma se non ha spazio per fare il push reversed lo spazio che gli manca non è alla fine, è all'inizio (gli servirebbero locazioni prima dello 0). potrebbe ottenere le locazioni alla fine e fare la gestione ciclica in effetti, ma è inutile perché per realizzare tutti gli algoritmi in O(1) la dimensione massima dello stack deve essere nota a priori, altrimenti (assumendo di gestire l'array ciclico) si presenta il seguente problema: ho N locazioni da 0 a N-1, faccio K push "in avanti", metto il flag di reverse, e faccio N-K push all'indietro; ho riempito tutto l'array. ora che succede se faccio un altro push? altre locazioni la posso ottenere solo alla fine dell'array, ma non è lì che voglio mettere il mio nuovo elemento...
doublelinkedlist, un puntatore all'ultimo elemento inserito, un puntatore al primo elemento inserito(per la reverse), un booleano per la direzione(e per capire se quando fai pop poi devi usare il prev o il succ, uguale per la push)
naturlamente devi gestire la doublelinkedlist, oppure usarne una gia fatta.
ps.cosi a sentimento eh, potrebbe essere una castroneria :asd:
infatti così funziona, ma io avevo capito che il realizzare lo stack utilizzando un array era un requisito... :huh:
infatti così funziona, ma io avevo capito che il realizzare lo stack utilizzando un array era un requisito... :huh:
dal post non sembra un requisito
ps.scusate la niubbaggine, ma sono a digiuno di c & company da molto....ma come si espande un array?
Grazie ragazzi! :)
Desidero aggiungere qualche informazione al mio precedente post:
Nessuna (double)linked list, lo stack è gestito con un Array di Object classico
Se riempio l'array, in automatico viene chiamato il metodo espandi() che duplica la dimensione dell'array e copia gli elementi (questo metodo non deve essere O(1))
Nessuna gestione dell'Array a ciclo
PGI-Bis
se non ha spazio può espandere l'array, è pesante ma sempre O(1).
Come faccio ad espandere l'array in O(1)? La copia degli elementi dal vecchio al nuovo non mi spara la complessità ad O(n)?
71104
se espande l'array ottiene delle locazioni oltre la fine, ma se non ha spazio per fare il push reversed lo spazio che gli manca non è alla fine, è all'inizio (gli servirebbero locazioni prima dello 0). potrebbe ottenere le locazioni alla fine e fare la gestione ciclica in effetti, ma è inutile perché per realizzare tutti gli algoritmi in O(1) la dimensione massima dello stack deve essere nota a priori, altrimenti (assumendo di gestire l'array ciclico) si presenta il seguente problema: ho N locazioni da 0 a N-1, faccio K push "in avanti", metto il flag di reverse, e faccio N-K push all'indietro; ho riempito tutto l'array. ora che succede se faccio un altro push? altre locazioni la posso ottenere solo alla fine dell'array, ma non è lì che voglio mettere il mio nuovo elemento...
Hai centrato il punto! :)
Idea: e se ad ogni push e pop al posto di mettere e togliere da un solo array metto e tolgo da 2 array distinti? Uno ovviamente è gestito "al contrario" del seconddo. Così facendo la reverse non fa altro che cambiare i due riferiementi... che ne dite?
Come faccio ad espandere l'array in O(1)? La copia degli elementi dal vecchio al nuovo non mi spara la complessità ad O(n)? se in C usi la realloc è improbabile che il blocco debba essere spostato e quindi ricopiato, ma tu stai usando new quindi si, è O(n) perché lo devi ricopiare.
Idea: e se ad ogni push e pop al posto di mettere e togliere da un solo array metto e tolgo da 2 array distinti? Uno ovviamente è gestito "al contrario" del seconddo. Così facendo la reverse non fa altro che cambiare i due riferiementi... che ne dite? ottima idea... :wtf: non ci avevo pensato! :D
non serve neanche che li "gestisci al contrario" come dici tu, basta che siano due!!
supponi di avere due array, A e B, e di conoscerli tramite i rispettivi puntatori *A e *B:
push aggiunge un elemento all'array puntato da *A (lo esapnde se necessario)
pop leva un elemento dall'array puntato da *A
reverse scambia i valori di *A e *B
fine :|
è geniale!! :D
si però utilizzi il doppio della memoria :asd:
certo che però funziona e ti tieni l'O(1) :)
Certo, utilizzo il doppio della memoria ma mi rimane O(1), che è il mio scopo finale :cool:
Grazie ragazzi :cincin:
Per espandere l'array crei un nuovo array più grande e usi System.arraycopy per trasferire il blocco di memoria rappresentato dal vecchio nel nuovo, a partire da un certo offset.
si però utilizzi il doppio della memoria :asd: si ma solo nel caso pessimo: nel caso ottimale ne usi esattamente tanta quanta te ne serve. in certi casi può risultare meglio della lista doppiamente linkata, dove ne usi sempre e comunque di più :Prrr:
Perchè solo nel caso pessimo? A me sembra che sia sempre il doppio come dice thebol.
Perchè solo nel caso pessimo? A me sembra che sia sempre il doppio come dice thebol. no: è il doppio (anzi per l'esattezza il doppio meno 1) solo quando entrambi gli array sono stati entrambi riallocati; ma se sono entrambi pieni li sfrutti al meglio.
Allora non ho capito la soluzione. Hai due array A e B:
A [ ][ ][ ][ ][ ][ ]
B [ ][ ][ ][ ][ ][ ]
push aggiunge un elemento ad A. Con due push (o segnala il cursore):
A [x][o][ ][ ][ ][ ]
B [ ][ ][ ][ ][ ][ ]
Cos'è che fa reverse ora?
Uppo, 71104: sai che noi matti siamo curiosi :D
Magari è persino meglio della soluzione ad array unico. Non farti pregare.
e sta calmo, stavo a magnà :D
hai questi:
A [x][o][ ][ ][ ][ ]
B [ ][ ][ ][ ][ ][ ]
ora se fai reverse non cambia nulla, però grazie al fatto che tu scambi i puntatori ciò che tu vedi è questo:
A [o][ ][ ][ ][ ][ ]
B [x][ ][ ][ ][ ][ ]
Allora non ho capito la soluzione. Hai due array A e B:
A [ ][ ][ ][ ][ ][ ]
B [ ][ ][ ][ ][ ][ ]
push aggiunge un elemento ad A. Con due push (o segnala il cursore):
A [x][o][ ][ ][ ][ ]
B [ ][ ][ ][ ][ ][ ]
Cos'è che fa reverse ora?
L'idea e' molto chiara se immagini di "appicicare" le basi dei due array per farne uno che abbia gli elementi che invece di partire da un lato partano dal centro.
Riscrivendo il disegno di sopra nel seguente modo:
[ ][ ][ ][ ][ ][ ] B A [ ][ ][ ][ ][ ][ ]
Forse ti sara' piu' chiaro.
Parti con A e aggiungi verso destra
-->
[ ][ ][ ][ ][ ][ ] B A [x][ ][ ][ ][ ][ ]
...
[ ][ ][ ][ ][ ][ ] B A [x][x][x][x][x][x]
Quando riempi a semplicemente espandi il doppio array verso destra
[ ][ ][ ][ ][ ][ ] B A [x][x][x][x][x][x][ ][ ][ ][ ][ ][ ]
Quando fai la reverse scambi di ruolo i due array e cominci ad aggiugnere a sinistra
<--
[ ][ ][ ][ ][x][x] B A [x][x][x][x][x][x][ ][ ][ ][ ][ ][ ]
Per gestire il caso pila vuota basta tenere un contatore.
Ok, non ho capito :D.
push Pippo:
A [Pippo][null][null][null]...
B [null][null][null]...
push Gianni e push Mario
A [Pippo][Gianni][Mario][null]
B [null][null][null]...
peek restituisce "Mario" (ultimo inserito nella pila).
Ora faccio un reverse e scambio i puntatori. Cioè se faccio peek() l'array sottostante non è più A ma B (è così?). E questo peek mi restituisce Pippo?
:fagiano: Non ci arrivo :fagiano:
Grazie marco.r, ora ho capito. Ammazza che roba complicata.
push, push, push
[ ][ ][ ][ ][ ][ ]BA[x][x][x][ ][ ][ ][ ]
reverse, push, push, push, push, push
[ ][ ][x][x][x][x]BA[x][x][x][ ][ ][ ][ ]
reverse, pop, pop, pop, pop, pop
[ ][ ][x][x][ ][ ]BA[ ][ ][ ][ ][ ][ ][ ]
reverse, push
[ ][ ][x][x][ ][ ]BA[x][ ][ ][ ][ ][ ][ ]
e mo? Se faccio due pop? O mi sono incasinato io? :huh:
[ ][ ][x][x][ ][ ]BA[ ][ ][ ][ ][ ][ ][ ]
reverse, push
[ ][ ][x][x][ ][ ]BA[x][ ][ ][ ][ ][ ][ ]
e mo? Se faccio due pop? O mi sono incasinato io? :huh:
Ad ogni momento devi tenere almeno due indici, ovvero il margine sinistro e quello destro degli elementi utilizzati. Lo zero dei due array non e' altro che un punto di riferimento. Nel caso sopra, avremo un left == 4 e un right == 3 (o 5 e 2 a seconda se indichiamo l'ultimo elemento occupato o il primo libero), per cui col push successivo (supponendo di riempire a destra) andremo a colmare il secondo elemento e right diventera' 2 (risp. 1).
[ ][ ][x][x][ ][ ]BA[ ][ ][ ][ ][ ][ ][ ]
^ ^
| |
left right
[ ][ ][x][x][x][ ]BA[ ][ ][ ][ ][ ][ ][ ]
^ ^
| |
left right
Tu immagina che "BA" non sia altro che l'origine degli assi, e la pila un verme che si muove a destra e sinistra e si accorgia e si allunga :D
Ora ti faccio un rapido prototipo in python, cosi' capisci meglio :P.
N.B.: E' chiaro che con una implementazione del genere nel caso peggiore l'occupazione di memoria cresce indefinitamente anche con pochi elementi. Visto che non sempre potro' ridurre le dimensioni degli array.
Mi pare d'aver capito. Penso che in una scala di voti da zero a trenta una cosa del genere valga trenta. Frustate. :D
import Numeric
class Pila:
def __init__(self,initial_size):
self.head = 0 # Prossima casella libera
self.tail = -1 # Casella prima della coda
A = Numeric.zeros(initial_size)
B = Numeric.zeros(initial_size)
self.other = { id(A) : B, id(B) : A }
self.size = 0
self.head_array = A
self.tail_array = A
self.direction = +1
def check_push_bounds(self):
# sforo "in alto"
if self.direction == +1 and self.head == len(self.head_array):
other_array = self.other[ id(self.head_array) ]
new_size = len(self.head_array) * 2
new_head = Numeric.resize( self.head_array, (new_size,) )
self.other = { id(new_head) : other_array, id(other_array) : new_head }
if self.tail_array == self.head_array:
self.tail_array = new_head
self.head_array = new_head
# sforo in basso, devo passare all'altro array
if self.direction == -1 and self.head == -1:
self.head_array = self.other[ id(self.head_array) ]
self.direction = 1
self.head = 0
def push(self,x):
self.check_push_bounds()
self.head_array[ self.head ] = x
self.head+= self.direction
self.size += 1
def peek(self):
if self.size == 0:
raise Exception('Empty Stack')
return self.head_array[ self.head - self.direction ]
def check_pop_bounds(self):
if self.direction == -1 and self.head == 0:
self.head_array = self.other[ id(self.head_array) ]
self.direction = 1
def pop(self):
if self.size == 0:
raise Exception('Empty Stack')
self.check_pop_bounds()
self.head -= self.direction
self.size -= 1
def reverse(self):
x = self.head
self.head = self.tail
self.tail = x
x = self.head_array
self.head_array = self.tail_array
self.tail_array = x
if self.head_array == self.tail_array:
self.direction *= -1
Codice blandamente testato che necessita di Numeric (giusto per complicarsi la vita, con le liste di python era piu' semplice, ma forse meno fedele alla richiesta iniziale). Tengo un indice head ed uno tail per indicare l'inizio e la fine del verme :D. head_array e tail_array indicano su quale array cadono testa e coda. direction indica se sto facendo crescere o calare gli indici (ovvero se il verme si allontana o si avvicina all'origine ). other indica ovviamente "l'altro" array rispetto quello specificato.
Usa un verme solo.
ArrayStack
array dati
intero cursore, coda, numeroTotaleElementi
booleano invertita
push valore
cursore = cellaSuccessiva(cursore)
dati[cursore] = valore
aumenta di 1 numeroTotaleElementi
espandi array se necessario
valore pop
valore = dati[cursore]
cursore = cellaPrecedente(cursore)
riduci di 1 numeroTotaleElementi
reverse
invertita = il contrario di invertita
scambia cursore con coda
booleano isEmpty
numeroTotaleElementi è zero?
espandi array se necessario
è necessario se numeroTotaleElementi vale quanto la dimensione di dati
crea un nuovo array più grande
se cursore - coda + 1 vale numeroTotaleElementi
copia dati nel nuovo array più grande
altrimenti
copia la parte terminale di array nel nuovo array
copia la parte iniziale di array nel nuovo array
scambia array con l'array più grande
intero cellaPrecedente indice
se è invertita, restituisce indice + 1, altrimenti indice - 1
applica all'indice restituito la condizione di circolarità di un anello
intero cellaSuccessiva indice
se è invertita, restituisce indice - 1, altrimenti indice + 1
applica all'indice restituito la condizione di circolarità di un anello
Cursore sta per il punto di ultimo inserimento che nello schema qui sotto è la testa.
push push push
coda testa
A[x][x][x][x][ ][ ][ ][ ][ ]
reverse
testa coda
A[x][x][x][x][ ][ ][ ][ ][ ]
push push push
coda testa
A[x][x][x][x][ ][ ][x][x][x]
pop, pop
coda testa
A[x][x][x][x][ ][ ][ ][ ][x]
reverse
testa coda
A[x][x][x][x][ ][ ][ ][ ][x]
quattro push
testa coda
A[x][x][x][x][x][x][x][x][ ][ ][ ][ ][ ][ ][ ][x]
Dieci a uno che il prof gli ha fatto fare gli anelli (aka array circolari) prima di rifilargli questo.
Usa un verme solo.
<cut>
Dieci a uno che il prof gli ha fatto fare gli anelli (aka array circolari) prima di rifilargli questo.
Ci avevo pensato, ma vedo un problema: che succede se riempio l'array a meta' strada ?
Supponendo di partire con array di otto elementi,
dopo la seguente sequenza
push push push push reverse push push push push
ti trovi con l'array pieno e con gli estremi che ti toccano a meta' array.
Come espandi l'array per il prossimo elemento ? Idealmente vorresti farlo "in mezzo" all'array, per aver spazio per i prossimi push.
Non mi vienei n mente una soluzione semplice.
Esattamente come hai detto, "lo apri in due come una mela". E' un anello lo espandi come tale.
La posizione del cursore ti dice dove stà "la metà" e dal suo rapporto con
la coda e il numero totale degli elementi ricavi se il cursore abbia o non abbia fatto "un giro" e in che senso l'abbia fatto.
T H
[X][X][X][X][X][X][X][X]
se H è maggiore di T e "l'array ha fatto un giro", da zero a T va in testa al nuovo array e da H a length - 1 va in coda.
se H è minore ti T da zero ad H va in testa e da T a length - 1 va in coda al nuovo.
se H è maggiore di T e "l'array non ha fatto un giro" allora copy da T ad H inclusi nel nuovo array, a partire da zero o da T se vuoi lasciare inalterati gli indici della testa e della coda.
Anzi, è più semplice:
gli elementi da zero al minore tra T ed H vengono copiati nelle posizioni da zero al minore tra T ed H nel nuovo array.
gli elementi dal maggiore tra T ed H e la lunghezza dell'array vegono copiati da
(lunghezza - Max(T, H)) a nuovoArray.length.
Più o meno uno che è tardi e non ci ho voglia di contare tanto :D
[Aggiunto] No, meglio quella di prima :coffee:
[Aggiunta all'aggiunto] Anzi, è meglio questo di adesso. Ok, vado a dormire :D
Hai ragione. Partivo dal presupposto che se devo ricopiare gli ultimi n elementi non ho piu' l'O(1), pero' in effetti quando espando un array nel caso generale devo comunque copiare i suoi elementi per cui in ogni caso ho l'O(n) ( o l'O(1) ammortizzato se preferisci )
Grazie marco.r, ora ho capito. Ammazza che roba complicata.
push, push, push
[ ][ ][ ][ ][ ][ ]BA[x][x][x][ ][ ][ ][ ]
reverse, push, push, push, push, push
[ ][ ][x][x][x][x]BA[x][x][x][ ][ ][ ][ ]
reverse, pop, pop, pop, pop, pop
[ ][ ][x][x][ ][ ]BA[ ][ ][ ][ ][ ][ ][ ]
reverse, push
[ ][ ][x][x][ ][ ]BA[x][ ][ ][ ][ ][ ][ ]
e mo? Se faccio due pop? O mi sono incasinato io? :huh: azz, è vero... :mbe: non ci avevo pensato...
allora tocca modificare così: oltre ai puntatori *A e *B aggiungiamo i due indici Left e Right: quando hanno un valore positivo indicano in *A, quando è negativo in *B. e sono 1-based e non possono mai essere 0. a questo punto:
push, se Right è negativo scrive in B[-Right-1], se è positivo scrive in A[Right-1]; incrementa Right; se necessario espande l'array.
pop, se Right è negativo legge da B[-Right-1], se è positivo da A[Right-1]; decrementa Right e se diventa nullo lo fa diventare -1
reverse, scambia *A e *B, scambia Left e Right
a proposito:
reverse, push, push, push, push, push
[ ][ ][x][x][x][x]BA[x][x][x][ ][ ][ ][ ] c'è un push di troppo :Prrr:
E se lo facciamo circolare lo stack non è più semplice ?
Basta fare push in coda nel caso sia reversed...
E se lo facciamo circolare lo stack non è più semplice ?
Basta fare push in coda nel caso sia reversed...
Appunto.
Per l'espansione me n'è venuta un'altra, ancora più facile.
copia da array tutti gli elementi a partire da coda fino a cursore in array più grande a partire da zero. Poi imposta coda a zero, cursore a numero di elementi meno uno e invertita a false.
E se lo facciamo circolare lo stack non è più semplice ?
Basta fare push in coda nel caso sia reversed... se ne è già parlato prima ma no, perché non si conosce la dimensione massima dello stack.
se ne è già parlato prima ma no, perché non si conosce la dimensione massima dello stack.
E questo sarebbe di un qualche impedimento?
se ne è già parlato prima ma no, perché non si conosce la dimensione massima dello stack.
Se devi implementarlo con un vettore bene o male la conosci la dimensione massima, per l'espansione automatica a stack pieno (che si è detto non deve essere O(1)) si usa l'algoritmo che ha detto sopra PGI-bis...
per l'espansione automatica a stack pieno (che si è detto non deve essere O(1)) ah è vero :p
copia da array tutti gli elementi a partire da coda fino a cursore in array più grande a partire da zero. Poi imposta coda a zero, cursore a numero di elementi meno uno e invertita a false.
O semplicemente si estraggono gli elementi con la pop fino a svuotarlo e dopo si inseriscono all'inizio del nuovo vettore (o dall'elemento uno fino all'N-1, in tal caso si fa uno stack reversed, o dall'elemento N-1 fino allo zero, e si impostano di conseguenza i due puntatori alla testa e alla coda)...
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.