C++中如何存储布尔数据以实现快速按位与运算

我拥有一个编译时大小未知的布尔值数据库，示例如下：

Dtb[100][6] = { {0,1,0,1,1,0},
                {1,0,0,1,1,0},
                {0,0,1,0,1,0},
                ...          }

该数据库仅在运行时初始化一次，之后不再修改。需要针对给定的布尔数组i = {0,0,0,1,1,0}，检查每一行是否满足条件：若i中的某一位为true，则该行对应位置也必须为true，即通过i == i & row进行判断。

希望找到C++中存储该数据库的最优方式，使这类检查操作速度极快。曾考虑以下几种方案：

• std::vector<std::vector<bool>>
• std::vector<std::vector<char>>（或按列存储）
• boost::dynamic_bitset

调研得出以下结论：

• 不应使用std::vector<bool>，因为它并非标准容器
• boost::dynamic_bitset的存储空间占用比std::vector<bool>更少
• std::vector<char>访问速度更快，但初始化耗时更长

由于可直接使用按位与运算，无需单独访问单个位，曾认为boost::dynamic_bitset或许是最佳选择。

补充说明 #

• 不能使用std::array类，因为编译时无法知晓数据库的大小
• 数据库维度可能较大，每行最多可容纳约100个值

解决方案 #

参考论文《Performance of C bit-vector implementations》，boost::dynamic_bitset是C++中动态可调整大小的位向量实现的最佳选择。但实现@Homer512提供的BoolMatrix类后，对比测试发现其速度比boost::dynamic_bitset快5倍，测试代码及输出如下：

测试代码 #

#include <iostream>
#include <chrono>
#include <vector>
#include <boost/dynamic_bitset.hpp>

#define ROWS 1000000
#define COLS 30
#define LOOPS 100

using namespace std;

// BoolMatrix class
class BoolMatrix {
private:
    std::size_t rows, bits_per_row, ints_per_row;
    std::vector<std::uint64_t> data;
public:
    BoolMatrix(std::size_t rows, std::size_t bits_per_row)
        : rows(rows),
        bits_per_row(bits_per_row),
        ints_per_row((bits_per_row + 63) / 64),
        data(rows* ints_per_row) {
        for (std::uint64_t& ints : data) { ints = 0; }
    }

    void set(std::size_t row, std::size_t col) noexcept {
        data[row * ints_per_row + col / 64] |= ( 1 << (col % 64) );
    }

    int match_count(const std::uint64_t* subset) const noexcept {
        int count = 0;
        for (std::size_t i = 0; i < rows; ++i) {
            for (std::size_t j = 0; j < ints_per_row; ++j) {
                if ((data[i * ints_per_row + j] & subset[j]) != subset[j]) { break; } // mismatch
                if (j == ints_per_row - 1) { count++; } // match
            }
        }
        return count;
    }
};

// some auxiliary functions
void tic_clock(std::chrono::high_resolution_clock::time_point start) {
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() * 1e-9 << std::endl;
}
void set(bool* matrix, int row, int col, bool value) {
    matrix[row * COLS + col] = value;
}
bool get(bool* matrix, int row, int col) {
    return matrix[row * COLS + col];
}

int main()
{
    auto start = std::chrono::high_resolution_clock::now();
    bool* data;
    data = new bool[ROWS * COLS];
    assert(data != NULL);
    bool compare[COLS] = { 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1 }; // 101000101010000000000111000101
    int counter;

    // generate random bool dtb
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            set(data, i, j, rand() % 2);
        }
    }
    tic_clock(start);

    //
    // vector of bitsets
    vector<boost::dynamic_bitset<uint32_t>> data_a(ROWS, boost::dynamic_bitset<uint32_t>(COLS));
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            // set data
            if (get(data,i,j)) { data_a[i].set(j); }
        }
    }
    tic_clock(start);
    
    boost::dynamic_bitset<uint32_t> compare_a(COLS);
    for (int j = 0; j < COLS; j++) {
        if (compare[j]) { compare_a.set(j); }
    }
    tic_clock(start);

    // count number of subsets !!!
    for (int k = 0; k < LOOPS; k++) {
        counter = 0;
        for (const auto& row : data_a) {
            if (compare_a.is_subset_of(row)) { counter++; }
        }
    }
    tic_clock(start);

    cout << counter << endl;
    
    //
    // BoolMatrix
    BoolMatrix data_b(ROWS, COLS);
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            // set data
            if (get(data, i, j)) { data_b.set(i,j); }
        }
    }
    tic_clock(start);

    std::uint64_t compare_b[(COLS + 63) / 64];
    compare_b[0] = 0;
    for (int j = 0; j < COLS; j++) {
        if (compare[j]) { compare_b[j / 64] |= (1 << (j % 64)); } // stored reverse
    }
    tic_clock(start);

    // count number of subsets !!!
    for (int k = 0; k < LOOPS; k++) {
        counter = data_b.match_count(compare_b);
    }
    tic_clock(start);

    cout << counter << endl;

    delete[] data;
    return 0;
}

测试输出 #

4.11788
5.92903
5.92976
10.8508 // -> takes ~5sec
870 // count
11.5189
11.5199
12.2765 // -> takes ~1sec
870 // count

最终若改用C语言实现可能会有小幅性能提升，但提升幅度不大。感谢@Homer512提供的快速且详尽的解答。

内容的提问来源于stack exchange，提问作者entrepreneur