Newsgroup: it.comp.java
Titolo: contenitori per elementi numerosi

Ciao,
ho l'esigenza di dove gestire bean nell'ordine delle decine di
migliaia.
Usualmente non mi è mai capitata questa esigenza e me la sono cavata
benissimo con ArrayList e HashMap, a seconda dell'esigenza, ma mi
rendo conto che se sui grandi numeri un po' soffrono, e mi chiedo, tra
le numerose Collection standard fornite, quali siano le migliori per i
grandi numeri. Suggerimenti?
Grazie mille.
Anselmo

 writes:
A> Ciao, ho l'esigenza di dove gestire bean nell'ordine delle decine
A> di migliaia.
Serializzarli su un DB ?
-- 
 /\           ___
/___/\_|_|\_|__|___Gian Uberto Lauri_____
  //--\| | \|  |   Integralista GNUslamico
\/                 e coltivatore diretto di Software

 Serializzarli su un DB ?
E' proprio quello che devo fare, ma prima devo fare delle
associazioni, dei controlli logici, ecc. Premetto che devo mettere a
posto del codice non fatto da me toccando il meno possibile. Mi
sarebbe utile sapere quali delle numerose collection che java mette
adisposizione sono le più indicate, se ce ne sono.
Anselmo

> Serializzarli su un DB ?
A> E' proprio quello che devo fare, ma prima devo fare delle
A> associazioni, dei controlli logici, ecc. Premetto che devo mettere
A> a posto del codice non fatto da me toccando il meno possibile.
Temo che il meno possibile NON possa prescindere dalla serializzazione
a meno che tu non abbia TAAAAAAAAANTA memoria.
Una hashmap creata  con la dimensione ad hoc (per  non perdere tempo a
riordinarla)  potrebbe  andare bene.  Ma  devi avere  TAAAAAAAAAAAANTA
memoria...



Alla fine me la sono cavata così. Avevo da gestire due array di
oggetti creati da XMLBeans dalla lettura di due file xml
particolarmente grossi (array di circa 16000 bean). Dovevo poi, prima
di eseguire dei controlli e fare un inserimento con hibernate,
incrociare i dati e fare degli accoppiamenti tra ogni elemento del
primo file con un elemento del secondo. Tenendo i due array originali
non perdevo tempo e memoria a costruire altri contenitori, ma
l'operazione di accoppiamento era troppo lunga. Alla fine ho lasciato
la prima lista nell'array originale, la seconda l'ho riversata in una
List, dalla quale ogni volta mi faccio restituire un iterator e dalla
quale ogni volta rimuovo l'elemento trovato. Credendo che la fase
critica fosse la lettura, ho usato una LinkedList, ma ho visto che
alla fine la lettura è molto veloce (anche perché gli elementi da
accoppiare si trovano con approssimazione nella stessa posizione, e
rimuovendo gli oggetti dalla lista trovo l'elemento cercato sempre ai
primi posti) mentre la fase di scrittura della Linked è molto onerosa.
Quindi credo che banalmente al suo mosto userò un ArrayList...
Anselmo

> Integralista GNUslamico \/ e coltivatore diretto di Software
A> lunga. Alla fine ho lasciato la prima lista nell'array originale,
A> la seconda l'ho riversata in una List,
In  questo modo  la ricerca  e` sequenziale.  Se usi  una  HashMap che
indicizzi  col campo con  cui fare  incrocio, il  tempo di  accesso e`
costante.




Le collection sono *tutte* adatte ai grandi numeri.
Il problema è che le collection gestiscono i reference agli oggetti,
quindi ti garantiscono le performances relative agli accessi ma non
alla gestione della memoria.


In realtà anche gestire 16000 riferimenti non è così semplice,
soprattutto se li si vuole legati in qualche modo. Ad esempio prova ad
istanziare un array con dimensione 16000 di qualsiasi classe, e inizia
a caricarlo. All'inizio è molto veloce, ma riempito per metà inizia a
rallentare i tempi di accesso, perché evidentemente fisicamente le
porzioni di memoria per i riferimenti non sono sequenziali ma riempiti
in qualche modalità hash. Così anche riempire un hashMap con tanti
elementi credo sia faticoso. Per le liste credo dipenda, se usi una
linkedList fa un po' fatica (ma meno) perché comunque in qualche modo
logico lega ogni riferimento al successivo per rendere più veloci le
operazioni di lettura sequenziale, ma se si usa un altro tipo di lista
le operazioni di riempimento non dovrebbero degradarsi.
Anselmo

 costante.
Come ho spiegato, nel caso specifico mi aspetto di trovare l'elemento
cercato nella lista sempre ai primi posti (tenendo conto che gli
elementi trovati vengono rimossi), quindi questo tipo di ricerca
diventa il più performante. Inoltre la fase di riempimento dovrebbe
essere molto più veloce che con un hashMap.
Grazie comunque dei tuoi consigli.
Anselmo

 in qualche modalità hash. 
Quando parlo di performance di accesso mi riferisco ai metodi get/put 
quando già sono presenti i 16000 elementi. Durante il riempimento è 
essenziale evitare continui ridimensionamenti della capacità, quindi 
fornire una initial capacity adeguatamente alta e (eventualmente) un 
load factor basso. Quando invece la collection è piena è importante che 
la capacità sia minore possibile per ridurre i tempi di iterazione.

 writes:
A> In realtà anche gestire 16000 riferimenti non è così semplice,
A> soprattutto se li si vuole legati in qualche modo. Ad esempio prova
A> ad istanziare un array con dimensione 16000 di qualsiasi classe, e
A> inizia a caricarlo. All'inizio è molto veloce, ma riempito per metà
A> inizia a rallentare i tempi di accesso, perché evidentemente
A> fisicamente le porzioni di memoria per i riferimenti non sono
A> sequenziali ma riempiti in qualche modalità hash. Così anche
A> riempire un hashMap con tanti elementi credo sia faticoso.
Con 16000 oggetti la macchina comincia a 
    - richiedere memoria al sistema per aumentare lo heap
    - paginare, se la memoria fisica non basta.
Algoritmi di hash per gli array ? Ohi, ma abbiamo imparato informatica
su "Casa e Cucina" :> ?
Usare un  Array dinamico non  dimensionato per 16000  elementi provoca
delle reallocazioni degli  array sottostanti (cosa che non  fai con la
versione implementata tramite liste linkate - questo peraltro comporta
la creazione di  16000 oggetti "elemento della lista",  e qui di nuovo
abbiamo i  discorsi sulla espansione della memoria  allocata dalla JVM
per allargare lo  heap e quindi problemi di  paginazione - grind grind
grind, a quanti RPM e` il disco ? File o partizione di swap ?)
Per le  hashmap il tempo  di calcolo di  un hash e` costante  (lo deve
dare  l'oggetto, se non  usi come  chiavi classi  di libreria  con una
buona funzione già  scritta te la devi riscrivere,  non è difficile ma
nemmeno banale...). Di nuovo,  conviene creare la hashmap perchè abbia
una dimensione adeguata,  in questo caso consigliano sovradimensionata
mi  pare   del  75%  (quindi   28000  elementi),  altrementi   vai  di
riallocazioni e riordinamenti della tavola...


 cercato nella lista sempre ai primi posti
Occhio che per avere la certezza dei "primi" posti, devi usare il
listIterator, non l'iterator

 riallocazioni e riordinamenti della tavola...
Come ti ho già detto due volte, nel mio caso una lista è la scelta
migliore, supponendo che la JVM ci metta meno a leggere per 16000
volte i primi 10 elementi di un iterator ottenuto da una lista ogni
volta più piccola  (da 16000 a 1) piuttosto che di trovare il valore
associato ad una chiave tra 16000, tenendo anche conto del tempo che
ci si mette a riempire una lista di 16000 elementi piuttosto che
un'HashMap... ma in effetti non posso dire ciò con certezza. Ma a a
spanne mi sembra che deve essere così.
Anselmo

 writes:
A> ma forse era la memoria che si intasava
A> a provocare il rallentamento.
E' lei, credimi.
A> ah, mi stai dicendo che le linked list creano degli oggetti ad
A> hoc...  be', sě, in effetti č il metodo piů ovvio di creare la
A> catena...  quindi consigli di usare un'arraylist? Tanto, come
A> dicevo, il problema di lettura si č rivelato non critico...
Consiglio una linkedlist. La rimozione costa molto molto meno.



In che senso? Perché l'iterator non tiene l'ordinamento e le
listIterator sì?
Anselmo