[java] economia di spazio

[Pierock]

Salve ragazzi,
sono da un po' di tempo impegnato in un problema che comporta la risoluzione di un sistema lineare di circa 4900 equazioni in 4900 incognite.....(chi non vorrebbe trovarsi al mio posto!?)
.... va da se che, anche solo per affacciarmi ad un problema del genere, devo stare bene attento a fare economia di spazio utilizzato... oramai sogno anche la notte l'eccezione java.lang.OutOfMemoryError !!! :P

a tal proposito vi pongo un paio di domandine... senza entrare troppo nel merito...

perché se creo un array bidimensionale così definito

public static void main(String[] arg){ 
         int num =16100; 
         int[][] g = new int[num][num];
  System.out.println("...OK..."); }

va tutto per il meglio, mentre se creo un vettore con la stessa quantità di elementi

public static void main(String[] arg){ 
         int num =16100; 
         int[] g = new int[num*num];
  System.out.println("...OK..."); }

vado a rincappare nel mio caro java.lang.OutOfMemoryError ??? devo dedurre che 2 dimensioni "occupano" meno di una sola? quindi dovrei preferire questa struttura?

--- domandina veloce numero due ---- (so ke normalmente se ne pone solo una per post!)

perché se provo ad aumentare lo spazio della JVM non posso superare i 1024 mega? ... il mio pc dispone di 2giga di ram... ora, nn pretendo di utilizzarne 2048 ... però... che diamine!
e cmq questo problema rimane anche se uso un pc con 4giga di ram!
nn so... delucidatemi!
grazie mille

[andbin]

Originariamente inviato da Pierock
devo dedurre che 2 dimensioni "occupano" meno di una sola?

No, semmai proprio il contrario! In Java gli array multi-dimensionali sono semplicemente "array di array": un oggetto array principale i cui elementi sono "reference" ad altri oggetti array, ecc... in base alle dimensioni.

Quindi facendo new int[num][num] con num=16100 ci sono ben 16101 oggetti (gli array) presenti nel heap space! C'è un array principale che contiene 16100 reference ad altrettanti array che contengono ognuno una sequenza contigua di 16100 int.

Mentre con new int[num*num] c'è 1 solo array che contiene 259210000 int.

Se contiamo solo lo spazio per tutti gli int (tralasciamo un momento il fatto che nel primo caso ci sono più oggetti con dati intrinseci che occupano quindi di più del secondo caso) siamo intorno a circa 990 MByte di memoria.
Un po' tantino. Per default la JVM ha normalmente max 64 MByte o giù di lì per il heap. Quindi comunque in ogni caso devi aver impostato un heap space massimo molto più grande.

Quindi continua così .... setta un heap space massimo sensato per quello che devi fare e in base alla macchina che hai a disposizione.

Originariamente inviato da Pierock
quindi dovrei preferire questa struttura?

Il concetto da usare è una matrice bidimensionale? Allora ovviamente int[][].

Originariamente inviato da Pierock
perché se provo ad aumentare lo spazio della JVM non posso superare i 1024 mega? ... il mio pc dispone di 2giga di ram... ora, nn pretendo di utilizzarne 2048 ... però... che diamine!
e cmq questo problema rimane anche se uso un pc con 4giga di ram!

Lo spiega qui:
http://java.sun.com/docs/hotspot/Hot...#gc_heap_32bit

[Pierock]

Grazie mille andbin sei stato gentilissimo...e illuminante..!
quindi, tornando al nostro array, confermata la mia vecchia convinzione che un array bidimensionale "occupa" qualcosina in più di uno monodimensionale, il fatto che
new int[num*num] mi causi un errore, mentre int[][] g = new int[num][num] no lo devo attribuire al fatto che il primo caso, se pur occupando meno spazio, comporta la più difficoltosa pretesa che le 259210000 celle siano "contigue", mentre utilizzando due indici, questa quantità di celle viene suddivisa in 16100 settori?

Quindi comunque in ogni caso devi aver impostato un heap space massimo molto più grande.

Si Si... per cercare di lavorare con più numeri possibili ho aumentato già la dimensione dell'heap, ho impostato -Xmx1024m !! vorrei fare di più ma proprio nn me lo permette!


tornando al mio problema iniziale, (di risolvere un sistema di 4900 equazioni in altrettante incognite) sono costretto a creare delle Matrici enormi, ma fortunatamente per me, sono matrici stracolme di zeri , quindi sono convinto che la mia unica ancora di salvezza sia qualla di realizzare delle matrici sparse , tenendo traccia esclusivamente dei valori NON nulli.

avresti mica delle dritte in tal proposito??

ad esempio, dopo queste delucidazioni su vettori UNI o BI-dimensionali, ora sono portato a pensare che sarebbe difficile contenere tutti i valori non nulli in un singolo vettore, forse mi converrebbe realizzare un vettore in cui ogni cella "punti" ad un'altra???

domandina più tecnica....
superata la difficoltà della realizzazione di una matrice sparsa... qualcuno ha una vaga idea di come realizzare una fattorizzazione LU (LU decomposition) di tale matrice???
concettualmente dovrebbe essere identica all'approccio classico, ma dato che MatLab (sempre sia lodato) riesce nella fantastica impresa di fattorizzare all'istante matrici sparse di dimensioni "imbarazzanti" mi sembra di capire che utilizza un algoritmo ad Hoc !!

...spero di nn essermi dilungato troppo ! :P

[andbin]

Originariamente inviato da Pierock
lo devo attribuire al fatto che il primo caso, se pur occupando meno spazio, comporta la più difficoltosa pretesa che le 259210000 celle siano "contigue", mentre utilizzando due indici, questa quantità di celle viene suddivisa in 16100 settori?

Sì, la questione alla fin fine è questa: il fatto che 259210000 int contigui per qualche motivo (frammentazione del heap o altro) non riesce ad ottenerli.

Originariamente inviato da Pierock
Si Si... per cercare di lavorare con più numeri possibili ho aumentato già la dimensione dell'heap, ho impostato -Xmx1024m !! vorrei fare di più ma proprio nn me lo permette!

La pagina che ho linkato infatti descrive questa questione.

Originariamente inviato da Pierock
fortunatamente per me, sono matrici stracolme di zeri , quindi sono convinto che la mia unica ancora di salvezza sia qualla di realizzare delle matrici sparse , tenendo traccia esclusivamente dei valori NON nulli.

avresti mica delle dritte in tal proposito??

Se le cose stanno così, si può di certo fare qualcosa. Ma a questo punto non più con gli array. Fai una tua classe Matrice (che tra l'altro può poi fare tutte le operazioni che vuoi) che ha i metodi get/set per gestire i dati nella matrice. Ma attenzione, Matrice internamente invece di usare un array bidimensionale potrebbe usare una "map" che associa ad esempio un oggettino (anche privato, non visibile all'esterno) Cella che "modella" riga/colonna ad un oggetto Integer.
E ovviamente fai in modo da tenere solo valori non zero. Se viene settato un valore zero e prima c'era qualcosa nella mappa lo elimini. Se viene fatto un get e non c'è nella mappa, ritorni 0.
Insomma, dall'esterno sembra una normale completa matrice ma tu internamente ottimizzi la memorizzazione.

Originariamente inviato da Pierock
qualcuno ha una vaga idea di come realizzare una fattorizzazione LU (LU decomposition) di tale matrice???

Qui non ho proprio idea di cosa sia una "fattorizzazione LU" ... passo la parola a qualche guru di matematica.

[Pierock]

ti confesso che fino a 2 minuti fa nn avevo la più pallida idea di cosa fosse la classe MAP di java... ma ... googlizzando un po' , oltre ad essermi imbattuto nella mappa dell'isola di java ( ) ho letto qualcosina di utile... quindi .. ora te la butto li:

Considerando una matrice quadrata A di dimensioni m*m (m righe e m colonne)
creo la mia matrice "sparsa" come una Map , e inserisco il generico elemento non nullo A(i,j) in questo modo: (tanto per fare n esempio)

     int value = A[i][j];
     int hash = i*m+j;                       // così è facile ottenere una key univoca a partire
                                                  // da coordinate (i,j), e viceversa.
     Map sparsa = new HashMap();
     sparsa.put(hash, value);

e dici che così risolviamo il problema di occupare troppe celle contigue??
io stavo pensando invece ad esaurirmi con le LinkedList su una struttura fatta ad hoc <chiave , valore> ... ma mi sembra che la tua soluzione sia molto più elegante!!


per la fattorizzazione... confido in un guru!... altrimenti .. vedo un po' di arrangiarmi...
...inutile ribadire che ti sono grato per tutto