[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
|