Telefonino.net network
 
| HOMEPAGE | INDICE FORUM | REGOLAMENTO | ::. NEI PREFERITI .:: | RSS Forum | RSS News | NEWS web | NEWS software |
| PUBBLICITA' | | ARTICOLI | WIN XP | VISTA | WIN 7 | REGISTRI | SOFTWARE | MANUALI | RECENSIONI | LINUX | HUMOR | HARDWARE | DOWNLOAD | | CERCA nel FORUM » |

Torna indietro   WinTricks Forum > Software > Programmazione

Notices

Rispondi
 
Strumenti discussione
Vecchio 28-10-2006, 23.37.15   #1
aduri
Newbie
 
Registrato: 23-08-2006
Messaggi: 22
aduri promette bene
(java) problemi ridimensionamento code

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

Codice:
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
aduri non è collegato   Rispondi citando
Vecchio 29-10-2006, 02.23.49   #2
Dav82
Gold Member
Top Poster
 
Registrato: 18-07-2002
Messaggi: 6.399
Dav82 promette bene
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
Dav82 non è collegato   Rispondi citando
Rispondi


Utenti attualmente attivi che stanno leggendo questa discussione: 1 (0 utenti e 1 ospiti)
 
Strumenti discussione

Regole di scrittura
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is ON
Gli smilies sono ON
[IMG] è ON
Il codice HTML è OFF

Vai al forum

Discussioni simili
Discussione Autore discussione Forum Risposte Ultimo messaggio
Per la felicita di Dav82...JAVA!! Downloader Programmazione 65 29-06-2005 01.22.52
problemi con floppy - penna usb - lettore cd Alberto.m Windows 7/Vista/XP/ 2003 2 07-02-2005 14.41.54
problemi jvm e xp home Tartarughoz Windows 7/Vista/XP/ 2003 3 26-10-2004 15.19.05
SUN: DISPONIBILE JAVA STUDIO CREATOR Giorgius Programmazione 0 09-07-2004 13.07.46
Problema con java PRIMO Windows 7/Vista/XP/ 2003 4 20-04-2004 00.35.55

Orario GMT +2. Ora sono le: 21.41.10.


E' vietata la riproduzione, anche solo in parte, di contenuti e grafica.
Copyright © 1999-2017 Edizioni Master S.p.A. p.iva: 02105820787 • Tutti i diritti sono riservati
L'editore NON si assume nessuna responsabilità dei contenuti pubblicati sul forum in quanto redatti direttamente dagli utenti.
Questi ultimi sono responsabili dei contenuti da loro riportati nelle discussioni del forum
Powered by vBulletin - 2010 Copyright © Jelsoft Enterprises Limited.