偶然看到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算法只能操作非重复数字的排序
网友评论