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

From: Bo Peng (ben.bob_at_[hidden])
Date: 2006-06-07 15:36:15

> No, that is intentionally not possible. But you can construct the
> dynamic_bitset object directly from a suitable iterator range (no need
> to use an intermediate vector). Just to illustrate the point, this is
> an example iterator based on boost::iterator_facade.

I think I get the idea of this piece of code (after reading the
iterator document), but it does not really fit my needs. If you are
interested, I can explain to you the whole scenario:

In a large simulation program, I need to simulate successes at
different rates, for many times. For example, I may need to simulate a
sequence of 0/1 with probability [0.00001, 0.5, 0.003, 0.001] for
10000 times. This 10000-times process may be repeated as well. Doing
randUniform(0,1) < p 40000 times is very slow.

I then build a class that wraps around a
vector<dynamic_bitset<unsigned long> >, which, for example, has 4
dynamic_bitset of length 10000.
Since 0.5 and very small p are comon, I use special algorithms to
handle them and store the results in this bit matrix. The results will
be retrieved as size 4 vectors. The bit matrix has fixed size, and
will be refreshed when needed.

Efficiency needs to be improved in two parts:

1. set random bits when p=0.5. This has been largely solved but I need
to use a temporary vector to stored generated random number, and
transfer them into the dynamic_bitset. Your iterator allows me to
create a bitvector, but I basically need to write to an existing
vector. A built-in block iterator would be helpful in this case.

2. retrieve succ from each column of this matrix. Curently, I am doing
something like

  vector<int> succ(4);
 ....
  for(size_t i=0; i<4; ++i)
    succ[i] = succ_matrix[i][cur];
  // process succ
  cur ++
  // get another row

The [cur] operation is slow since its location in dynamic_bitset needs
to be calculated each time. It would be better if I can do something
like:

  vector<int> succ(4);
  for(size_t i=0; i<4; ++i)
    succ[i] = *(++succ_iterator[i]);

where the location is stored in iterators and need not to be re-calculated.

So, as you can see, I basically need two levels (bit and block) of
iterators to access existing bitsets.

Cheers,
Bo