位图表示法

1. 把一个不连续集合中，各元素出现的位置表示在一个连续的位置表里，类似bitmap。

    如集合 { 1,2,3,5,8,13 }可以表示成[ 0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0  ]。这样给出一个6，我们可以直接用Array[6]得到一个‘0’表示 6 不在原来的集合里，省去了一个个的把所有元素比较一遍的可能。

    有两个问题，一是元素跨度大，导致空间浪费严重。如集合{3,5,150,75,814,26 }。

    二是用整形一维数组表示的范围有限。如a[1000 0000]至多可存储 1E7 个位置，需要开辟的空间为power(10,7)*sizeof(int)，即时用short int/char空间代价也太高。如果用bit呢？

    考虑到Int32 a[n]每一个元素都由32位二进制数表示，我们把十进制bitmap转化为二进制bitmap，这样一个Int32可以标识32个元素的存在与否，空间压缩至原来的1/32。

4294967295个unsigned int需要2^32/32个Int32(4Byte)，占用内存2^32/32 *4B/1024/1024 = 512M。

怎样转化呢？这就是位运算的问题了。

#define WORD 32
#define SHIFT 5 //移动5个位,左移则相当于乘以32,右移相当于除以32取整
#define MASK 0x1F //16进制下的31
#define N 10000000
unsigned int a[1000];

//m mod n 的位运算：当n = 2的X次幂的时候,m mod n = m&(n-1)

//置位函数——用"|"操作符，i&MASK相当于mod 32操作
void bmp_set(int i)
{
    a[i>>SHIFT]|=(1<<(i&MASK)); //把i的32bit表示的第i位置1
    //i=6, a[6>>5] |= (1<<(6%32)); --> a[0] |= 1<<6;
    //i=33, a[33>>5] |= 1<<(33%32); --> a[1] |= 1<<1;
}

//清除位操作，用&~操作符
void bmp_clear(int i)
{
    a[i>>SHIFT]&=~(1<<(i&MASK));
}

//测试位操作用&操作符
int is_Exist(int i)
{
    return a[i>>SHIFT]&(1<<(i&MASK));
}

2. 应用位图法排序

 

问题：给定不大于整数 n 的 k=1000,0000 个互不相等的整数 ( 2^32 < k < n ) ， 对这些整数进行排序，要求只有1M内存可用。

 

    位图法的set过程虽然是无序的，但是结果恰好是有序的。所谓的位图法排序只是占用空间小罢了。

 

// blog.csdn.net/shuqin1984/article/details/6204224
#include
#include
#include

 

#define BUF_SIZE 10
#define DATA_MAX 10000000
#define MAX_DATA_LEN 10

 

//生成n个最大为max的整数到文件
void genDatas(int n, int max)
{
    int i;
    FILE* fout = fopen("data.txt", "w");
    if(!fout) exit(-1);
   
    for(i = 0; i < n; ++i)
    {
        fprintf(fout, "%d\n", ( rand() + rand() )%max );
    }
    fclose(fout);
}

 

//实际上，bitmap的set()的结果已经是排序的了。
// 0 - (32-1)放在a[0], 32 - 63 放在a[1]
void bmpSort(char* filename)
{
    int i;
    char buf[BUF_SIZE];
   
    FIFE* fin = fopen(filename, "r");
    if(!fin) exit(1);
   
    while( fgets(buf, MAX_DATA_LEN, fin) )
    {
        bmp_set( atoi( buf ) );
    }
    fclose(fin);

    FILE* fout = fopen("output.txt", "w");
    if(!fout) exit(-1);
    for( i = 0; i < DATA_MAX; ++i)
    {
        if( is_Exist(i) )
        {
            fprintf(fout, "%d\n", i);
        }
    }
}

//测试某function的运行时间
void runtime(void (*f)() )
{
    printf("get running time...\n");
   
    clock_t start = clock();
    (*f)();
    clock_t end = clock();
   
    printf("cost time: %8.4f\n", (double)(end - start)/CLOCKS_PER_SEC );
}