我在前面的随笔里已经写过关于处理海量数据的哈希表和Trie的方法了，本文提到的是常用方法之一：Bitmap，测试数据是100万条随机数。
Bitmap是用于处理有限位数的整数，理论上，对于1GB的内存，处理的整数范围大约在0-8,000,000,000内，即一般处理10亿以内，同时也是10位数以内的数据，可实现的操作有存储，排序，查找，删除，查重
而朴素的方法处理10亿的整数需要40GB以上的内存空间，所以，在int用32位表示的机器上，理论内存空间使用比例为1：32，我在下面的代码里用到的测试数据是100万条1亿以内的随机数，完成增删查排序功能。
欢迎有共同学习兴趣的同学加好友探讨学习哦～～^_^
代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 /** 8 * @author:zanzan101 9 */ 10 using namespace std; 11 12 unsigned int* build_bitmap(const unsigned int m) 13 { 14 // 建立一个空bitmap 15 // 我这里是用1位表示一条记录，没有查重的功能，如果用2位表示，或者使用双bitmap，则可以实现查重 16 unsigned int* p = new unsigned int[1 + m/(8*sizeof(unsigned int))]; 17 memset(p, 0, m/8 + sizeof(unsigned int)); 18 return p; 19 } 20 21 void set_bit(unsigned int* arr, unsigned int n) 22 { 23 // 常数时间插入任何一个数 24 unsigned int pos = n/(8*sizeof(unsigned int)); 25 unsigned int tmp = n%(8*sizeof(unsigned int)); 26 unsigned int msk = (unsigned int)1 << tmp; 27 arr[pos] |= msk; 28 } 29 unsigned int get_bit(unsigned int* arr, unsigned int n) 30 { 31 // 常数时间查找任何一个数 32 unsigned int pos = n/(8*sizeof(unsigned int)); 33 unsigned int tmp = n%(8*sizeof(unsigned int)); 34 unsigned int msk = (unsigned int)1 << tmp; 35 tmp = arr[pos]; 36 tmp &= msk; 37 return tmp>0?1:0; 38 } 39 void delete_bit(unsigned int* arr, unsigned int n) 40 { 41 // 常数时间删除任何一个数 42 unsigned int pos = n/(8*sizeof(unsigned int)); 43 unsigned int tmp = n%(8*sizeof(unsigned int)); 44 unsigned int msk = (unsigned int)1 << tmp; 45 msk = ~msk; 46 arr[pos] &= msk; 47 } 48 49 50 void save_bitmap(unsigned int* arr, unsigned int m) 51 { 52 ofstream output_file; 53 output_file.open("D:\\test_bitmap___.txt"); 54 if(!output_file.is_open()) 55 return; 56 57 // bitmap 本身就是有序的，只需从前往后依次遍历访问即可有序输出 58 for(unsigned int i = 0; i < m; i++) 59 if(get_bit(arr, i)) 60 output_file << i << endl; 61 } 62 63 void print_bitmap(unsigned int* arr, unsigned int m) 64 { 65 if(m > 100) 66 { 67 printf("数据量过大，不便于在屏幕上显示，已存入文件：D:\\test_bitmap___.txt\n"); 68 save_bitmap(arr, m); 69 return; //数据量过大时，还是保存到文件里比较好～～～ 70 } 71 72 // bitmap 本身就是有序的，只需从前往后依次遍历访问即可有序输出 73 for(int i = 0; i < m; i++) 74 if(get_bit(arr, i)) 75 printf("%8d ", i); 76 printf("\n"); 77 } 78 79 unsigned int big_rand(const unsigned int max) 80 { 81 unsigned int sum = 0; 82 int tmp = max/RAND_MAX; 83 if(!tmp) 84 return rand()%max; 85 86 int round = rand()%tmp; 87 sum += RAND_MAX*round; 88 sum += rand(); 89 return sum; 90 } 91 92 int main() 93 { 94 timeb time_begin; 95 timeb time_end; 96 unsigned int seconds; 97 unsigned int miseconds; 98 99 const unsigned int MAX = 100000000;100 unsigned int* bitmap = build_bitmap(MAX);101 srand(time(0));102 // 测试插入功能103 // 插入100万条随机数104 printf(">> 插入：100万条%u以内的随机数\n", MAX);105 for(int i = 0; i < 1000000; i++)106 set_bit(bitmap, big_rand(MAX));107 108 // 测试排序功能109 // bitmap本身就是有序的110 printf(">> 排序：\n");111 print_bitmap(bitmap, MAX);112 113 // 测试查找功能114 printf(">> 查找：100个%u以内的随机数\n由于是随机数，其实找到每个数的概率是0.01，下面只显示找到的情况\n", MAX);115 ftime(&time_begin); 116 int ran;117 for(int i = 0; i < 100; i++)118 {119 ran = big_rand(MAX);120 if(get_bit(bitmap, ran))121 printf("\t%d存在！\n", ran);122 // 由于找到的概率比较小，下面就不显示没有找到的情况了123 // else 124 // printf("\t%d不存在！\n", ran);125 }126 ftime(&time_end);127 seconds = time_end.time - time_begin.time;128 miseconds = time_end.millitm - time_begin.millitm;129 miseconds = seconds * 1000 + miseconds;130 printf(">> 100次查找总共耗时：%u毫秒\n", miseconds);131 132 // 现插入现找133 ran = big_rand(MAX);134 set_bit(bitmap, ran);135 printf(">> 查找：现插入随机数%d，再查找它\n", ran);136 137 if(get_bit(bitmap, ran))138 printf("\t%d存在！\n", ran);139 else140 printf("\t%d不存在！\n", ran);141 142 // 测试删除功能143 // 删除刚才插入的那个随机数144 145 printf(">> 删除：刚才插入的那个随机数%d删掉，之后再查找它\n", ran);146 delete_bit(bitmap, ran);147 if(get_bit(bitmap, ran))148 printf("\t%d存在！\n", ran);149 else150 printf("\t%d不存在！\n", ran);151 delete[] bitmap;152 system("pause");153 return 0;154 }
输出结果：
>> 插入：100万条100000000以内的随机数>> 排序：数据量过大，不便于在屏幕上显示，已存入文件：D:\test_bitmap___.txt>> 查找：100个100000000以内的随机数由于是随机数，其实找到每个数的概率是0.01，下面只显示找到的情况 92857475存在！ 19411480存在！ 58457743存在！ 37785850存在！ 26831485存在！>> 100次查找总共耗时：0毫秒>> 查找：现插入随机数82440561，再查找它 82440561存在！>> 删除：刚才插入的那个随机数82440561删掉，之后再查找它 82440561不存在！请按任意键继续. . .