A
aloha.kakuikanu
JLS describes boolean array
boolean[] x
implemented via array of integers. So if there is a space
consideration, then one may want to pack bits into the integers and
define boolean array as:
class BooleanArray {
private int[] data;
public BooleanArray( int size ) {
data = new int[size/Integer.SIZE+1];
for( int i = 0; i < data.length; i++ )
data = 0;
}
public boolean get( int index ) {
int row = index/Integer.SIZE;
int col = index%Integer.SIZE;
return ((data[row]>>col)&1)==1;
}
public void set( int index, boolean val ) {
int row = index/Integer.SIZE;
int col = index%Integer.SIZE;
int bitmap = data[row];
if( !val ) if( (((bitmap>>col)&1)==1) )
data[row]=bitmap ^ (1<<col);
if( val ) if( (((bitmap>>col)&1)==0) )
data[row]=bitmap | (1<<col);
}
}
Now, I found this implementation to be more than 3 times slower than
native boolean[]. Is this expected behavior, or I'm missing something?
Or, perhaps there is a well known alternative packed boolean array
implementation which doesn't suffer the above space-time tradeoff?
BTW, why boolean is not the same as byte[] (or char[] -- whatever is
smaller?-)
boolean[] x
implemented via array of integers. So if there is a space
consideration, then one may want to pack bits into the integers and
define boolean array as:
class BooleanArray {
private int[] data;
public BooleanArray( int size ) {
data = new int[size/Integer.SIZE+1];
for( int i = 0; i < data.length; i++ )
data = 0;
}
public boolean get( int index ) {
int row = index/Integer.SIZE;
int col = index%Integer.SIZE;
return ((data[row]>>col)&1)==1;
}
public void set( int index, boolean val ) {
int row = index/Integer.SIZE;
int col = index%Integer.SIZE;
int bitmap = data[row];
if( !val ) if( (((bitmap>>col)&1)==1) )
data[row]=bitmap ^ (1<<col);
if( val ) if( (((bitmap>>col)&1)==0) )
data[row]=bitmap | (1<<col);
}
}
Now, I found this implementation to be more than 3 times slower than
native boolean[]. Is this expected behavior, or I'm missing something?
Or, perhaps there is a well known alternative packed boolean array
implementation which doesn't suffer the above space-time tradeoff?
BTW, why boolean is not the same as byte[] (or char[] -- whatever is
smaller?-)