位图的介绍以及海量数据的处理

Bitmap

参考:http://taop.marchtea.com/06.07.html
位图法就是bitmap的缩写，所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。
位图是一种很特殊的数据结构，可以利用位图来排序，但是这种排序方法对输入的数据是有比较严格的要求(数据不能重复，大致知道数据的范围)。举个例子，假如有一个集合{3,5,7,8,2,1}，我们可以用一个8位的二进制向量set[1-8]来表示该集合，如果数据存在，则将set相对应的二进制位置1，否则置0.根据给出的集合得到的set为{1,1,1,0,1,0,1,1}，然后再根据set集合的值输出对应的下标即可得到集合{3,5,7,8,2,1}的排序结果。
–百度百科
位图法
位图法的本质是将存储的数转变成一个位，例如int 7,创建一个字节(8位)，将7映射到这个字节的第七位上，这样就减少了内存，因为本来存储一个int需要32位，此时只需要1位。

bitmap排序

给定一个数组[4,7,2,5,3],输出排序后的数组,因为这里面最大的数字是7，所以只需要一个字节就可以容下，初始化的情况

然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位（从左往右数）置为1（可以这样操作 p+(i/8)|(0×01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况，这里默认为Big-ending）,因为是从零开始的，所以要把第五位置为一（如下图）：

最终的情况是:

  6     for(int i = 0; i < pos/BYTESIZE; i++)
#include <memory>
#include <cstdio>
#define BYTESIZE 8

void setBit(char *p, int pos){
    for(int i = 0; i < pos/BYTESIZE; i++)
        p++;

    *p = *p |(0x01<<(pos%BYTESIZE));
    return;
}

void bitMapSort(){
    int num[]={3,5,2,10,6,12,8,14,9};

    const int LEN = 2;

    char *buffer = new char[LEN];

    memset(buffer, 0, LEN);
    for(int i = 0; i < 9; i++){
        setBit(buffer, num[i]);
    }

    for(int i = 0; i < LEN; i++)//每次处理一个字节(Byte)
    {
        for(int j = 0; j < BYTESIZE; j++)//处理该字节中的每个Bit位
        {
        //判断该位上是否是1，进行输出
            if((*buffer&(0x01<<j)) != 0){
                printf("%d ",i*BYTESIZE + j);
            }
        }
        buffer++;
    }
}

海量数据的处理

给40亿个不重复的unsigned int的整数，没有排过序，然后再给一个数，如果快速判断这个数是否在那40亿个数当中。

解体思路:如果每个数都用unsigned int 来表示，那么将会花费,一个数要花费一个unsigned int空间，存在$2^{32}种情况，总的内存空间为$$$2^{32}32/8 = 16G内存$$，使用一个bit位表示一个数字，消耗的内存为$$2^{32} 1 / 8 = 512M$$是以前的$1/32$。
实现:c

申请内存时，需要找到这堆数中的最大值，进而确定所需要的内存，这种连续内存的申请一般用int数组实现，或者用char数组实现。
例如，给出一堆数其中最大的数是1000，那么需要申请的内存大小为int bitmap1000/32 + 1，对应的数如何对应到数组上的位了，例如bitmap[0]的第一位为0，bitmap[1]为1，…,bitmap[i]的第j位就是i32 + j。给定数字888，它所在的bit位就是位于bitmap[888/32]的第[888 % 32]位上
下面是我写的实现*素数筛选的bitmap方法

#include <cstdio>
#include <cstring>
int countPrimes(int n) {
        int LEN = n /32;
        int *arr = new int[LEN + 1];

        //0代表是素数，1代表不是素数
        memset(arr, 0, sizeof(arr));
        arr[0] |= 1;
        arr[0] |= 1<<1 ;
        int m_count = 0;
        for(int i = 2; i < n; i++){
            if(!(arr[i/32] & (1<<(i%32))  ) ){
                m_count++;
                for(int j = i + i; j < n; j += i)
                    arr[j / 32] |= (1<<(j%32));
            }
        }
        delete []arr;
        return m_count;
}

int main(){
    int m = 499979;

    printf("%d\n", countPrimes(m));
    return 0;
}

bitset

c++中有专门的bitset库，可以很方便的来进行bit位操作。
需要注意的是，在构造bitset的时候,一定是一个常数,不能是一个传入的参数

bitset<1000> bitmap;
或者
const int MAX = 100000;
bitset<MAX+1> bit;

用法很类似数组
详细内容参见
参考:http://www.cnblogs.com/dolphin0520/archive/2011/10/19/2217369.html
参考文章:
http://blog.csdn.net/v_july_v/article/details/6279498
http://www.cnblogs.com/pangxiaodong/archive/2011/08/14/2137748.html