c++ - 将整数紧密地打包在一个 vector 中 - 可以更快地完成吗？

Question

对于我目前制作的数据结构，我需要将整数紧密地打包在一起。这意味着，如果 vector 中的最大元素是 n，我将最多使用 lg n 位来表示它。因此，我将整数 vector 视为位列表。我当前的解决方案工作得很好——但我需要知道我是否可以加快整数的解包速度。该查找操作是对我的数据结构的搜索查询中不可或缺的一部分。

// uint is an unsigned 32 bit integer (std::uint32_t)
uint
Data::findInt(const std::vector<uint>& input, int size, int pos) {
    pos = pos*size;
    int end = pos+size;
    int firstc = pos/32;
    int secondc = end/32;
    int ipos = pos % 32;
    int jpos = end % 32;

    if(firstc == secondc) {
        uint number = input.at(firstc);
        number = number >> (32 - end);
        number = number & ((1 << size) - 1);
        return number;
    }
    // else
    uint number = input.at(firstc);
    number = number << (jpos);
    number = number & ((1 << size) -1);
    uint number2 = input.at(secondc);
    number2 = number2 >> (32 - jpos);
    number2 = number2 & ((1 << jpos) - 1);

    return number + number2;
}

std::vector<uint>
Data::packBits(const std::vector<uint>& input, int size) {

    std::vector<char> bits = translatetobits(input, size);
    while(bits.size() % 32 != 0) {
        bits.push_back(0);
    }

    std::vector<uint> packedbits;
    for(int i = 0; i < bits.size(); i += 32) {
        uint res = 0;
        for(int j = 0; j < 31; ++j) {
            res += (bits.at(i+j));
            res = res << 1;
        }
        res += (bits.at(i+31));
        packedbits.push_back(res);
    }

    // Current lookup requires an empty entry - should be fixed
    packedbits.push_back(0);

    return packedbits;
}

我一次只能获取一个整数，而且查找操作的索引会随意跳转，所以我不能一起批量查找。有没有人有加速查找的好主意？

Answer 1

at 已选中。检查边界一次，而不是每次与 vector 的交互。

考虑使用原始指针而不是 vector 进行低级操作。

您的包装效率极低——它进行内存分配。为什么以神的名义。

您应该使用固定大小的数据，而不是通用的 uint。

您有重复的代码计算 number。考虑消除。该代码中的常量 32 与位的打包方式有关——以不同的方式打包，保存操作。

如果需要，您可以针对无分支进行优化，但这可能不会带来性能提升(它会带来最坏情况下的性能提升，但不会增加重复操作，因为分支预测器非常可靠)。一种可能性是始终将您的数据解压缩为 64 位无符号类型，然后将其移走:我认为有一些方法可以做到这一点，以便第二次查找只注入(inject)零或被屏蔽的数据，如果不需要的话.