is this the correct code for a bitset map

[Rich S.]

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;

[Greg]

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 lexicographical ly (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

[Rich S.]

"Greg" <gr****@pacbell .net> wrote in message
news:11******** **************@ f14g2000cwb.goo glegroups.com.. .

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 lexicographical ly (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.

[Greg]

Rich S. wrote:

"Greg" <gr****@pacbell .net> wrote in message
news:11******** **************@ f14g2000cwb.goo glegroups.com.. .

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 lexicographical ly (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<boo l> instance:

std::vector<boo l> 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(binaryDa ta); i++)
s1.push_back( binaryData[i] == '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(binaryDa ta); i++)
s1.push_back( binaryData[i] );

// 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] = { 0b0010011001001 1...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[i] & j );

Once the vector<bool> object has been initialized just use it as the
key in the std::map<std::v ector<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<boo l> 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

[Greg]

Greg wrote:

Rich S. wrote:

"Greg" <gr****@pacbell .net> wrote in message
news:11******** **************@ f14g2000cwb.goo glegroups.com.. .

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 lexicographical ly (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<boo l> instance:

std::vector<boo l> 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(binaryDa ta); i++)
s1.push_back( binaryData[i] == '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(binaryDa ta); i++)
s1.push_back( binaryData[i] );

// 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] = { 0b0010011001001 1...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[i] & j );

Once the vector<bool> object has been initialized just use it as the
key in the std::map<std::v ector<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<boo l> 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

Of course just after I post I find my first mistake. Change Example 3
to declare an array of 5 unsigned 16-bit shorts and change the loop to
match. Four 32 bit integers has far too many bits.

Greg

[Rich S.]

"Greg" <gr****@pacbell .net> wrote in message
news:11******** **************@ g47g2000cwa.goo glegroups.com.. .

Greg wrote:

Rich S. wrote:

> "Greg" <gr****@pacbell .net> wrote in message
> news:11******** **************@ f14g2000cwb.goo glegroups.com.. .
> > 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 lexicographical ly (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<boo l> instance:

std::vector<boo l> 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(binaryDa ta); i++)
s1.push_back( binaryData[i] == '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(binaryDa ta); i++)
s1.push_back( binaryData[i] );

// 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] = { 0b0010011001001 1...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[i] & j );

Once the vector<bool> object has been initialized just use it as the
key in the std::map<std::v ector<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<boo l> 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

Of course just after I post I find my first mistake. Change Example 3
to declare an array of 5 unsigned 16-bit shorts and change the loop to
match. Four 32 bit integers has far too many bits.

Greg

Thanks for the samples. I'll try them out and see what works best for me.

Thanks again