[Java] Interi su array di booleani: il programma va in errore con numeri grandi

[valereds]

ciao a tutti..

devo fare un programma che gestisce un insieme di numeri interi positivi..attraverso un ARRAY DI BOOLEANI dinamico..

implementando i due metodi put(int) e remove(int)..però ho riscontrato qlk problemino...infatti inserendo numeri parecchio grandi il mio programma va in crash in quanto viene lanciata l'eccezione OutOfMemoryError ...

private boolean[] b;   //questa è la mia variabile per la struttura 
private int n; //serve per contare gli elementi dell'insieme


//il metodo put() che ho scritto io
public boolean put(int s){
		
		if(s<0) throw new IllegalArgumentException("Intero negativo!");
		
		if(s>=b.length) {
			allunga(s);
			set[x]=true;
                        n++;
			return true;
		}
		if(set[s]) return false;
		else{
		set[s]=true;
		n++;
		return true;
		}

//Metodo che aumenta la capacita' dell'array
	private void aumenta(int last) {
		boolean[] b1 = new boolean[last+1];
		System.arraycopy(b, 0, b1, 0, b.length);
		b=b1;
	}

ora quando provo ad inserire un numero mooolto grande..mi si crasha tutto..

suggerimenti?? grazie

[andbin]

Originariamente inviato da valereds
ora quando provo ad inserire un numero mooolto grande..mi si crasha tutto..

Più il numero è grande ..... più l'array è grande!! Quale numero hai messo??? Ma sopratutto sai che la JVM tipicamente ha un limite massimo (modificabile) preimpostato del heap???

[LeleFT]

Suggerisco una lettura del regolamento, in riferimento a questi punti:

1) Il titolo della discussione deve essere chiaro e dare un'idea del contenuto
2) Il codice va postato indentato all'interno degli appositi tag CODE

Sistemo io.


Ciao.

[valereds]

ho provato ad inserire 100milioni ... 200milioni... ed il programma gira lentissimo...
se poi inserisco tipo 800milioni..il programma stoppa..

su eclipse ho impostato il limite di 1 giga di ram..(cosi come è la ram della mia macchina)

[andbin]

Originariamente inviato da valereds
ho provato ad inserire 100milioni ... 200milioni... ed il programma gira lentissimo...
se poi inserisco tipo 800milioni..il programma stoppa..

su eclipse ho impostato il limite di 1 giga di ram..(cosi come è la ram della mia macchina)

Il problema non è solo l'hardware della macchina (ovviamente la memoria installata conta) .... ma anche il fatto che il "heap" di memoria della JVM ha un limite massimo (impostabile tramite una opzione non standard del comando 'java').

Ma a parte tutto questo .... di che ti stupisci??? Allochi un array enorme ..... e non solo: quando espandi ne allochi un altro solo di 1 più grande. Quindi occupi (anche se temporaneamente) il doppio del necessario!

[valereds]

hai ragionissimo..non mi sn stupito del risultato perchè è giusto che sia cosi per il modo in cui sto gestendo la cosa
...però non mi è venuto (per ora) in mente ancora nulla di piu elegante e efficiente..se provo con int = 700milioni..il programma gira alla fine però è super mega lento..quindi credo ci sia un modo per non creshare testandolo all'intero che serve a me..

[andbin]

Originariamente inviato da valereds
...però non mi è venuto (per ora) in mente ancora nulla di piu elegante e efficiente..

Qualcosa di migliore e più efficiente si può fare.
Si possono usare i bit-field, ovvero usi un array di byte in cui ognuno degli 8 bit del byte rappresenta un flag "booleano" che interessa a te. Ovviamente devi fare della "aritmetica" per raggiungere il byte e il bit voluto!

Questo però non centra con il problema della espansione ... riduce solo di 8 volte il consumo della memoria. Se non vuoi dover istanziare ogni volta che è necessario un array di poco più grande, si possono usare altri metodi. Uno ad esempio è quello di non usare un array "lineare" ma una struttura di array a più livelli.

[taigasuki]

Caro Vale, credo che implementare un insieme di numeri utilizzando solo un array di booleani dinamico, senza l'aiuto di strutture d'appoggio, ti sia praticamente impossibile.
A mio modo di vedere i casi sono due: o rischi di rendere la computazione lunghissima o finisci la memoria. Mi spiego...
Se riallochi l'array quando rimuovi l'elemento più grande (nomearray.length-1), della lunghezza del secondo elemento più grande, risparmi memoria pagando però il costo dell'allocazione. Se allochi un array da 800milioni di elementi un po' ci mette, e se fai allocazioni e rimozioni in serie di un valore così alto come test, il tuo pc avrà da fare per molto tempo...
Se invece, ogni volta che inserisci un elemento maggiore della lunghezza dell'array, ne allochi uno nuovo, senza però allocarne uno più piccolo quando rimuovi l'elemento maggiore, arriverai ad un punto in cui la memoria ti finisce e il programma terminerà con un'eccezione di memoria heap terminata.
Siccome il programma di test che ti hanno fornito fa per un milione di volte l'inserimento e la rimozione del numero 800milioni, se ad ogni rimozione allochi un array più piccolo per poi riallocare quello da 800milioni durante l'inserimento, non finisci più. Però non puoi nemmeno lasciare l'array allocato, perchè un test successivo di quel programma si crea un array di 100mila insiemi, inizializza il primo insieme con il numero 10, e inserisce a quelli successivi il max del precedente+1, cioè fino a 100010. Ovviamente la memoria non basta. Perciò chiedi al professor R cos'altro puoi usare oltre all'array di booleani (dato che se nn ricordo male non puoi usare strutture della API di Java).
Facci sapere... Ciao.