为什么 vector<int>比 vector<bool> 快在以下情况下 [英] Why vector&lt;int&gt; is faster than vector&lt;bool&gt; in the following case

问题描述

当我为 LeetCode 问题N-Queens编程时发现了这种现象.>

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

版本 1，vector，运行时间:4 ms

class 解决方案 {民众:void dfs(vector<string>& crtrst, vector<vector<string>>& finalrsts, int row, vector<int>& mup, vector<int>& m45dgr, vector<int>& m135dgr){int n = crtrst.size();如果(行== n){finalrsts.push_back(crtrst);返回;}for (int j=0; jcrtrst(n,string(n,'.'));向量mup(n,1);向量m45dgr(2*n-1,1);//度数 45: '\'向量m135dgr(2*n-1,1);//度数 135: '/';整数行 = 0;dfs(crtrst,finalrsts,row,mup,m45dgr,m135dgr);返回决赛；}};

版本 2，vector，运行时间:12 毫秒

class 解决方案 {民众:void dfs(vector<string>& crtrst, vector<vector<string>>& finalrsts, int row,向量<bool>&mup、vector<bool>&m45dgr，向量<bool>&m135dgr){int n = crtrst.size();如果(行== n){finalrsts.push_back(crtrst);返回;}for (int j=0; jcrtrst(n,string(n,'.'));向量mup(n,true);向量m45dgr(2*n-1,true);//度数 45: '\'向量m135dgr(2*n-1,true);//度数 135: '/';整数行 = 0;dfs(crtrst,finalrsts,row,mup,m45dgr,m135dgr);返回决赛；}};

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

解决方案

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

位向量的紧凑尺寸非常适合存储要求，但它会导致速度变慢，除非您的数据变得足够大以致缓存问题发挥作用.

如果您想获得速度并且仍然比每个值 4 个字节更有效率，请尝试使用 vector.

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:

Version 1, 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>.

这篇关于为什么 vector<int>比 vector<bool> 快在以下情况下的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！