[squeak-dev] large dense sets of 1..n

Yoshiki Ohshima yoshiki at vpri.org
Tue Aug 24 04:23:31 UTC 2010


At Mon, 23 Aug 2010 19:37:28 -0600,
Ralph Boland wrote:
> 
> >> I need to create some dense sets which will contain
> >> subsets of the integers á1..n where n is very large.
> >> I don't want to use regular sets because they would use to much space.
> ...
> >> Is there code already that does this?
> ...
> >> Ralph Boland
> >
> > You can see example in WideCharacterSet in image, or also load
> > BitArray from SqueakMap.
> 
> > See also these messages for playing with bits
> > http://lists.squeakfoundation.org/pipermail/squeak-dev/2009-December/141893.html
> ...
> 
> I downloaded BitArray and discovered that it used Form.
> This seemed backwards to me so I looked at Form and discovered
> that Form uses Bitmap.  Bitmap looked like what I was looking for
> so I looked at Bitmap.

  What is backwards?  A collection of bits should represent a bitmap but a
bitmap should not represent a collection of bits?

> To use Bitmap I would need to add methods  at:  and  at:put:  based on code
> from class BitArray.

  And, these accessors are pretty much provided via Form.  Yes, Form
is a facade to a collection of bits so to me, it is pretty good way to
represent bits.

>  However, the code in BitArray use instance variables
> wordCache cacheIndex which make accessing consecutive bits more efficient.

  You should measure the effects of the cache for your use case.  It
may not be needed.

> So my plan was to create class BitSet which will be a subclass of Bitmap and
> have instance variables wordCache and casheIndex.  Of course this didn't work
> because I am not allowed to add instance variables to BitSet.
> So my plan now is to make BitSet a subclass of ArrayedCollection with
> an instance variable bitmap holding objects of class Bitmap.
> I will implement some but not all of the methods in BitArray.
> I will also implement methods booleanAt:  and booleanAt:put:.

  In that way, you cannot take advantage of existing primitives for
Forms.  These are pretty efficient.  Why don't you add a few methods
to BitArray (like add:, includes: and etc.)?  BitArray would suddenly
behave as if a set of integers.

> BitSet will be a class in a package that I will eventually release to SqueakMap
> so I thought it was worth allowing comments before I implement
> BitSet.

  BitArray is also on SqueakSource.  If you are happy with the idea of
just adding some features to it, I don't mind adding you as a commitor.

-- Yoshiki



More information about the Squeak-dev mailing list