在下列情况下,为什么vector <int>比vector <bool>更快

Question

当我编写LeetCode问题N-Queens时,会发现这种现象.

我有两个版本的接受代码,唯一的区别是我存储哈希表的方式,一个是使用vector<int>而另一个是使用vector<bool>.具体来说,两个版本的代码如下:

版本1,vector<int>运行时间:4毫秒

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;
}
};

版本2 ,, vector<bool>运行时间:12毫秒

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;
}
};

据我所知,vector<bool>使用1位而不是bool变量(可能是2字节)vector<int>存储每个元素,并使用4个字节存储每个元素.所以vector<bool>看起来比较小vector<int>.但是,为什么它比慢vector<int>？

Answer 1

访问单个位通常比完成可寻址单元(C++术语中的字节)慢.例如,要写一个字节,只需发出一条写指令(mov on x86).要写一个位,需要加载包含它的字节,使用按位运算符在字节内设置正确的位,然后存储结果字节.

位向量的紧凑大小很适合存储要求,但除非数据变得足够大以致缓存问题发挥作用,否则会导致速度减慢.

如果你想拥有速度并且仍然比每个值4个字节更有效,那么试试吧vector<unsigned char>.