定义
位图法即 bitmap，就是用一个 bit 位来标记某个元素对应的 Value，而 Key 即是该元素。由于采用了 Bit 为单位来存储数据，因此在内存占用方面，可以大大节省。适用于大规模数据，但数据状态不是很多的情况。通常是用来判断某个数据存不存在。
实现
应用
求集合的所有子集
集合有 n 个元素，它的子集的个数就是对这 n 个元素做组合，一共有n个位置可以组合，每个位置上该元素可以出现也可以不出现，所以最后总的个数为2的n次方。
这种状态只有两个，一共有 n 个位置的情况，完全适合适用位图。
因此只需要从 0 遍历到 2^n，即可将所有的子集遍历出来。然后再针对每一个值，去出相应位上的 bit 值，0 不出现在子集中，1 出现在子集中。
100亿整型数据去重
整型数据为 32 位最多有 2^32 (42亿多），所以 100 亿整型数据一定有重复的，2^32 个整形用位表示，需要 (2^32)bit == 512MB，需要 512MB 内存表示。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <stdio.h>
#include <stdlib.h>
#define MAX (0xffffffff)
void setBuf(char *buf, unsigned int num)
{
*(buf+(num>>0x3)) |= (0x1<<(num&0x7));
return;
}
unsigned int getBuf(char *buf, int num)
{
unsigned int flag = 0;
flag = ((*(buf+(num>>0x3)) & (0x1<<(num&0x7))) != 0)? 1:0;
return flag;
}
int main(int argc,char **argv)
{
if(argc < 2)
{
printf("usage:./a {0-9}*\n");
return 0;
}
unsigned int index = 1;
unsigned int num;
unsigned int max = 0;
char* buf = (char*)calloc((MAX>>0x3)+1,sizeof(char));
while(index < argc)
{
num = atoi(argv[index]);
max = max>num? max:num;
setBuf(buf,num);
++index;
}
for(index = 0; index <= max; index++)
{
if(getBuf(buf,index) == 1)
{
printf("id:%-10u flag:0x%-16x value:%-10u state:%-2d\n",
index>>0x3,
(unsigned int)buf[index>>0x3],
index,
getBuf(buf,index));
}
printf("process[%u]:%.2f%%\r",index,(float)(index)/max*100);
}
printf("\n");
return 0;
}
|
参考
