关于位图存储与数组下标存储的探讨

最近在看《编程珠玑》，书中的第一章提到了位图。位图存储使用二进制位的位数信息，来表示数字。例如，存储1、3、4、6、8，这五个数字，可以使用<1, 0, 1, 1, 0, 1, 0, 1>这样的向量来表示，这样可以大大减少存储空间，只用了一个字节（8bit），就可以存储原来需要的8个数字才能表示的信息。

当我跟朋友谈到这个方法时，他却产生了质疑，他觉得这样不如直接按照数组下标存储来的快。他认为数组下标直接存储，直接一步完成，二位图则需要每次位运算寻址，会非常费时间。于是我们就决定写一个程序，实际跑一下看看。

这是位图的代码

typedef struct {
    uint32_t *bits;
    size_t size;
} Bitmap;

Bitmap *create_bitmap(size_t max_num) {
    size_t num_words = (max_num + 31) / 32;  // 计算需要多少个32位字
    Bitmap *bm = malloc(sizeof(Bitmap));
    if (!bm) {
        perror("Bitmap allocation failed");
        exit(EXIT_FAILURE);
    }
    bm->bits = calloc(num_words, sizeof(uint32_t));  // 分配约 1亿位 ≈ 12.5MB
    bm->size = max_num;
    if (!bm->bits) {
        perror("Bitmap bits allocation failed");
        exit(EXIT_FAILURE);
    }
    return bm;
}

void bitmap_set(Bitmap *bm, int num) {
    size_t word_idx = num / 32;
    size_t bit_idx = num % 32;
    bm->bits[word_idx] |= (1U << bit_idx);
}

int bitmap_get(const Bitmap *bm, int num) {
    size_t word_idx = num / 32;
    size_t bit_idx = num % 32;
    return (bm->bits[word_idx] >> bit_idx) & 1U;
}

位运算把每个字节大小的内存当作为一组，使用除法判断组数，再用对8取余，得出每组的位次

下面是数组的代码

#define N 10000000  // 处理 1000 万个整数
#define MAX_NUM 100000000  // 数字范围：0 ~ 1亿

void array_set(int *arr, int num) {
    arr[num] = 1;
}

int array_get(const int *arr, int num) {
    return arr[num];
}

// 初始化数组（全部置0）
int *create_array() {
    int *arr = calloc(MAX_NUM, sizeof(int));  // 分配 1亿个int ≈ 400MB
    if (!arr) {
        perror("Array allocation failed");
        exit(EXIT_FAILURE);
    }
    return arr;
}

结果确实出乎了我们的意料，总结来说如下

当数据导向在大小在10MB一下时，数组比位图略有优势
当数据大于10MB时，位图大约要快5-10倍
然而当数据非常大时，比如1一个数，虽然位图还是要快于数组，但两者没那么明显了

这是因为

在很小数据的时候，cpu缓存可以完全存下数据，而数组的指令开销更少，所以会略快
而当数据在大时，数组就无法在缓存中完全存储了，而位图还可以。于是cpu的缓存命中率就会下降，cpu需要从内存中加载数据，我们都知道cpu缓存的速度比内存快几十倍，所以数组方式的就慢了很多
但是当数据非常大时，这时位图也无法完全缓存了，在这种情况下，影响程序运行速度的主要因素就是从内存加载的速度了，这时候两者时间接近。但是位图的存储更加紧凑，命中概率更高，所以还是会快一些。

何时选择哪种方案？

用数组：当数字范围小（例如 0~1000），或需要频繁读取且容忍内存浪费时。
用位图：当处理海量数据（如爬虫去重、数据库索引），或数字范围大但稀疏分布时。

实际应用案例：

Linux 内核页表 使用位图管理内存页
Redis 的 Bitmap 类型 用于高效存储布尔值

总结

实践是检验真理的唯一标准我们对于计算机的了解不足，忘记了计算机是一个复杂的系统，程序运行的时间受到多种因素影响。而我们都以理想的角度去理解，就导致了形而上学的认识。

收获

认识到了cpu缓存命中带来的影响
对不同数据结构在不同条件下的性能影响

关于位图存储与数组下标存储的探讨#

何时选择哪种方案？#

实际应用案例：#

总结#

收获#

关于位图存储与数组下标存储的探讨

何时选择哪种方案？

实际应用案例：

总结

收获