[JAVA] Strutture dati efficienti in spazio

[camellight]

Salve,

ho notato con molto rammarico che le strutture dati di java.util non sono affatto efficienti in spazio. Ad esempio per

List<Integer> L = new ArrayList<Integer>();

for(int i=0;i<10000000;i++)
L.add(i);

10 milioni di interi allocati in questo modo ho un consumo di memoria (secondo il windows task manager) totale di 420mb. Utilizzando invece gli array:

int L[] = new int[10000000]; 		 		
for(int i=0;i<10000000;i++) 			
L[i]=i;

il cosumo scende a 46mb che considerando quanto effettivamente occupano gli interi (che sono a 32bit) più altre informazioni conservate eventualmente dalla jvm fanno un costo praticamente pari a quello atteso...

La situazione non migliora con Vector e peggiora di molto con LinkedList...qualcuno ha qualche spiegazione in merito? Considerando che ho un problema in cui ho a che fare con qualcosa nell'ordine delle centinaia di milioni di interi, e che ho bisogno di strutture dati per la loro gestione, mi trovo alquanto in difficoltà!

[andbin]

Originariamente inviato da camellight

List<Integer> L = new ArrayList<Integer>();

for(int i=0;i<10000000;i++)
L.add(i);

int L[] = new int[10000000]; 		 		
for(int i=0;i<10000000;i++) 			
L[i]=i;

Attenzione, c'è una importante differenza tra i due casi. Le collezioni contengono oggetti, non tipi primitivi.
ArrayList è basato internamente su un array di tipo reference gestito per così dire a "espansione di capacità" cioè in un certo momento la capacità fisica dell'array interno potrebbe essere ben maggiore del numero logico degli elementi.

Ma in sostanza c'è un array di riferimenti ad oggetti. E nel primo caso sopra, sebbene un Integer abbia come unico "stato" il int primitivo, comunque occupa altra memoria per via di come la JVM gestisce gli oggetti.

Nel tuo secondo caso, l'array è di int primitivi, che sono tutti allocati uno a fianco all'altro in modo contiguo e compatto.

Originariamente inviato da camellight
La situazione non migliora con Vector

Vector è il "fratello più vecchio" di ArrayList.

Originariamente inviato da camellight
e peggiora di molto con LinkedList

LinkedList è una lista internamente gestita come doppiamente-linkata fatta di nodi interni che hanno il riferimento all'oggetto i-esimo ma anche 2 riferimenti uno al nodo precedente, l'altro al successivo. E pure questo consuma ovviamente memoria, oltre al fatto che è davvero poco performante per un accesso "casuale".

[camellight]

Innanzitutto ti ringrazio per la risposta,

per quanto riguarda la capacità effettiva e quella attuale sono ovviamente d'accordo: immagino che ArrayList utilizzi una strategia simile a quella del raddoppio per mantenere una complessità costante su n inserimenti, ed in effetti utilizzando:

List<Integer> 
L = new ArrayList<Integer>(10000000); 		 		
for(int i=0;i<10000000;i++) 			
L.add(i);

quindi allocando esattamente i 10 milioni di interi le cose "migliorano" se così si può dire (340mb!).
Anche considerando che ArrayList usa un array di riferimenti ad oggetti a me non sembra assolutamente normale che per ogni intero inserito si paghi 10 volte il costo dell'intero stesso...esiste qualche struttura dati più efficiente in tal senso ? O qualcuno ha qualche idea su come posso risolvere il problema ? Ripeto, mi servirebbe una struttura dati che scali in maniera ottima su una mole di dati (principalmente interi) nell'ordine delle centinaia di milioni

[andbin]

Originariamente inviato da camellight
per quanto riguarda la capacità effettiva e quella attuale sono ovviamente d'accordo: immagino che ArrayList utilizzi una strategia simile a quella del raddoppio per mantenere una complessità costante su n inserimenti

Di serie, Vector espande di 2 volte, ArrayList di 1,5 volte.
Solo per Vector è possibile specificare un capacityIncrement ad uno dei costruttori (altrimenti è come detto sopra).

Originariamente inviato da camellight
a me non sembra assolutamente normale che per ogni intero inserito si paghi 10 volte il costo dell'intero stesso...

Ripeto: quello che metti nel ArrayList è un oggetto non un tipo primitivo.

Originariamente inviato da camellight
esiste qualche struttura dati più efficiente in tal senso ? O qualcuno ha qualche idea su come posso risolvere il problema ? Ripeto, mi servirebbe una struttura dati che scali in maniera ottima su una mole di dati (principalmente interi) nell'ordine delle centinaia di milioni

Allora cerca una libreria che fornisca una classe es. IntArray, concettualmente simile ad ArrayList (mutabile, espandibile) ma che sia basata internamente su un array int[].
E ce ne sono sicuramente svariate. Ad esempio la Apache Commons Primitives ha una classe ArrayIntList (vedi suo javadoc dalla home indicata).

Oppure se hai tempo/voglia/capacità puoi implementarla tu. Fare una classe del genere (che magari non centra nemmeno nulla con il Collections Framework di Java) è tutto sommato fattibile e senza troppe grane.

[vincent87]

Originariamente inviato da camellight
Innanzitutto ti ringrazio per la risposta,

per quanto riguarda la capacità effettiva e quella attuale sono ovviamente d'accordo: immagino che ArrayList utilizzi una strategia simile a quella del raddoppio per mantenere una complessità costante su n inserimenti, ed in effetti utilizzando:

List<Integer> 
L = new ArrayList<Integer>(10000000); 		 		
for(int i=0;i<10000000;i++) 			
L.add(i);

quindi allocando esattamente i 10 milioni di interi le cose "migliorano" se così si può dire (340mb!).
Anche considerando che ArrayList usa un array di riferimenti ad oggetti a me non sembra assolutamente normale che per ogni intero inserito si paghi 10 volte il costo dell'intero stesso...esiste qualche struttura dati più efficiente in tal senso ? O qualcuno ha qualche idea su come posso risolvere il problema ? Ripeto, mi servirebbe una struttura dati che scali in maniera ottima su una mole di dati (principalmente interi) nell'ordine delle centinaia di milioni

Io a questo punto ti consiglio di costruirti una struttura ad hoc da solo. Ad esempio potresti simulare l'arrayList con una implementazione personale di array dinamico, magari non con la tecnica del raddoppiamento ma con quella che vuoi tu. In tal modo avresti una struttura che pesa come un array di interi, ma che occupa lo spazio che decidi tu.

[camellight]

allora,

nel creare un struttura ad hoc non ci sono grossi problemi, infatti ho gestito in maniera circolare un array con eventuali raddoppi o riduzioni di taglia quando necessario. La cosa che mi è sembrata veramente strana è il fatto di non poter utilizzare i generics dato che anche per gli interi in tal caso si sarebbero dovuti utilizzare gli Integer (eventualmente con autowrapping) facendo lievitare il costo della struttura. Allora il fatto di dover scrivere una struttura solo per gli interi mi è sembrato un pò strano (esistono comunque diverse librerie open source come "pcj" o "trove") e contrario alla programmazione orientata agli oggetti.

Il problema è appunto nel passaggio da tipi primitivi e oggetti, il modo in cui la jvm gestisce i riferimenti e alloca la memoria è sproporzionato per oggetti che contengono pochi campi (es. oggetti che hanno il valore dell'intero che rappresenta). Vale per ogni tipo di oggetto, anche per le stringhe.

Rimango comunque con dei problemi da risolvere ad esempio prima utilizzavo una mappa tra gli oggetti e alcune liste di interesse...sarà un pò difficile sostituire tali strutture ed eventualmente chiederò ancora una volta a voi qualche idea per risolvere il problema!

[andbin]

Originariamente inviato da camellight
La cosa che mi è sembrata veramente strana è il fatto di non poter utilizzare i generics

Le parametrizzazioni utilizzabili con i generics sono solo per i tipi "reference".

Originariamente inviato da camellight
Allora il fatto di dover scrivere una struttura solo per gli interi mi è sembrato un pò strano (esistono comunque diverse librerie open source come "pcj" o "trove") e contrario alla programmazione orientata agli oggetti.

Purtroppo non puoi "generalizzare" sui tipi primitivi (a meno di decidere di usare un primitivo "grande" es. double per tutto ... ma dubito che avrebbe senso in certi scenari).

D'altronde se guardi proprio la libreria che ho citato prima, essa possiede: ArrayByteList, ArrayCharList, ArrayShortList, ecc..... (tranne per boolean). Insomma hai capito bene: per ogni primitivo hanno proprio replicato la classe simil-ArrayList.
Non si può fare diversamente a questi livelli ....

[camellight]

Salve a tutti,

rieccomi dopo qualche giorno passato a provare qualche soluzione al problema:

Innanzitutto ho provato alcune librerie (tra cui quella proposta da andbin) e devo dire che ne esistono diverse, tutte più o meno simili. Poi volendo passare ad una "versione object oriented" del tutto ho trovato alcune soluzioni quali Ehcache, KyotoCabinet e simili che in pratica consentono di realizzare una Map interamente (o parzialmente) su disco in modo da avere una scalabilità limitata solo dallo spazio disponibile su disco (le Map sono di solito realizzate con hashing o con strutture BTree).

Non contento però ora vorrei provare a rappresentare tali grafi attraverso una matrice di Bitset (classe di java util) quindi attraverso una matrice di adiacenza. Ho però un problema: pur conoscendo a priori il numero dei vertici, essi non hanno come etichetta un numero, bensì una coppia di interi. Allora vorrei chiedervi come potrei fare ad associare in modo univoco gli indici per poi realizzare tale matrice? Avete qualche idea? Ci ho pensato ma non mi viene in mente niente...L'unica idea era quella di una matrice 4dimensionale ma suppongo sia una strada completamente sbagliata...

vi ringrazio per i consigli che mi avete dato finora !

[camellight]

Rieccomi qua,

come scritto nell'ultimo post ho adottato una libreria esterna che consente di memorizzare il grafo su disco. Ovviamente la lentezza dell'accesso al disco si fa sentire...per ora non sono riuscito a trovare altre vie d'uscita...se qualcuno ha qualche idea il problema rimane il seguente:

ho un enorme grafo (milioni di archi e vertici) di cui posso conoscere a priori il numero sia di vertici che di archi prima della effettiva costruzione. Di questo grafo ogni vertice è identificato da un numero (sono passato dalla coppia agli interi singoli tramite una piccola funzioncina di mapping) mentre degli archi non ho bisogno di conservare nessuna informazione, mi basta sapere che esiste l'arco tra due vertici. Gli archi sono direzionati e ci sono degli autocicli.

Ho provato ad utilizzare un array di BitSet (di java util) ma il problema è sempre lo stesso: al crescere del numero di archi e vertici il consumo di memoria diventa enorme (>1,5GB !)...

Se qualcuno ha qualche idea per la rappresentazione del grafo sono tutt'orecchi!