位图算法

位图法定义

位图法就是bitmap的缩写，所谓bitmap，是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

例如，要判断一千万个人的状态，每个人只有两种状态：男人，女人，可以用0，1表示。那么就可以开一个int数组，一个int有32个位，就可以表示32个人。操作的时候可以使用位操作。

欢迎关注我的个人博客：www.wuyudong.com, 更多云计算与大数据的精彩文章

unsigned int bit[N];

在这个数组里面，可以存储 N * sizeof(int) * 8个数据，但是最大的数只能是N * sizeof(int) * 8 - 1。假如，我们要存储的数据范围为0-15，则我们只需要使得N=1，这样就可以把数据存进去。如下图：

数据为【5，1，7，15，0，4，6，10】，则存入这个结构中的情况为

位图法应用 一、给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中

申请512M的内存

一个bit位代表一个unsigned int值

读入40亿个数，设置相应的bit位

读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在

二、使用位图法判断整形数组是否存在重复

判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循环法就不可取了。位图法比较适合于这种情 况，它的做法是按照集合中最大元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上1，如遇到 5就给新数组的第六个元素置1，这样下次再遇到5想置位时发现新数组的第六个元素已经是1了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组 初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高 一倍。

#include stdio.h 

#include stdlib.h 

#include string.h 

#include stdbool.h 

bool hasDuplicatedItem(int *a, int len)

 int length, max, i; 

 length = len;

 max = a[0];

 for(i = 1; i length; i++){

 if(a[i] max)

 max = a[i];

 int *arr;

 arr = (int*)malloc(sizeof(int) * (max + 1));

 for(i = 0; i length; i++){

 if(arr[a[i]])

 return true;

 else

 arr[a[i]] = 1;

 return false;

int main()

 int length;

 int test[] = {0,1,2,3,45,12,13};

 length = (sizeof(test) / sizeof(test[0]));

 if(hasDuplicatedItem(test, length))

 printf("hasDuplicatedItem!\n");

 else

 printf("hasNoDuplicatedItem!\n");

 return 0;

}

三、使用位图法进行整形数组排序

首先遍历数组，得到数组的最大最小值，然后根据这个最大最小值来缩小bitmap的范围。这里需要注意对于int的负数，都要转化为unsigned int来处理，而且取位的时候，数字要减去最小值。

#include stdio.h 

#include stdlib.h 

#include string.h 

#include stdbool.h 

void bitmapSort(int *a, int len)

 int length, max, min, i, index; 

 length = len;

 min = max = a[0];

 //找出数组最大值 for(i = 1; i length; i++){

 if(a[i] max){

 max = a[i];

 if(min a[i]) {

 min = a[i];

 //得到位图数组 int *arr;

 arr = (int*)malloc(sizeof(int) * (max - min + 1));

 for(i = 0; i length; i++){

 index = a[i] - min;

 arr[index]++;

 //重整a中的元素 int arr_length;

 arr_length = max - min + 1;

 index = 0;

 for(i = 0; i arr_length; i++){

 while(arr[i] 0){

 a[index] = i + min;

 index++;

 arr[i]--;

void print(int *a, int n)

 int i;

 for(i = 0; i i++) {

 printf("%d ", a[i]);

 printf("\n");

int main()

 int length;

 int test[] = {50,1,26,3,45,12,13};

 length = sizeof(test) / sizeof(test[0]);

 print(test, length);

 bitmapSort(test, length);

 print(test, length);

 return 0;

}

四、位图法存数据

输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=10,000,000 输入文件中没有重复的整数，没有其他数据与该整数相关联。

输出： 按升序排列这些数。

约束：有 1MB多（不超过2MB） 的内存空间可用，有充足的硬盘空间。

#include stdio.h 

#define BITSPERWORD 32

#define SHIFT 5

#define MASK 0x1F

#define N 10000000

int a[1 + N/BITSPERWORD];

/* a[i SHIFT]是第i位应该在第几个int上 */ /* (1 (i MASK))是第i位在该int上的第几个bit */ void set(int i)

 a[i SHIFT] |= (1 (i MASK));

void clr(int i)

 a[i SHIFT] = ~(1 (i MASK));

int test(int i)

 return a[i SHIFT] (1 (i MASK));

int main()

 int i;

 for(i = 0; i i++)

 clr(i);

 while(scanf("%d", i) != EOF)

 set(i);

 for(i = 0; i i++)

 if(test(i))

 printf("%d\n", i);

 return 0;

}

三种集成学习算法原理及核心公式推导 本文主要介绍3种集成学习算法的原理及重要公式推导部分，包括随机森林（Random Forest）、自适应提升（AdaBoost）、梯度提升（Gradient Boosting）。仅对重点理论和公式推导环节做以简要介绍。