maschere di bit e boolean

[AF.D.O.C]

E' possibile utilizzare una maschera di bit su un'array di booleani???


Grazieee!!

[andbin]

Originariamente inviato da AF.D.O.C
E' possibile utilizzare una maschera di bit su un'array di booleani???

Detto così non vuol dire nulla .... e quindi dovresti chiarire.
E tuttavia aggiungo che i "bit" li puoi manipolare solo sui tipi di dato interi (byte, char, short, int, long) mentre il tipo boolean è tutta un'altra cosa.

[AF.D.O.C]

Ho un'array di booleani dove devo inserire 1000000000 di elementi.
Se aumento la dimensione dell'array utilizzando la copia dopo un pò mi lancia eccezione di heap pieno.
Quindi pensavo di utilizzare un'altra implementazione lavorando sui bit (come appunto posso fare per gli interi) però appunto sò che la dimensione di un booleano dipende dalla jvm...

Era un'idea per un'altro tipo di implementazione...non saprei come risolvere il problema.

Grazie!

[andbin]

Originariamente inviato da AF.D.O.C
Quindi pensavo di utilizzare un'altra implementazione lavorando sui bit

Se la tua intenzione è quella di realizzare una classe che "modella" un array di boolean però implementata internamente con l'accesso ai singoli bit in un array di "parole" (di un certo tipo intero), puoi benissimo farlo. Tra l'altro è proprio la cosa che fa java.util.BitSet!!

BitSet ha un campo:
private long[] words;

Se il BitSet contiene 256 bit, il campo words referenzia un array di 4 long (4*64=256) e quindi accede poi ai singoli bit. E chiaramente "nasconde" questa dettaglio, in quanto BitSet ti "espone" poi dei boolean con: boolean get(int bitIndex) / void set(int bitIndex, boolean value) ecc...

Originariamente inviato da AF.D.O.C
però appunto sò che la dimensione di un booleano dipende dalla jvm...

Vero. E per la JVM Sun, per quanto so, usa 1 byte per 1 boolean.

[AF.D.O.C]

Il problema è che posso usare solo un'array di booleani (è un progetto didattico che appunto vuole più o meno simulare la classe BitSet di java!).

Se faccio come dici te vado fuori specifica!

[andbin]

Originariamente inviato da AF.D.O.C
Il problema è che posso usare solo un'array di booleani

E allora scusa .... quale è il dubbio? Usa un boolean[]. E qualunque cosa tu intenda fare come operazioni (set, get, AND, OR ecc...) ovviamente la devi implementare appositamente. Es. se fai una tua classe MyBitSet (con internamente un boolean[]) e vuoi che un bitset possa essere messo in "AND" (mascheramento) con un altro e restituire un nuovo bitset (o alterare il primo) con il risultato .... non vedo problemi. Due boolean possono essere messi in AND: bout = b1 & b2;

[AF.D.O.C]

Mi sono informata un pò meglio.
La miglior tecnica per implementare un bitSet sarebbe appunto usare una maschera di bit.
Ma è quello che non vuole perchè vuole vedere quanto siamo bravi a implementare un'array di booleani e gestire la memoria.
Ovvero: se inserisco 1000000000 di elementi in un'array di booleani nel modo più classico possibile ad un certo punto ci sarà eccezione dello heap, perchè troppo pieno.
Il trucco stà nel riuscire a inserire questi elementi in un'array di booleani senza lanciare eccezione.

[andbin]

Originariamente inviato da AF.D.O.C
Ovvero: se inserisco 1000000000 di elementi in un'array di booleani nel modo più classico possibile ad un certo punto ci sarà eccezione dello heap

Innanzitutto c'è il problema "materiale" della dimensione del heap. Per default tipicamente è di 64 MB (o giù di lì a seconda forse della versione di Java). Come ho già detto, perlomeno nella JVM della Sun 1 boolean occupa 1 byte, quindi se chiedi di istanziare un array di 1000000000 boolean, puoi usare qualunque tecnica/sistema/classe tu voglia ma con un heap massimo al default di 64 MB non ci cavi un bel niente.

Quindi per prima cosa: bisogna aumentare la dimensione massima del heap. E questo si può fare con la opzione -XmxNNN dell'eseguibile java (nota: -Xmx è una opzione non standard). Vedere documentazione Sun.

1000000000 vuol dire 1 miliardo .... quindi un bel heap e ci vuole anche una certa memoria fisica installata.

Originariamente inviato da AF.D.O.C
Il trucco stà nel riuscire a inserire questi elementi in un'array di booleani senza lanciare eccezione.

Innanzitutto non c'è alcun "trucco". A patto di poter espandere l'heap a sufficienza, nessuno ti vieta poi di istanziare un array di 1 miliardo di boolean.

Semmai la questione è un'altra e sbuca fuori nel caso tu voglia ridimensionare l'array. Hai un array di 10000 boolean e vuoi aggiungerne altri 100. Gli array, una volta istanziati, non si ridimensionano!! Devi per forza istanziare un altro array di es. 10100 boolean e poi ricopiare i 10000 originali nel nuovo array, quindi "perdere" il riferimento all'array vecchio e tenere solo il riferimento al nuovo array.
Quale è il problema? Mi pare evidente: in quella frazione di tempo hai allocati 10000 + 10100 boolean!!! Praticamente almeno il doppio. L'esempio l'ho fatto con numeri non enormi ma inizia a pensare di ridimensionare array davvero molto più grandi ....

Una tecnica che evita questo problema sarebbe la "segmentazione" dell'array che per gestirla bene sarebbe meglio "incapsularla" dentro una classe.
Se segmenti l'array, non hai più un unico enorme array, ma tanti piccoli segmenti, diciamo per esempio di 1024 boolean l'uno.
Se hai bisogno di altri 2048 boolean non hai bisogno di istanziare un array di 3072 boolean ma solo 2 in più da 1024 e quello iniziale oltretutto non lo perdi nemmeno.

Ed è chiaro che così, dato un indice 'i' non puoi accedere subito direttamente .... hai tanti array separati. Ma lo fai usando un array principale che "mappa" gli altri sotto-array.
Un indice es. 1780 vuol dire che devi andare nel 2° blocco da 1024 e prendere l'elemento all'indice 756.
Bastano solo pochi calcoli e puoi gestire il tutto. Ovviamente richiede qualche sforzo in più. Ma evita il problema del ridimensionamento.

E ripeto: è tutto qui, non c'è alcun "barbatrucco" (e la tecnica della segmentazione non lo vedo come un barbatrucco).

[Rubox]

Mi intrometto.
Questa della segmentazione dell'array non l'avevo mai pensata / vista ed è una tecnica che mi piace.
Per risparmiare ulteriore spazio, si potrebbe trattare un boolean, e quindi un byte (8 bit) come in realtà un insieme appunto di 8 bit, boolean primitivi? Nel senso. Se ho bisogno di 8 valori vero/falso, allora con un boolean/byte mascherando opportunamente i valori, posso memorizzarli/restituirli?

[andbin]

Originariamente inviato da Rubox
Per risparmiare ulteriore spazio, si potrebbe trattare un boolean, e quindi un byte (8 bit) come in realtà un insieme appunto di 8 bit, boolean primitivi?

Sì, possibilissimo. E anche questa è una tecnica che definirei di "segmentazione".

Come ho già detto la stessa tecnica che usa internamente java.util.BitSet. Usare una "parola" di N bit (BitSet usa dei long) dove ogni bit rappresenta un flag boolean. E chiaramente andrebbe tutto "nascosto" dentro una classe. Nel senso che se chiedo a BitSet il boolean all'indice 90, il fatto che BitSet vada a prendere il secondo long e guardare il suo bit 26 .... importa a BitSet, non all'esterno.

Però AF.D.O.C l'ha detto chiaramente: gli hanno imposto di usare solo boolean[] e basta.