Re: [boost] [interval container (itl)] A pretty large bitset

Subject: Re: [boost] [interval container (itl)] A pretty large bitset
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2009-11-03 04:34:58

2009/11/3 OvermindDL1 <overminddl1_at_[hidden]>:
> On Mon, Nov 2, 2009 at 10:25 AM, Joachim Faulhaber
> <afojgo_at_[hidden]> wrote:
>>
>> Find the documented example code in my updated library
>> docs at
>>
>> http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/projects.html
>>
>
> Hmm, this looks quite fascinating, I have very random bitset and
> normal sparse methods do not work, might see if this does.

I hope I does :)

But I have to point out, that a randomly distributed *and*
sparse set is the worst case scenario for the 'large_bitset'
as well.

(1) If you have long runs of bits set to '1' (or repeating bit patterns),
  interval compression kicks in.
(2) If you have regions with randomly but relatively densely distributed
  bits, bit compression will help.

For a randomly distributed and sparse set non of these
compression techniques can be applied. In the worst case
you are holding one tree node of the underlying rb-tree for
every bit.

Joachim