Newsgroup: it.comp.java
Titolo: Si può conoscere la capacità attuale di un ArrayList (tipo capacity() di un Vector)?

Come da oggetto: si può conoscere la capacità attuale di un ArrayList
(tipo capacity() di un Vector)?
Vorrei confrontare, al termine di un metodo, la capacità attuale
(capacity) di un arrayList con la dimensione effettiva (size), per
controllare se i valori che ho dichiarato inizialmente sono ottimali,
ma non so come fare. Il valore formito da Vector.capacity() non sembra
accessibile per un ArrayList. C'è un modo?

Marco ha scritto:

mmhh sembra di no.
pero' puoi sempre fare un trimToSize() per liberare la memoria non
usata.
Ciao Jack

 usata.
ho riletto bene le API dell'ArrayList.
A quanto pare non si puo' sapere la capacita' dell'ArrayList, che cmq
e' dinamica e aumenta se ce n'e' bisogno. Se quando fai un add() non
c'e' spazio il metodo alloca automaticamente della memoria (non c'e'
modo di sapere se solo per un elemento o piu').
Per eliminare l'eccedenza si usa TrimToSize().
L'unico modo (indiretto) per conoscerne la capacita' e' tramite il
costruttore o tramite il metodo ensureCapacity().
Cmq con un sitze() sai quanti elementi contiene, e quindi sai se la tua
stima iniziale era giusta, troppo alta o troppo bassa.
Ciao Jack

 ma non so come fare. 
Mah, il valore ottimale ce l'hai già, è size!

 writes:
J> Jack ha scritto:
J> metodo alloca automaticamente della memoria (non c'e' modo di
J> sapere se solo per un elemento o piu'). 
A  dire il  vero ci  si  può immaginare  come funziona  e andandosi  a
studiare un po' di teoria e guardando il comportamento don un debugger
simbolico.
A  naso  raddoppia  la  capacità,  se  non  ricordo  male  l'algoritmo
(pubblicato tra l'altro sul Comer,  Leiserson e R(?)). Non ho guardato
se riduce automaticamente la capacità quando il contenuto scende sotto
una certa soglia.
-- 
 /\           ___
/___/\_|_|\_|__|___Gian Uberto Lauri_____
  //--\| | \|  |   Integralista GNUslamico
\/                 e coltivatore diretto di Software

> Mah, il valore ottimale ce l'hai già, è size!
Sì, ma se non capisco da chi è stata chiamata la classe (sono
previsti vari punti di ingresso con diversi valori iniziali, a seconda
delle necessità ipotizzabili), non riesco a capire dove andrebbe
aumentato o diminuito il valore iniziale per aumentare l'efficienza.
Anche se devo dire che, laddove ho provato a variare tra 50 e 150 la
capacità iniziale, non ho rilevato differenze significative nei tempi
di esecuzione...
In ogni caso, sarebbe meglio una capacità iniziale uguale al valore
massimo, alla media, o è indifferente ai fini del tempo e della
memoria effettivamente impiegati?

 writes:
M> Anche se devo dire che, laddove ho provato a variare tra 50 e 150
M> la capacità iniziale, non ho rilevato differenze significative nei
M> tempi di esecuzione...
I  tempi di esecuzione  dovresti misurarli  su migliaia  di esecuzioni
probabilmente per percepire differenze sensibili.
M> In ogni caso, sarebbe meglio una capacità iniziale uguale al valore
M> massimo, alla media, o è indifferente ai fini del tempo e della
M> memoria effettivamente impiegati?
Se sai quanti saranno gli  elementi alla fine, assicurandoti subito la
dimensione  fai la  cosa, a  parer mio,  miglore:  quando ridimensiona
l'array interno a naso ricopia i dati nel nuovo array.
Dimensionarli a valor medio dovrebbe essere la cosa migliore.


 memoria effettivamente impiegati?
Lo estenderei al massimo compattandolo alla fine.
Salvo scoprire che magari stai (come si suol dire) pitturando le
scuregge alle mosche :-) ovvero stai andando a fare aggiustamenti fini
ma inapprezzabili. Se devi inserire 10000 voci, probabilmente vedi il
rallentamento se lasci il valore di default a 10, ma che tu preimposti
uno spazio di 9000 o 11000 probabilmente non ti cambia nulla.

> memoria effettivamente impiegati?
e> Lo estenderei al massimo compattandolo alla fine.
La migliore per la velocità ? Forse. Che anche quando riduci a naso
ricopi i dati.


 A  naso  raddoppia  la  capacità, 
Se ben mi ricordo una vecchia implementazione raddoppiava, ora aggiunge 
il 75%.
Chi ha voglia di controllare e dichiarare il vincitore tra Giambo e 
U_M_berto ;) ?

> A naso raddoppia la capacità,
G> Se ben mi ricordo una vecchia implementazione raddoppiava, ora
G> aggiunge il 75%.  Chi ha voglia di controllare e dichiarare il
G> vincitore tra Giambo e U_M_berto ;) ?
Se ci metti un'altra volta la M mi faccio un Giambo al forno :) :) :) :)
Scherzi a parte grazie per la precisazione.


Giambo ha scritto:

Senza andare troppo lontano, la risposta è sotto i nostri occhi, dentro 
"src.zip", quest'implementazione è della 1.5.0_10 e della 1.6.0:
     public void ensureCapacity(int minCapacity) {
	modCount++;
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
	    int newCapacity = (oldCapacity * 3)/2 + 1;
     	    if (newCapacity < minCapacity)
		newCapacity = minCapacity;
             // minCapacity is usually close to size, so this is a win:
             elementData = Arrays.copyOf(elementData, newCapacity);
	}
     }
Questo metodo che è publico viene richiamato ad ogni invocazione del 
metodo add():
     public boolean add(E e) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
     }
Volevo aggiungere che il metodo Arrays.copyOf(), si preoccupa di creare 
un nuovo array del tipo del oggetto passato (in questo caso Object[]) co 
n capacità specificata, e di effettuare una chiamata al System.arraycopy 
  () copiando un numero di elementi pari a:
	Math.min(original.length, newLength));
Diciamo che è un algoritmo fortemente ottimizzato che basa le sue 
potenzialità in System.arraycopy() che guarda caso è una chiamata nativa:
	public static native void arraycopy(Object src,  int  srcPos,
                                         Object dest, int destPos,
                                         int length);
Che dire oltre a: "Grande JAVA"!? :D
Ciao,
jRed

 writes:
j> Senza andare troppo lontano, la risposta è sotto i nostri occhi,
j> dentro "src.zip", quest'implementazione è della 1.5.0_10 e della
j> 1.6.0:
Grazie per esserti preso il tempo di andare a guardare.
j> al System.arraycopy () copiando un numero di elementi pari a:
j> Math.min(original.length, newLength));
Immaginavo che andasse a richiamare una copy "nativa".


 Immaginavo che andasse a richiamare una copy "nativa".
Già. La vera potenza della piattaforma Java in alcuni contesti sta 
proprio nel fatto di, al momento giusto, richiamare una funzione "nativa"...
A volte alcune implementazioni full-java non è che siano proprio il 
massimo, la giusta ottimizzazione si ha proprio con delle chiamate 
native di funzioni particolarmente importanti per la VM...
Copiare un array con System.arraycopy() è come farlo in C, solo con un 
piccolissimo overhead di memoria (qualche riferimento ai tuoi oggetti)...
Speriamo che in futuro le nuove release della VM inseriscano maggiori 
chiamate native per funzioni essenziali, ovviamente sempre al punto 
giusto! ;)
Ciao,
jRed

 writes:
j> Copiare un array con System.arraycopy() è come farlo in C, solo con
j> un piccolissimo overhead di memoria (qualche riferimento ai tuoi
j> oggetti)...
Questo è un  caso "limite", in quanto anche la libreria  del C va "giù
bassa" come  livello per sfruttare  al massimo le capacità  dell'HW ed
evitarne le "debolezze"  ed avere la maggior "banda  possibile" per la
comunicazione "memoria memoria".
I termini non sono precisissimi...
j> Speriamo che in futuro le nuove release della VM inseriscano
j> maggiori chiamate native per funzioni essenziali, ovviamente sempre
j> al punto giusto! ;)
Su queste cose penso che le  persone che ci hanno lavorato siano state
"abbastanza  sveglie" da fare  una buona  implementazione :),  un buon
algoritmo viene prima di una implementazione tiratissima :).


 ricopi i dati.
A naso, anche ogni volta che estende.

emmeesse ha scritto:

Senza a naso, lo fa in entrambi i casi! :P
ensureCapacity() è chiamato anche dai metodi add()!
Creandolo con la dim max si evita di far scatenare la copia dell'array 
quando vai ad aggiungere gli oggetti, e compattandolo alla fine delle 
operazioni la copia viene effettuata!
Ma a livello "basso" e quindi sarà fortemente ottimizzata! (almeno cosi 
sperano tutti...)
Ciao,
jRed

> ricopi i dati.
e> A naso, anche ogni volta che estende.
Quello era dato per scontato. Java non implementa la realloc(), che in
ogni caso non garantisce di non ricopiare i dati.
