Re: [boost] Dynamic Bitset formal review - half way point

From: Victor A. Wagner, Jr. (vawjr_at_[hidden])
Date: 2002-06-17 21:33:50

a sorted   vector<unsigned short> would work just fine.  Which operation on 
this "type" do you not believe exists?  set_union(), set_difference() 
already exist in <algorithm>.

At Monday 2002/06/17 12:09, you wrote:

>Has any thought been given to adding a library to support sparse bitsets
>as well as dense bitsets supported in dyn_bitset and in the standard
>bitset?
>
>Dense bitsets use 1 bit of storage for each set element, and thus are very
>space efficient if the bitset has a fairly even distribution of zeros and
>ones.
>
>However, there are some applications where the distribution of zeros and
>ones (or present in the set vs. not present in the set) are heavily
>skewed.  For example, only 10 out of 10000 members of a set may be
>present.  In these cases, a sparse bit set can be more efficient in terms
>of space and time for common operations (set union, set intersection,
>etc).  Sparse bitsets store the indexes of those set elements that are
>present/absent from the set.  The underlying representation is
>generally something like vector<unsigned short>.
>
>A dense bitset is O(log2(N)) in both storage and time for all
>operations (where N is the size of the set).  A sparse bitset is
>O(M) where M is the number of elements present (or not present) in the
>set.  For large skewed bitsets, M can be less than log2(N).
>
>I have found it useful in the past to have both sparse and dense
>implementations of a bit vector with identical interfaces.  Thus, the
>appropriate bit_vector implementation can be chosen based on what the
>programmer knows about the data distribution.
>
>For example, in the source code to the SUIF compiler from Stanford, both
>dense and sparse "natural sets" are included with identical interfaces,
>and both are heavily used in the data-flow analysis of various
>optimization passes.
>
>Do others feel that sparse bit sets would be useful and appropriate with
>an interface matching dyn_bitset?
>
>I haven't reviewed the dyn_bitset implementation so I can't give an
>opinion on it, but I did want to toss this idea out to see what people
>thought.
>
>Regards,
>-Tom Wenisch
>Computer Architecture Lab
>Carnegie Mellon University
>
>_______________________________________________
>Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Victor A. Wagner Jr.      http://rudbek.com
PGP RSA fingerprint = 4D20 EBF6 0101 B069 3817 8DBF C846 E47A
PGP D-H fingerprint = 98BC 65E3 1A19 43EC 3908 65B9 F755 E6F4 63BB 9D93
The five most dangerous words in the English language:
               "There oughta be a law"