[M3devel] iterating over sets?

[Jay]

I was asking about Modula-3 syntax and built in mechanisms.
Here are the ways to implement this sort of thing.
There are two main scenarios:
a small set  this can be either 0..n or n..m  "small" is n or m-n
a big set again 0..n or n..m offseting the start is trivial
A small set should be represented by an array of some integer type,such as array of 8 bit int, or 16 bit int, or 32 bit, or 64 bit int
It should support operations such as:
Operations my question needs:  FindFirstSetBit  FindNextSetBit(start)
Operation of course needed:  GetBit(offset)
Operations other uses of this data structure would want, though maybe not a "set":  FindFirstClearBit  FindNextClearBit(start)  FindClearBits(start,count)  FindSetBits(start,count)  SetBits(start,count)  ClearBits(start,count)
  You might want to combine some of them -- FindClearBitsAndSet, FindSetBitsAndClear.
Operations that Modula-3 already has:  union  intersect  difference  symmetric_difference
I was asked stuff about this as an interview question years ago.
Depending on processor support, one implementation is an array of bytes and youhave roughly the following small tables:
typedef unsigned char byte;byte MaximumBitsSet[256];byte MaximumBitsClear[256];byte BitsSetLeft[256];byte BitsClearLeft[256];byte BitsSetRight[256];byte BitsClearRight[256];byte OffsetOfMaximumBitsSet[256];byte OffsetOfMaximumBitsClear[256];
Some of this might be redundant.You could pack them the other way:
typedef struct BitInfo_t {  byte MaximumBitsSet; // or 3 bit bitfield  byte MaximumBitsClear;  etc.} BitInfo_t;
BitInfo_t BitInfo[256];
>From here you can reasonably easily reasonably efficiently implementthe functions I identified.
Now, if your processor supports intructions to compute some of thesefigures efficiently, esp. on a 32 bit or 64 bit integer, that mightbe more efficient. There's a term here "population count" and an instructionin some processors. Maybe also "lzcnt" -- leading zero count.
If the set does not start at 0, you just offset things at some point. Easy.
For a large set, this will use too much memory.You can use simply a sorted array of integers.And use binary search against that.Not terrible.
Or you can use an array of offset, length pairs."extents" perhaps this is called.You would sort this by offset, and again use binary search.This would tend to be more compact.
You could be adaptive.You could set some thresholds of size or density at which you would switchthe representation from one to the other.Of course you if I am frequently adding/removing items to a set, you don'twant to frequently change the representation.
I'm still pondering 64 bit integer support in the x86 back end.The basic dilemna is a stack of pairs or the existing stack of singletons wheresometimes you'd use two stack items at a time. I'm leaning towarda stack of pairs.
After that we can discuss something like: FindFirstMemberInSet FindNextMemberInSet
and adding that to the language, etc.
FIRST and NEXT seem natural but I believe FIRST already meansthe first possible value, not the first present value.
On Windows, run link /dump /exports %windir%\system32\ntdll.dll | findstr /i bit.You'll see some of this stuff and more.
 - Jay



> Date: Wed, 31 Oct 2007 23:09:11 +0100> From: lemming at henning-thielemann.de> Subject: Re: [M3devel] iterating over sets?> To: jay.krell at cornell.edu> CC: m3devel at elegosoft.com> > > On Wed, 31 Oct 2007, Jay wrote:> > > Let's say I had> >> > TYPE T = SET OF { 0 .. 256 };> >> > Must I say:> >> > VAR t: T;> > FOR i := FIRST(t) TO LAST(t)> > IF i IN t DO> > something with i> > END> > END> > You may speed up search by splitting the set into subsets.> > E.g.> > IF t * T{16..31} = T{} THEN> skip this block completely> ELSE> inspect that block in detail> END;
_________________________________________________________________
Climb to the top of the charts!  Play Star Shuffle:  the word scramble challenge with star power.
http://club.live.com/star_shuffle.aspx?icid=starshuffle_wlmailtextlink_oct
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20071102/d4f1dcbf/attachment-0001.html>