排序和查找算法-Bitmap算法

偶然看到Bitmap算法，利用闲暇时间仔细深入研究一番，这里谈谈我的感悟。

一、算法思想

在日常编程过程中，我们熟知很多高性能的排序算法，比如：归并排序算法，在一定大数据量、时间复杂度上有很大优势。如果当前有10亿整形数，所需要的空间为10^9 × 4 / (1024 ^ 3) = 3.725 G，其中4为int类型所占字节数。

当在所限的硬件条件下，又提倡高性能，一次性加载这么多数据肯定是不可行的。那么我们如何解决在所限的硬件条件下，又能达到高性能的处理速度，那么就需要考虑怎么把整形数用一个bit来表示，就能大大的减小10亿整形数所占用的内存(3.725 / 8 = 0.465G)。

把十进制的数通过map表映射到bit位，0表示无，1表示有，这就是Bitmap的算法思想。

二、Bitmap表

假设我们需要排序的int型数据总数为N ，我们所需要申请的内存大小为 int byte[1 + N / 32 ]，由于int类型数为32bit，只能表示32个数

bitmap表为：

图片.png

三、编程实现

在代码实现之前，我们需要搞清楚两个问题：

1、一个数怎么快速定位到它在byte[]中的下标index。
2、找到了index怎么知道它在byte[index]中的那一位及position是多少。

我们可以把int byte[]的bitmap表看做是一个矩阵，矩阵的每一行有32个数，这个矩阵每一格从0到Max(最大数)，

假设数字为M那么

index = M >> 5 即 M / 32;
position = M & 0x1F 即 M % 31

(1) set(int num) 设置数在byte[]中存在

void set(int num) {
    byte[num >> 5] |= (1 << (num & 0x1F));
}

(2) clean (int num) 重置byte[]所有bit为0

void clean(int num) {
    byte[num >> 5] &= ~(1 << (num & 0x1F));
}

(3) int contain(int num) byte[]是否包含某个数

int contain(int num) {
    return byte[num >> 5] & (1 << (num & 0x1F));
}

举例：N = 100

int a[] = {13, 8, 1, 34, 23, 56, 78, 91, 3, 0, 45, 87, 95};
int length = sizeof(a) / sizeof(int);

//将bitmap所有位设置为0
for (int i = 0; i < N; ++i) {
    clean(i);
}

//bitmap中将待排序数组中值所在的位设置为1
for (int i = 0; i < length; i++)
    set(a[i]);

//输出排序后的结果
for (int i = 0; i < N; ++i) {
    if (contain(i))
        printf("%d  ", i);
}

排序的算法思想：首先在byte[]中设置这个值的bit位为1，进而顺序遍历0 - N 查找这个值是否存在，那么就达到了排序的目的。另外需要注意的是Bitmap算法只能操作非重复数字的排序