Rich said:
Rich S. wrote:
Hi,
Is the code below the best way to have the less than function for an
80
bit
bitset or is there something faster / better?
When I populate this map with millions (... and millions) of sets it
gets
slower and slower, I'm looking to make it faster.
Thanks
typedef bitset<80> myBitSet;
struct ci_less : binary_function<myBitSet, myBitSet, bool>
{
bool operator() (const myBitSet & s1, const myBitSet & s2) const
{
for(int x= 79; x >= 0; x--)
{
if(s1[x] != s2[x])
return s1[x] < s2[x];
}
}
}; // end of ci_less
typedef map<myBitSet, int,ci_less> Results_Map;
I did not see a method in the bitset interface to let you compare the
bits in groups larger than a single bit. There may be vendor-specific
extensions to the bitset class that you are using that offer such
access.
You may wish to consider using a vector<bool> instead of a bitset
since
it has the same compact storage as a bitset, but defines the less
than
operator (<) to compare two vectors lexicographically (which is the
type comparison the routine above performs).
Since a vector<bool> would no doubt compare the bits as words, it
should run up to 32 times faster than your current comparison
routine.
Greg
Can you show me how that would work in this case. I have patterns like
1101010101010 etc etc etc, that I use the bitset to represent and toss
in
the map to calculate how many I have of each.
How would vector<bool> work like that?
Thanks for your time.
Since I'm not quite sure from your question whether the bit vector is
to be initialized from a character array of ASCII 1's and 0's, a
character array with 1 and 0 values, or as an 80-bit long bit field
packed as integer values, I will provide examples for each one of those
cases.
First, declare and size the std::vector<bool> instance:
std::vector<bool> s1(80);
// Example 1
// initializer is an 80 character array of ASCII '1' and '0'
// characters
const char binaryData[80] = "010101010101...01010101010101";
for (i = 0; i < sizeof(binaryData); i++)
s1.push_back( binaryData
== '1' );
// Example 2
// initializer is an 80 element array of 1's and 0's
const char binaryData[80] = { 0, 1, 0, 1, 0, ... 1, 1, 0};
for (i = 0; i < sizeof(binaryData); i++)
s1.push_back( binaryData );
// Example 3
// initializer is s packed 80 bit bitfield declared as an array of
// four 32-bit unsigned integers.
// The code below uses the binary integer format which not all
// compilers recognize. Of course hexadecimal, decimal or octal
// notation to specify each of the 32 bit integer values would
// work just as well.
const u_int32_t binaryData[4] = { 0b00100110010011...1001100110};
for (u_int32_t i = 0; i < 4; i++)
for (u_int32_t j = (1 << 31); j != 0; j >>= 1)
s1.push_back( binaryData & j );
Once the vector<bool> object has been initialized just use it as the
key in the std::map<std::vector<bool>, int>. Note that no custom
comparision routine for the vector<bool> needs to be written in order
for the std::map to sort its elements. std::vector<bool> already
defines a less than comparison function.
I was too lazy to compile these examples myself. I did try and be
careful in writing them. Hopefully they are good enough to at least
point you in the right direction.
Greg
