Warum Vektor <int> ist schneller als Vektor <bool> im folgenden Fall

Question

Dieses Phänomen wird gefunden, wenn ich für das LeetCode-Problem N-Queens programmiert habe.

Ich habe zwei Versionen von akzeptiertem Code, der einzige Unterschied zwischen denen ist die Art, wie ich die Hash-Tabelle gespeichert, verwendet vector<int> und die andere verwendet vector<bool>. Um genau zu sein, sind die beiden Versionen von Code wie folgt:

Version 1, vector<int>, Laufzeit: 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>, Laufzeit: 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; 
} 
}; 

Wie ich weiß, dass vector<bool> jedes Element unter Verwendung von 1 Bit anstelle einer bool Variablen (möglicherweise 2 Bytes) speichert und vector<int> speichert jedes Element mit 4 Bytes. So scheint vector<bool> kleiner als vector<int>. Warum ist es jedoch langsamer als vector<int>?

Answer 1

Der Zugriff auf einzelne Bits ist normalerweise langsamer als das Abschließen von adressierbaren Einheiten (Bytes im Jargon von C++). Um beispielsweise ein Byte zu schreiben, geben Sie einfach eine Schreibanweisung aus (mov on x86). Um ein Bit zu schreiben, müssen Sie das Byte, das es enthält, laden, verwenden Sie bitweise Operatoren, um das richtige Bit in dem Byte festzulegen, und speichern Sie dann das resultierende Byte.

Die kompakte Größe eines Bitvektors eignet sich gut für Speicheranforderungen, führt jedoch zu einer Verlangsamung, außer wenn Ihre Daten groß genug werden, dass Caching-Probleme eine Rolle spielen.

Wenn Sie Geschwindigkeit haben und dennoch effizienter als 4 Bytes pro Wert sein möchten, versuchen Sie eine vector<unsigned char>.

Answer 2

Meine Interpretation:

Es gibt eine vector<type> Spezialisierung für bool, die eine Bitmap ist; das ist sehr effizient in Bezug auf die Speicherung (1Byte Vektorspeicher = 8 bool), aber schlechter beim tatsächlichen Zugriff auf die Daten; Für jede andere vector, können Sie nur auf das Element an der n th Position von *([address of first element + n * sizeof(element)]) zugreifen, aber für die Bool-Out-of-Byte-Speicher zu bekommen, werden Sie unweigerlich einige Bit-Operationen, die in Zeiten von großen machen müssen Caches, möglicherweise erheblich langsamer als nur ein Array von int s, die jeweils einen Wahrheitswert darstellen.