• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

A java exercise question on BitSet

 
Ranch Hand
Posts: 133
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Marshal
Posts: 28177
95
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 133
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 28177
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.)
 
Bartender
Posts: 4568
9
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 133
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Marshal
Posts: 28177
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 133
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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..


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
Marshal
Posts: 28177
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic