Có phải sử dụng vectơ các giá trị boolean chậm hơn bitet động không?

Question

Có phải sử dụng vectơ các giá trị boolean chậm hơn bitet động không?

Tôi vừa nghe về bitet động của boost, và tôi đã tự hỏi là nó có giá trị sự cố. Tôi có thể sử dụng vector của các giá trị boolean thay thế không?

Answer 1

Rất nhiều ở đây phụ thuộc vào số lượng giá trị Boolean bạn đang làm việc.

Cả hai bitet và vector<bool> thường sử dụng biểu diễn được đóng gói trong đó Boolean được lưu trữ chỉ như một bit.

Một mặt, áp đặt một số chi phí ở dạng thao tác bit để truy cập một giá trị duy nhất.

Mặt khác, điều đó cũng có nghĩa là nhiều Booleans của bạn sẽ phù hợp với bộ nhớ cache của bạn.

Nếu bạn đang sử dụng nhiều Booleans (ví dụ, triển khai rây Eratosthenes), hãy lắp nhiều bộ nhớ trong bộ nhớ cache hầu như sẽ luôn có kết quả thuần. Việc giảm sử dụng bộ nhớ sẽ giúp bạn có được nhiều hơn thao tác bit bị mất.

Hầu hết các đối số chống lại std::vector<bool> quay trở lại thực tế rằng nó không phải là vùng chứa tiêu chuẩn (nghĩa là nó không đáp ứng các yêu cầu đối với vùng chứa). IMO, đây chủ yếu là câu hỏi về kỳ vọng - vì nó nói vector, nhiều người cho rằng đó là một container (các loại vectơ khác), và chúng thường phản ứng tiêu cực với thực tế là vector<bool> không phải là vùng chứa.

Nếu bạn đang sử dụng vectơ theo cách thực sự yêu cầu nó là một vùng chứa, thì có thể bạn muốn sử dụng một số kết hợp khác - deque<bool> hoặc vector<char> có thể hoạt động tốt. Hãy suy nghĩ trước khi bạn làm điều đó mặc dù - có rất nhiều (lousy, IMO) khuyên rằng vector<bool> nên tránh nói chung, với ít hoặc không có giải thích lý do tại sao nó nên tránh ở tất cả, hoặc trong những trường hợp nó làm cho một thực tế sự khác biệt với bạn.

Có, có những tình huống mà một thứ khác sẽ hoạt động tốt hơn. Nếu bạn đang ở trong một trong những tình huống đó, sử dụng một cái gì đó khác rõ ràng là một ý tưởng tốt. Nhưng, hãy chắc chắn rằng bạn đang thực sự trong một trong những tình huống đầu tiên. Bất cứ ai nói với bạn (ví dụ) rằng "Herb nói rằng bạn nên sử dụng vector<char>" mà không có nhiều lời giải thích về sự cân bằng liên quan nên không đáng tin cậy.

Hãy đưa ra một ví dụ thực tế. Vì nó đã được đề cập trong các ý kiến, chúng ta hãy xem xét các Sieve of Eratosthenes:

#include <vector> 
#include <iostream> 
#include <iterator> 
#include <chrono> 

unsigned long primes = 0; 

template <class bool_t> 
unsigned long sieve(unsigned max) { 
    std::vector<bool_t> sieve(max, false); 
    sieve[0] = sieve[1] = true; 

    for (int i = 2; i < max; i++) { 
     if (!sieve[i]) { 
      ++primes; 
      for (int temp = 2 * i; temp < max; temp += i) 
       sieve[temp] = true; 
     } 
    } 
    return primes; 
} 

// Warning: auto return type will fail with older compilers 
// Fine with g++ 5.1 and VC++ 2015 though. 
// 
template <class F> 
auto timer(F f, int max) { 
    auto start = std::chrono::high_resolution_clock::now(); 
    primes += f(max); 
    auto stop = std::chrono::high_resolution_clock::now(); 

    return stop - start; 
} 

int main() { 
    using namespace std::chrono; 

    unsigned number = 100000000; 

    auto using_bool = timer(sieve<bool>, number); 
    auto using_char = timer(sieve<char>, number); 

    std::cout << "ignore: " << primes << "\n"; 
    std::cout << "Time using bool: " << duration_cast<milliseconds>(using_bool).count() << "\n"; 
    std::cout << "Time using char: " << duration_cast<milliseconds>(using_char).count() << "\n"; 
} 

Chúng tôi đã sử dụng một mảng đủ lớn mà chúng ta có thể mong đợi một phần lớn của nó để chiếm bộ nhớ chính. Tôi cũng đã đi đến một chút đau đớn để đảm bảo rằng chỉ điều thay đổi giữa một lời gọi và người kia là việc sử dụng một số vector<char> và vector<bool>. Đây là một số kết quả. Đầu tiên với VC++ 2015:

ignore: 34568730 
Time using bool: 2623 
Time using char: 3108 

... thì thời gian sử dụng g ++ 5.1:

ignore: 34568730 
Time using bool: 2359 
Time using char: 3116 

Rõ ràng, vector<bool> thắng trong cả hai trường hợp - bằng khoảng 15% với VC++, và hơn 30% với gcc. Cũng lưu ý rằng trong trường hợp này, tôi đã chọn kích thước để hiển thị vector<char> trong ánh sáng khá thuận lợi. Nếu, ví dụ, tôi giảm number100000000-10000000, sự khác biệt thời gian trở nên nhiều lớn:

ignore: 3987474 
Time using bool: 72 
Time using char: 249 

Mặc dù tôi đã không được thực hiện rất nhiều công việc để xác nhận, tôi đoán rằng trong trường hợp này , phiên bản sử dụng vector<bool> sẽ tiết kiệm đủ không gian mà mảng phù hợp hoàn toàn trong bộ nhớ cache, trong khi vector<char> đủ lớn để tràn bộ nhớ cache và liên quan đến rất nhiều quyền truy cập bộ nhớ chính.

Answer 2

Bạn thường nên tránh std::vector<bool> vì đó không phải là vùng chứa tiêu chuẩn. Đó là một phiên bản đóng gói, do đó, nó phá vỡ một số đảm bảo có giá trị thường được đưa ra bởi một vector. Một lựa chọn hợp lệ sẽ là sử dụng std::vector<char> đó là những gì Herb Sutter khuyến cáo.

Bạn có thể đọc thêm về nó trong Cập nhật GotW on the subject.

mình:

Như đã chỉ ra, vector<bool> có thể được sử dụng để hiệu quả tốt, như một đại diện đóng gói cải thiện địa phương trên tập dữ liệu lớn. Nó có thể là lựa chọn thay thế nhanh nhất tùy theo hoàn cảnh. Tuy nhiên, tôi vẫn không khuyến nghị nó theo mặc định vì nó phá vỡ nhiều lời hứa được thiết lập bởi std::vector và đóng gói là một sự cân bằng tốc độ/bộ nhớ mà có thể mang lại lợi ích cả về tốc độ và bộ nhớ.

Nếu bạn chọn sử dụng nó, tôi sẽ làm như vậy sau khi đo lường nó chống lại vector<char> cho ứng dụng của bạn. Thậm chí sau đó, tôi khuyên bạn nên sử dụng một số typedef để tham chiếu đến nó thông qua một tên mà dường như không đảm bảo rằng nó không giữ.

Answer 3

Dường như kích thước của một bit động không thể thay đổi: "Lớp dynamic_bitset gần giống với lớp std :: bitset. Sự khác biệt là kích thước của dynamic_bitset (số bit) được chỉ định tại thời gian chạy trong khi xây dựng đối tượng dynamic_bitset, trong khi kích thước của std :: bitset được chỉ định tại thời gian biên dịch thông qua tham số mẫu nguyên. " (từ http://www.boost.org/doc/libs/1_36_0/libs/dynamic_bitset/dynamic_bitset.html) Như vậy, nó sẽ nhanh hơn một chút vì nó sẽ có chi phí thấp hơn một chút so với véc tơ, nhưng bạn mất khả năng chèn các phần tử.

Answer 4

CẬP NHẬT: Tôi chỉ nhận ra rằng OP được hỏi về vector<bool> vs bitset, và câu trả lời của tôi không trả lời câu hỏi, nhưng tôi nghĩ rằng tôi nên rời khỏi nó, nếu bạn tìm kiếm C++ vector bool chậm, bạn kết thúc trên này này.

vector<bool> quá chậm. Ít nhất là trên hệ thống Arch Linux của tôi (bạn có thể có thể thực hiện tốt hơn hoặc một cái gì đó ... nhưng tôi đã thực sự ngạc nhiên). Nếu ai có bất cứ đề nghị nào tại sao nó quá chậm, tôi là tất cả tai! (Xin lỗi vì sự khởi đầu thẳng thắn, đây là phần chuyên nghiệp hơn.)

Tôi đã viết hai bản triển khai của SOE và việc triển khai 'gần với kim loại' C nhanh gấp 10 lần. sievec.c là triển khai C và sievestl.cpp là triển khai C++. Tôi vừa biên soạn với make (chỉ các quy tắc ngầm, không có makefile): và kết quả là 1.4 giây cho phiên bản C, và 12 giây cho phiên bản C++/STL:

sievecmp % make -B sievec && time ./sievec 27 
cc  sievec.c -o sievec 
aa 1056282 
./sievec 27 1.44s user 0.01s system 100% cpu 1.455 total 

và

sievecmp % make -B sievestl && time ./sievestl 27 
g++  sievestl.cpp -o sievestl 
1056282./sievestl 27 12.12s user 0.01s system 100% cpu 12.114 total 

sievec.c là như sau:

#include <stdio.h> 
#include <stdlib.h> 

typedef unsigned long prime_t; 
typedef unsigned long word_t; 
#define LOG_WORD_SIZE 6 

#define INDEX(i) ((i)>>(LOG_WORD_SIZE)) 
#define MASK(i) ((word_t)(1) << ((i)&(((word_t)(1)<<LOG_WORD_SIZE)-1))) 
#define GET(p,i) (p[INDEX(i)]&MASK(i)) 
#define SET(p,i) (p[INDEX(i)]|=MASK(i)) 
#define RESET(p,i) (p[INDEX(i)]&=~MASK(i)) 
#define p2i(p) ((p)>>1) // (((p-2)>>1)) 
#define i2p(i) (((i)<<1)+1) // ((i)*2+3) 

unsigned long find_next_zero(unsigned long from, 
        unsigned long *v, 
        size_t N){ 
    size_t i; 
    for (i = from+1; i < N; i++) { 
    if(GET(v,i)==0) return i; 
    } 

    return -1; 
} 

int main(int argc, char *argv[]) 
{ 

    size_t N = atoi(argv[1]); 
    N = 1lu<<N; 
    // printf("%u\n",N); 
    unsigned long *v = malloc(N/8); 
    for(size_t i = 0; i < N/64; i++) v[i]=0; 

    unsigned long p = 3; 
    unsigned long pp = p2i(p * p); 

    while(pp <= N){ 

    for(unsigned long q = pp; q < N; q += p){ 
     SET(v,q); 
    } 
    p = p2i(p); 
    p = find_next_zero(p,v,N); 
    p = i2p(p); 
    pp = p2i(p * p); 
    } 

    unsigned long sum = 0; 
    for(unsigned long i = 0; i+2 < N; i++) 
    if(GET(v,i)==0 && GET(v,i+1)==0) { 
     unsigned long p = i2p(i); 
     // cout << p << ", " << p+2 << endl; 
     sum++; 
    } 
    printf("aa %lu\n",sum); 
    // free(v); 
    return 0; 
} 

sievestl.cpp là như sau:

#include <iostream> 
#include <vector> 
#include <sstream> 

using namespace std; 

inline unsigned long i2p(unsigned long i){return (i<<1)+1; } 
inline unsigned long p2i(unsigned long p){return (p>>1); } 
inline unsigned long find_next_zero(unsigned long from, vector<bool> v){ 
    size_t N = v.size(); 
    for (size_t i = from+1; i < N; i++) { 
    if(v[i]==0) return i; 
    } 

    return -1; 
} 

int main(int argc, char *argv[]) 
{ 
    stringstream ss; 
    ss << argv[1]; 
    size_t N; 
    ss >> N; 
    N = 1lu<<N; 
    // cout << N << endl; 
    vector<bool> v(N); 

    unsigned long p = 3; 
    unsigned long pp = p2i(p * p); 

    while(pp <= N){ 

    for(unsigned long q = pp; q < N; q += p){ 
     v[q] = 1; 
    } 
    p = p2i(p); 
    p = find_next_zero(p,v); 
    p = i2p(p); 
    pp = p2i(p * p); 
    } 

    unsigned sum = 0; 
    for(unsigned long i = 0; i+2 < N; i++) 
    if(v[i]==0 and v[i+1]==0) { 
     unsigned long p = i2p(i); 
     // cout << p << ", " << p+2 << endl; 
     sum++; 
    } 
    cout << sum; 
    return 0; 
}