4 ms·
Using double here seems to be unsuitable for this kind of algorithm. Agreed! But for the purpose of the post it is fine to use boost. Doing a constexpr functi
by amallia 9y ago
Using double here seems to be unsuitable for this kind of algorithm.
Agreed! But for the purpose of the post it is fine to use boost. Doing a constexpr function is definitely a plus for a production implementation.
Also I don't see how your algorithm is constant time, unless you can write a bitmap class with a constant time operator[].
Decoding the block is constant. Accessing can be constant time, but is not if you encode implicitly the all-zeros/ones block. On the other and you can still do AND or OR between compressed bitmaps by paying only the scan.
I wonder what is the benefit compared to RLE.
Benchmarking with other implementations is something I will definitely do in the future.
jooster's comment seems to be valid too
Fixed that by using blocks of size 3 instead of 4. Sorry for the mistake. Please check the update, you will see it is even more compressed than before.
- willglynn 9y agoThe updated post basically boils down to the following encoding: 000 => 00 001 => 01 00 010 => 01 01 011 => 10 00 100 => 01 10 110 => 10 01 111 => 11 It compresses all-zeroes and all-ones blocks by one bit, and expands all other blocks by one bit. Compression rates therefore depend greatly on the exact bitmap, but this approach never yields more than 33% savings, and it results in expansion for random bitmaps with densities between 0.21 and 0.79.