为什么在以下情况下 vector<int> 比 vector<bool> 更快?

10
当我为LeetCode问题N-Queens编程时,发现了这种现象。
我有两个已被接受的代码版本,唯一的区别是哈希表存储方式,一个使用vector<int>,另一个使用vector<bool>。具体来说,这两个代码版本如下: vector<int>
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;
}
};
>
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> 慢呢?

4
直观地讲,从压缩存储中打包/解包一位需要时间,因此我预计std::vector<int>的性能优于std::vector<bool>,尤其是因为CPU实际处理的是寄存器(大小为int或更大)。 - Angew is no longer proud of SO
请问您使用的是哪种编译器? - DawidPi
这是一个很好的例子,说明当涉及到预测性能行为时,程序员的直觉经常是错误的。 - Andre Kostur
@DawidPi,我按照LeetCode在线评测系统的时间报告了时间。所以我不知道它使用的编译器是什么。 - C. Wang
2个回答

14

访问单个位的速度通常比访问整个可寻址单元(在C ++中是字节)要慢。例如,要写入一个字节,您只需发出写入指令(在x86上为mov)。要写入一个位,您需要加载包含它的字节,使用按位运算符来设置字节内的正确位,然后存储生成的字节。

位向量的紧凑大小对存储要求很好,但除非您的数据足够大以至于缓存问题起作用,否则会导致减速。

如果您想要速度并且仍然比每个值的4个字节更有效率,请尝试使用 vector<unsigned char>


为什么vector<unsigned char>vector<bool>更快?我用我的台式机进行了测试(unsigned charbool都被评估为1个字节),结果显示vector<bool>vector<unsigned char>慢3倍。我无法理解这个细节,因为它们都是1个字节。 - Bin
4
不是的。具体来说,vector<bool>不会将每个bool值单独存储在一个字节中;而是将它们打包成位(bit)。这使得它更加节省空间,但速度较慢。这就是问题的全部意义所在。 - Sebastian Redl

3

我的解释:

vector<type> 有一个针对 bool 的特化,它是一个位图;这在存储方面非常高效(1Byte的向量存储 = 8个bool),但是在实际访问数据时效率较低;对于任何其他的 vector,只需通过 *([第一个元素地址 + n*sizeof(element)]) 访问第n个位置上的元素,但对于从字节存储中获取 bool 值,您不可避免地需要进行一些位操作,这在大缓存时可能会比只有表示每个真值的int数组慢得多。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接