By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,570 Members | 1,208 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,570 IT Pros & Developers. It's quick & easy.

is this the correct code for a bitset map

P: n/a
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;

Aug 18 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a
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

Aug 18 '05 #2

P: n/a

"Greg" <gr****@pacbell.net> wrote in message
news:11**********************@f14g2000cwb.googlegr oups.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 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.

Aug 18 '05 #3

P: n/a
Rich S. wrote:
"Greg" <gr****@pacbell.net> wrote in message
news:11**********************@f14g2000cwb.googlegr oups.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 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[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(binaryData); 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] = { 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[i] & 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

Aug 19 '05 #4

P: n/a

Greg wrote:
Rich S. wrote:
"Greg" <gr****@pacbell.net> wrote in message
news:11**********************@f14g2000cwb.googlegr oups.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 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[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(binaryData); 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] = { 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[i] & 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


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

Aug 19 '05 #5

P: n/a

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

Greg wrote:
Rich S. wrote:
> "Greg" <gr****@pacbell.net> wrote in message
> news:11**********************@f14g2000cwb.googlegr oups.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 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[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(binaryData); 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] = { 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[i] & 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


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
Aug 22 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.