2015-09-28 6 views
7

Dieses Phänomen wird gefunden, wenn ich für das LeetCode-Problem N-Queens programmiert habe.Warum Vektor <int> ist schneller als Vektor <bool> im folgenden Fall

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>?

+4

Intuitiv dauert es * Zeit *, ein Bit aus komprimiertem Speicher zu packen/zu entpacken, also würde * * std :: vector '' std :: vector 'übertreffen, besonders was die CPU tatsächlich funktioniert mit sind Register ('int'-Größe oder größer). – Angew

+0

Darf ich wissen, welche Art von Compiler Sie verwenden? – DawidPi

+0

Dies ist ein gutes Beispiel dafür, wie Programmierer Intuition häufig falsch ist, wenn es darum geht, das Leistungsverhalten vorherzusagen. –

Antwort

7

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>.

+0

Warum ist 'schneller als' vector '? Ich habe die Unterschiede mit meinem Desktop getestet (sowohl 'unsigned char' als auch' bool' ausgewertet auf '1' Byte), das Ergebnis von' vector 'ist 3 mal langsamer als' vector '. Ich kann die Details nicht herausfinden, da beide 1 Byte sind. – Bin

+1

Nein, sind sie nicht. Insbesondere speichert "Vektor " nicht jedes bool als ein einzelnes Byte; Stattdessen verpackt sie sie als Bits zusammen. Das macht es mehr Speicher-effizient, aber langsamer. Das ist der ganze Punkt der Frage. –

3

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.

Verwandte Themen