Tại sao vector <int> nhanh hơn vectơ <bool> trong trường hợp sau

Question

Hiện tượng này được tìm thấy khi tôi lập trình cho vấn đề LeetCode N-Queens.

Tôi có hai phiên bản mã được chấp nhận, khác biệt duy nhất giữa đó là cách tôi lưu trữ bảng băm, một là sử dụng vector<int> và cách khác đang sử dụng vector<bool>. Để cụ thể, hai phiên bản của mã như sau:

Phiên bản 1, vector<int>, Running Thời gian: 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; 
} 
}; 

Phiên bản 2, vector<bool>, Thời lượng: 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; 
} 
}; 

Như tôi biết rằng, vector<bool> lưu trữ từng phần tử sử dụng 1 bit thay vì biến số bool (có thể là 2 byte) và vector<int> lưu trữ từng phần tử bằng cách sử dụng 4 byte. Vì vậy, vector<bool> có vẻ tinier hơn vector<int>. Tuy nhiên, tại sao nó chậm hơn vector<int>?

Answer 1

Truy cập vào các bit đơn thường chậm hơn để hoàn thành các đơn vị địa chỉ (byte trong lingo của C++). Ví dụ, để viết một byte, bạn chỉ cần viết một lệnh viết (mov on x86). Để viết một chút, bạn cần tải byte chứa nó, sử dụng các toán tử bitwise để thiết lập bit bên phải trong byte, và sau đó lưu trữ byte kết quả.

Kích thước nhỏ gọn của bit bit là tốt cho các yêu cầu lưu trữ, nhưng điều này sẽ dẫn đến chậm lại trừ khi dữ liệu của bạn đủ lớn để các vấn đề trong bộ nhớ đệm đóng vai trò.

Nếu bạn muốn có tốc độ và vẫn hiệu quả hơn 4 byte cho mỗi giá trị, hãy thử vector<unsigned char>.

Answer 2

giải thích của tôi:

Có một chuyên vector<type> cho bool, đó là một bản đồ bit; đó là hiệu quả cao liên quan đến lưu trữ (1Byte của lưu trữ vector = 8 bool), nhưng tồi tệ hơn tại thực sự truy cập dữ liệu; cho bất kỳ vector nào khác, bạn chỉ có thể truy cập phần tử tại vị trí thứ n bởi *([address of first element + n * sizeof(element)]), nhưng đối với việc lưu trữ bool-out-of-byte, bạn chắc chắn sẽ cần thực hiện một số thao tác bit, trong thời gian lớn cache, có thể chậm hơn đáng kể so với chỉ có một mảng là int s, đại diện cho một giá trị chân lý.