A java exercise question on BitSet

[Yogesh Gnanapraksam]

Hi,
I came across this java exercise
http://java.sun.com/developer/onlineTraining/collections/magercises/BitSet/index.html while trying to get an understanding on bit sets.


I read the following lines many times before posting the question here,but I don't understand the argument ( highlighted in bold )

A sparse bitset is a large collection of boolean values where many of the values are off (or false). For maintaining these sparsely populated sets, the BitSet class can be very inefficient. Since the majority of the bits will be off, space will be occupied to store nothing. For working with these sparse bitsets, you can create an alternate representation, backed instead by a hashtable, or HashMap. Only those positions where a value is set are then stored in the mapping

The solution talks about creating a class name SparseBitSet that extends the BitSet.

In that case I don't understand how this is going to be efficient because the default storage allocation will happen for this extended class also. I am not sure how this can be efficient compared to its parent class.

Regards
Yogi

[Paul Clapham]

I don't know what you mean by "the default storage allocation", so you might want to explain that.

However, as far as your question about "efficient", consider these two possibilities:

(1) An array of one million entries where entries number 886, 105507, and 665003 are one and the rest are zero.

(2) A HashSet<Integer> containing the numbers 886, 105507, and 665003.

Now evaluate those two possibilities in terms of the various meanings of the word "efficient".

[Yogesh Gnanapraksam]

When I say default allocation ,I am referring to the size of the BitSet returned by the size() method in bitset. In my machine when I create a BitSet object and check the size ,it shows 64 .
The same allocation will happen for its subclass also. So If I extend BitSet I do inherit the default storage allocated to a BitSet object.

[Paul Clapham]

Yes, you inherit all of the instance variables of the BitSet class, if that's what you mean by "default storage". (It does help if you use the standard names for things, you know.)

[Matthew Brown]

A size of 64 isn't going to be a problem, though. The problem is when you start adding larger numbers to the underlying storage, which you won't be doing. Though you may be able to use the BitSet constructor that takes an argument to reduce the storage allocation.

[Yogesh Gnanapraksam]

Yes, you inherit all of the instance variables of the BitSet class, if that's what you mean by "default storage". (It does help if you use the standard names for things, you know.)

I was thinking in the lines of arrays ..default size of an array is 10.. something like that..may be that is not correct

A size of 64 isn't going to be a problem, though. The problem is when you start adding larger numbers to the underlying storage, which you won't be doing. Though you may be able to use the BitSet constructor that takes an argument to reduce the storage allocation.

This gives me some insight. I was thinking about how to control this initial size in a sparse bit set and make it efficient. Now I can work on the exercise to make it efficient for large bit sets.

Thanks
Yogesh

[Paul Clapham]

Yogesh Gnanapraksam wrote:

A size of 64 isn't going to be a problem, though. The problem is when you start adding larger numbers to the underlying storage, which you won't be doing. Though you may be able to use the BitSet constructor that takes an argument to reduce the storage allocation.

This gives me some insight. I was thinking about how to control this initial size in a sparse bit set and make it efficient. Now I can work on the exercise to make it efficient for large bit sets.

I'm not sure I understand the concern here. If I were overriding BitSet to provide a sparse bit-set implementation, I wouldn't even be using the underlying Vector which BitSet uses. I would just set its size to zero and carry on with my own implementation.

[Yogesh Gnanapraksam]

Hi Paul,
The exercise solution doesn't actually do that, I think your suggestion is to use the BitSet constructor with argument by specifying the size as zero..

public class SparseSet extends BitSet {
    public SparseSet() {
       super(0);
    }
    
    public static void main(String a[]) {
      
      SparseSet s = new SparseSet();
      System.out.println(s.size());
      
    }
}

This sets the size to zero ,but the solution specified doesn't seem to do it this way. That is why I was thinking how it can be efficient but then Matthew Brown suggested that it could be efficient for larger numbers.

Can you please confirm whether the above code implements your suggestion ?

[Paul Clapham]

Yogesh Gnanapraksam wrote:Can you please confirm whether the above code implements your suggestion ?

Yes, that was something like what I had in mind. You do have to call one of the superclass constructors so that looks like a good choice. However I really haven't thought too much about the question and I don't know whether calling some other superclass constructor would use some trivial fixed amount of memory which I wouldn't care about.