Re: [Boost-users] set() of dynamic_bitset is too slow.

From: Bo Peng (ben.bob_at_[hidden])
Date: 2006-06-04 00:37:21

>
>      typedef UINT block_type;
>      boost::dynamic_bitset<block_type> succ; /* no resizing needed */
>
>      // (assuming m_N is a multiple of the UINT width, i.e. 32)
>      for(UINT i=1; i <= m_N / (block + 1); ++i)
>      {
>          block_type b = /*random...*/;
>          succ.append(b);
>      }
>
>
> Let us know if it worked for you.

I should have read the manuals more closely! I did not notice that
append is appending a block of bits, while push_back appends only one
bit.

Your code works fine, but I worry about the size of block so I use
dynamic_bitset<>::block_type and bits_per_block. The code is now more
complicated but runs *much* faster!

succ.clear();
size_t numblock = m_N/BitSet::bits_per_block;
vector<BitSet::block_type> first_blocks(numblock);
for(size_t i=0; i<numblock; ++i)
        first_blocks[i] = rng().randInt(~BitSet::block_type(0));
succ.append(first_blocks.begin(), first_blocks.end());
// last block
BitSet::block_type last_block = rng().randInt(~BitSet::block_type(0));
for(size_t i=0; i < m_N - numblock*BitSet::bits_per_block; ++i)
{
        if((last_block >> i) & 0x1)
                succ.set(numblock*BitSet::bits_per_block+i);
}

Of course BitSet is a typedef of dynamic_bitset<>.

Many thanks for your help.
Bo