This phenomenon is found when I programmed for the LeetCode problem N-Queens.
I have two versions of accepted code, the only difference between which is the way I stored the hash table, one is using vector<int>
and the other is using vector<bool>
. To be specific, the two versions of code are as follows:
vector<int>
, Running Time: 4 ms
class Solution {
public:
void dfs(vector<string>& crtrst, vector<vector<string>>& finalrsts, int row, vector<int>& mup, vector<int>& m45dgr, vector<int>& m135dgr)
{
int n = crtrst.size();
if (row == n)
{
finalrsts.push_back(crtrst);
return;
}
for (int j=0; j<n; j++)
{
if (mup[j] && m45dgr[j-row+n-1] && m135dgr[row+j])
{
crtrst[row][j] = 'Q';
mup[j] = m45dgr[j-row+n-1] = m135dgr[row+j] = 0;
dfs(crtrst,finalrsts,row+1,mup,m45dgr,m135dgr);
crtrst[row][j] = '.';
mup[j] = m45dgr[j-row+n-1] = m135dgr[row+j] = 1;
}
}
}
vector<vector<string>> solveNQueens(int n)
{
vector<vector<string>> finalrsts;
vector<string> crtrst(n,string(n,'.'));
vector<int> mup(n,1);
vector<int> m45dgr(2*n-1,1); // degree 45: '\'
vector<int> m135dgr(2*n-1,1); // degree 135: '/';
int row = 0;
dfs(crtrst,finalrsts,row,mup,m45dgr,m135dgr);
return finalrsts;
}
};
Version 2, vector<bool>
, Running time: 12 ms
class Solution {
public:
void dfs(vector<string>& crtrst, vector<vector<string>>& finalrsts, int row,
vector<bool>& mup, vector<bool>& m45dgr, vector<bool>& m135dgr)
{
int n = crtrst.size();
if (row == n)
{
finalrsts.push_back(crtrst);
return;
}
for (int j=0; j<n; j++)
{
if (mup[j] && m45dgr[j-row+n-1] && m135dgr[row+j])
{
crtrst[row][j] = 'Q';
mup[j] = m45dgr[j-row+n-1] = m135dgr[row+j] = false;
dfs(crtrst,finalrsts,row+1,mup,m45dgr,m135dgr);
crtrst[row][j] = '.';
mup[j] = m45dgr[j-row+n-1] = m135dgr[row+j] = true;
}
}
}
vector<vector<string>> solveNQueens(int n)
{
vector<vector<string>> finalrsts;
vector<string> crtrst(n,string(n,'.'));
vector<bool> mup(n,true);
vector<bool> m45dgr(2*n-1,true); // degree 45: '\'
vector<bool> m135dgr(2*n-1,true); // degree 135: '/';
int row = 0;
dfs(crtrst,finalrsts,row,mup,m45dgr,m135dgr);
return finalrsts;
}
};
As I know that, vector<bool>
stores each element using 1 bit rather than a bool
variable (may be 2 Bytes), and vector<int>
stores each element using 4 Bytes. So vector<bool>
seems tinier than vector<int>
. However, why it is slower than vector<int>
?
Access to single bits is usually slower than to complete addressable units (bytes in the lingo of C++). For example, to write a byte, you just issue a write instruction (mov on x86). To write a bit, you need to load the byte containing it, use bitwise operators to set the right bit within the byte, and then store the resulting byte.
The compact size of a bit vector is nice for storage requirements, but it will result in a slowdown except when your data becomes large enough that caching issues play a role.
If you want to have speed and still be more efficient than 4 bytes per value, try a vector<unsigned char>
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With