[racket] Bloom filter?

On Mon, Jun 6, 2011 at 17:45, Robby Findler <robby at eecs.northwestern.edu> wrote:
> On Mon, Jun 6, 2011 at 8:24 AM, Erich Rast <erich at snafu.de> wrote:
>> I had something similar in mind but was wondering about the
>> space-efficiency of a vector of booleans. Does the compiler represent
>> this as a memory area where each boolean corresponds to a single bit?
>
> It does not. The simplest way to do something like that in Racket is
> to use an exact integer to represent your set and use the bitwise
> operations to adjust the set (if the set has 30 or fewer members (62
> on a 64 bit build) then there won't be any allocation for new sets).

Attached there is an implementation of compact boolean vectors that
I used in a program of mine.  This was good enough for my needs and
I have not tried alternative implementations.

Note that in this implementation there's no guarantee that

(= (boolean-vector-length (make-boolean-vector n)) n)

but only that

(>= (boolean-vector-length (make-boolean-vector n)) n)

Suggestions for improvements, of course, are welcome.

Cheers
P.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: boolean-vectors.rkt
Type: application/octet-stream
Size: 3283 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20110606/046225b1/attachment.obj>