448,570 Members | 1,208 Online
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 { 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 Results_Map; Aug 18 '05 #1
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 { 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 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 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 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" 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 { 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 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 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 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 work like that? Thanks for your time. Aug 18 '05 #3

 P: n/a Rich S. wrote: "Greg" 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 { 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 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 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 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 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 instance: std::vector 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 object has been initialized just use it as the key in the std::map, int>. Note that no custom comparision routine for the vector needs to be written in order for the std::map to sort its elements. std::vector 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" 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> {> 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 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 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 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 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 instance: std::vector 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 object has been initialized just use it as the key in the std::map, int>. Note that no custom comparision routine for the vector needs to be written in order for the std::map to sort its elements. std::vector 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" wrote in message news:11**********************@g47g2000cwa.googlegr oups.com... Greg wrote: Rich S. wrote: > "Greg" 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 > >> { > >> 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 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 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 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 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 instance: std::vector 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 object has been initialized just use it as the key in the std::map, int>. Note that no custom comparision routine for the vector needs to be written in order for the std::map to sort its elements. std::vector 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.