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

Levente Uzonyi 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
> LargePositiveInteger.
> 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.


Levente

>
> Regards,
>
> Ralph Boland
>
>



More information about the Squeak-dev mailing list