(java) problemi ridimensionamento code

[aduri]

L'argomento ridimensionamento code purtroppo non mi e' chiaro.

public void enqueue(Object el) { 
if (isFull()) 
doubleQueue(); 
protected void doubleQueue(){ 
Object[] newdata = new Object[2*size]; 
for(int i=first, j=0; j<size; j++, i++,i=i%size){ 
newdata[j] = data[i]; 
} 
first=0; 
last=size-1; 
size=2*size; 
data=newdata; 
} 

public Object dequeue() { 
int elem; 
if (first<=last) 
elem=last-first+1; 
else 
elem=size-first+last+1; 
if (( elem<size/4) && (elem>=s_size/4)) 
halfQueue(elem); 
...... 

protected void halfQueue(int elem){ 
Object[] newdata = new Object[size/2]; 
for(int i=first, j=0; j<elem; j++, 
i++,i=i%size ){ 
newdata[j] = data[i]; 
} 
first=0; 
last=elem-1; 
size=size/2; 
data=newdata; 
}

Se non ho capito male il primo metodo enqueue(Object el) verifica se l'array e' pieno e se si'
ne raddoppia la taglia caricando i dati sul nuovo array.(anche se non capisco i=%size)
Nella seconda parte che descrive i metodi dequeue() e halfqueue(int el) non capisco i controlli di size e s_size cosa facciano.
Ho capito come calcola elem sia nel caso che first sis prima di last che viceversa ma dopo mi perdo

[Dav82]

Dopo aver calcolato elem, si controlla se l'array è troppo vuoto, e nel caso ne si dimezza la grandezza tramite il metodo halfqueue (che in pratica fa la cosa opposta del doublequeue). In sostanza sembra venga usato un meccanismo di "bilanciamento" come negli alberi di ricerca.


Il controllo su size serve a verificare se la quantità di dati presenti è troppo inferiore alle capacità del container, determinando uno spreco di memoria. Occhio che la condizione è diversa da quella inversa prevista per il raddoppio della capacità, per evitare di raddoppiare/dimezzare ogni volta la capacità (operazione onerosa) se alternatamente si toglie/aggiunge sempre un elemento che determina il cambiamento di capacità. (tipo: ho 12 elementi, arriva il 13° e la condizione mi dice che devo raddoppiare, poi ne tolgo uno e la condizione mi dice che devo dimezzare etc: con le condizioni poste questo eccesso computazionale non si verifica)

Quel s_size sinceramente non saprei... servirebbe che postassi tutto il codice, in modo da capire bene... (se magari ci sono pure dei commenti al codice tanto meglio )


Anzi, con una rapida ricerca con San Google ho trovato (penso) le slide a cui ti riferisci

Viene detto che s_size è la dimensione iniziale della coda, e il controllo (su s_size/4) serve a non scendere mai sotto la dimensione iniziale della coda... mh Non so, non è che mi sia chiarissma la cosa, perchè se fosse esattamente così, il controllo non dovrebbe avere quel "/4".
Cmq, il succo del discorso è che non si reputa utile avere una coda con troppi pochi posti disponibili, che in buona sostanza vuol dire: se ho una coda con (per dire) 10 posti ed è troppo vuota e quindi dovrei dimezzarla, val la pena di invocare un metodo, fare tutti quei conti per risparimiare (sempre per dire) 5 sole posizioni e quindi ben pochi byte in memoria? Forse no. Penso che la motivazione sia questa

Per il i = i%size la spiegazione è questa: non è detto, anzi in generale è falso, che il primo elemento dell'array sia il primo elemento "in coda". Il primo elemento in coda è quello indicato dalla variabile first (che funziona in pratica da "puntatore"), così come l'ultimo è quello indicato da last (se questa variabile è presente). Questo perchè? Perchè se anche all'inizio, quando la coda è vuota, si riempie l'array a partire dalla prima posizione, quando il primo elemento viene tolto dalla coda, il primo nella coda diventa l'elemento che sta nel posto successivo, che non è più il primo. Andando di questo passo e riempiendo la coda e togliendo elementi dall'inizio, può essere che il primo nella coda sia negli ultimi posti dell'array e che i primi posti dell'array siano di quelli ultimi nella coda. Qua sotto c'è un disegnino al volo che esemplifica il tutto.

Inserisco 1, inserisco 2, tolgo 1, inserisco 3, inserisco 4, tolgo 2, inserisco 5: il 5 devo metterlo nel primo posto dell'array, benché non sia il primo nella coda.



(lo sfondo verde indica il primo elemento nella coda)


Quando si procede al ridimensionamento dell'array, si "ricompatta" la struttura, e per questo si riempie il nuovo array (indicizzato con j) dalla prima posizione: si parte dal primo elemento in coda nel vecchio array (il primo in coda, non come posizione nell'array!), usando l'indice i, e si incrementa i mano a mano... però può essere che i vada oltre la dimensione dell'array e si debba ripartire da capo. L'operazione col "%" (modulo) serve appunto in questo caso: finché i è minore di size, il resto della divisione è pari a i stesso, e quindi nulla succede, se invece i è maggiore o uguale a size, allora i viene posto a 0 (p. es: 8 % 8 = 0) e si ricomincia da capo.


Ciao