
Boost : 
Subject: Re: [boost] [interval container (itl)] A pretty large bitset
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 20091103 05:08:06
2009/11/3 Scott McMurray <me22.ca+boost_at_[hidden]>:
> 2009/11/2 Joachim Faulhaber <afojgo_at_[hidden]>:
>>
>> As a new use case of interval containers I have developed
>> a *large_bitset* class template on top of itl::interval_map
>> that is able to combine interval compression *and* bitset
>> compression. It is, for instance, capable of representing
>> the bitset mentioned above
>>
>> '01010101...010'
>> a b
>>
>> a: bit 0
>> b: bit 2^641
>>
>> containing 2^63 bits (or elements) with just *one* internal
>> interval associated to only *one* value of 64bit length ;)
>>
>> Curious??
>>
>
> Quite.
The compact storage of repeated bit patterns is only the lead story
to baffle the reader a bit ;)
In the end I do not think that this is the most important property of
large_bitset. In fact it is just a byproduct of the basic idea to
combine interval and bitset compression via an itl::interval_map of
bitsets.
> How does it handle a repeat of 128 1s then 128 0s then 128 1s etc?
> (Or any repeating signal with a period longer than one storage unit?)
So a large_bitset<uint64_t, mini::bits<uint64_t> > would handle
them this way:
[0,2)>"111...1" (all 64 bits set)
[2,4)>"111...1"
...
[k,k+2)>"111...1"
which is obviously much less compact than the initial example
but still a good compression.
But, to be honest, the "periodic bit compression magic" has
more limitations than that. For instance it does not manage
to represent a bit pattern
"100100100...100"
with a single node like this can be done for patterns with
an even period length <= 64 (or word_length).
As I said, it's just a nice byproduct of the design. More
important IMO is the combination of interval and bit
compression as such and also the fact that large_bitset
can be implemented with *very little* code
http://www.heroldfaulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/projects.html
on top of itl::interval_map, which demonstrates the potential
of interval containers.
Cheers
Joachim
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk