[squeak-dev] large dense sets of 1..n
leves at elte.hu
Sun Aug 22 23:48:18 UTC 2010
On Sun, 22 Aug 2010, 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.
> Instead I want to map each set to an array of approximately size
> n/8 bytes which, because my sets will be dense, will save space.
> Containment of a number k in a set is to be determined by testing
> whether bit k is set or cleared. Pretty standard stuff I think.
> Is there code already that does this?
Yes and no. For example Integer class >> #largePrimesUpTo:do: does this,
but it's specialized for the problem, so it's not reusable.
> If not, I will create a class LargeDenseSet containing some instance
> bitMap that holds the necessary space.
> For bitMap, is it better for me to use an array of integers or a
> How about using a BltBit?
I would just roll my own variableByteSubclass.
> Is LargeDenseSet a sufficiently used class to be part of Squeak or at
> least part of
> some standard package?
I guess not. People rarely face problems which require such a special
collection. SkipLists were removed, and I think we are fine without them
99.9% of the time.
> Ralph Boland
More information about the Squeak-dev