空间管理您的位置: 51Testing软件测试网 » 笑遍世界的测试技术 » 日志

All things are difficult before they are easy. 没有软件的裸机是一具僵尸，没有硬件的软件是一个幽灵。2012，专注于Linux和C语言，关注自动化、性能测试，关注开源社区和开源测试工具、方法，尝试测试团队管理！

位图排序原理及实现（C语言版）

上一篇 / 下一篇 2010-11-16 20:54:01 / 精华(1) / 置顶(1) / 个人分类：C/C++

查看( 2343 ) / 评论( 0 ) / 评分( 0 / 0 )

在《编程珠玑》的第一章，就是相当的精彩，这个位图排序就是出自那里。书中讲到的位图排序非常的巧妙（时间和空间都时非常的节省），而这巧妙是来源于对实际问题和数据的透彻分析，然后选取了一种高效的解决方案。结合网上的一些资料以及自己的程序实现来简单记录一下吧。
1.位图的理解
我们都明白图形格式中位图储存方式,其实就是以象素为单位的小方块,一格一格的纵横累积起来. 每一个小方块代表一种颜色,当然,如果对于黑白的二色图来说更加简单,只需要一个bit位即可表示. 这和我们的数据在计算机中的存储格式是相似的,内存条的也像是一格一格的bit位纵横交错而成. 因为这样的启发,我们发现一个个bit位象列队一样排列着,顺序相当严谨,如果我们的数据能够通过一种转换方式(逻辑上)能有序的和bit位一一对应起来的话,那么我们按照bit位的顺序把它输出来不就是排序的数据集合吗?
2.索引的概念
通过上面的描述,我们很容易联想到一样东西-索引。索引对于我们数据库的使用无疑相当重要,以至于现在很多数据量巨大的单表查询的性能完全仰仗于它.它和位图的相似性在于:如果我们把每一行数据看作一个单位的数据,那么索引可以看作是该数据通过一种转化方式映射到某个存储空间,如果数据的顺序和索引的顺序是一致的话,那么当我们按序对该存储空间访问时,就得到了有序的数据集.当然很多情况下,索引都是数据的一部分,然而在Oracle中有函数索引的概念, 它就完全表达了这种转化方式和映射关系了.
3.排序的一种巧妙方法——位图排序
位图天生和排序分不开,因为它是最本质的有序载体. 问题如下：
输入：一个包含n个正整数的文件，每个正整数小于n,n等于10的7次方（一千万）。并且文件内的正整数没有重复和关联数据。
输出：输入整数的升序排列
约束：限制在1M左右内存，充足的磁盘空间，要求在10s钟内完成排序
分析如下：假设整数占32位，1M内存可以存储大概250000个整数，第一个方法就是采用基于磁盘的合并排序算法，第二个办法就是将0-9999999切割成40 个区间，分40次扫描（10000000/250000)，每次读入250000个在一个区间的整数，并在内存中使用快速排序。书中提出的第三个解决办法，是采用bitmap（或者称为bit vector）来表示所有数据集合（注意到条件，数据没有重复），这样就可以一次性将数据读入内存，减少了扫描次数。
联想: 抓住问题的意义,电话号码在本问题上的一个现实意义就是该电话号码在整个电话号码集合上的位子,更具有特征的是,电话号码本身就反应了这么一个位子信息. 如果我们设立1000万个bit位,每一位表示该位置上电话号码是否存在(设定1为存在,0-不存在),位号就是电话号码本身,那么我们遍历所有的位,输出位号为1的电话号码,不就是排序的电话号码吗?巧妙之处: 因为我们利用了数据本身的意义!
算法的伪代码如下：
阶段1：初始化一个空集合
for i=[0,n)
bit[i]=0;

阶段2：读入数据i，并设置bit[i]=1
    for each i in the input file
           bit[i]=1;
阶段3：输出排序的结果
   for i=[0,n)
          if bit[i]==1
              write i on the output file

算法的时间复杂度为O(N)

我们看到了位图排序的高效与精彩巧妙之处,对于我们的数据进行排序的时候,可不可以思考一下:分析我们的数据特征很关键,任何问题可能都是从分析特征找突破口的,考虑一下我们的数据存不存在一种转化方法使得他能映射到这种数字关系上来.这里的无重复的大量数据使得我们使用位图排序将会使得效率大幅提高。
4.位图排序的代码实例（C语言实现）：
此处仅通过产生的20个随机数(0~9999999)用位图排序的方法进行了排序。这里有两个点是应该注意的：
4.1 这里最原始的位图排序不支持有相同数字出现的情况，多个相同数字的出现，排序后会忽略多个相同数字的存在在，只保留一个。其实，稍微修改以下程序，也时可以实现兼容这种情况的，比如说，可以增加一个数组count[10000000]来对bitmap数组中值为1的个数进行计数即可。（当然这样会超出1MB的内存空间，不过原题规定时无重复的数据，故时可以在1MB内存限制条件下实现的）
4.2 是个题外话，我在产生测试用的随机数时，最开始我把srand随机数种子放在产生随机数myRand()函数中，则每次调用都会产生几乎同一个随机数。后来才了解到，随机数种子应该放在调用myRand()的主函数中，这样才能产生随机数。（其实，也可能产生相同的数字，只是我在0～9999999范围内产生20个随机数，它们重复的概率比较低的）另外，为了防止防止重复数据产生了，我确不知道，我也将排序后的数字个数打印出来，如果排序后数字个数比排序前要少，则排序输入的数据中有重复数字。

//位图排序法，时空高效的至高境界
#include <stdio.h>
#include <math.h>
#include <time.h>

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
#define M 20
int a[1 + N/BITSPERWORD];

//置a[i>>SHIFT]的第(i & MASK)位为1，也就是位数组的第i位为1
void set(int i){
    a[i >> SHIFT] |= (1<<(i & MASK));
}

//置a[i>>SHIFT]的第(i & MASK)位为0,也就是位数组的第i位为0
void clr(int i){
    a[i >> SHIFT] &= ~(1<<(i & MASK));
}

//测试位数组的第i位是否为1
int test(int i){
    return a[i >> SHIFT] & (1<<(i & MASK));
}

int myRand()   /* 产生一个0~1之间的随机数 */
{
int num;
num = rand() % 10000000;
return num;
}

int main(void) {
    int i;
    int j;
    int arr[M];
    int count=0;
    for (i = 0; i < N; i++) {
        clr(i);
    }
    //while (scanf("%d", &i) != EOF) {
    //    set(i);
    //}
    srand( (unsigned)time( NULL ) );     //注意这个随机数种子不能放在产生随机数myRand()函数中，否则每次调用都会产生几乎同一个随机数
    printf("The count of array is %d:\n",M);
    for (j = 0; j < M; j++) {    //供简单的正确性测试
        arr[j]=myRand();            //注意，输入的数不能重复     //否则当只输入一次
    printf("%d\t",arr[j]);
    }

    for (j = 0; j < M; j++) {    //供简单的正确性测试
        set(arr[j]);
    }

    printf("\nAfter Sorted:\n");
    for (i = 0; i < N; i++) {
        if (test(i)) {
        printf("%d\t", i);
        count++;
    }
    }
    printf("\nAfter sorted count is %d\n",count);    //打印出排序后的数字个数，如果有重复数字作为输入，则排序后数字的个数会比排序前少。
    return 0;
}

参考资料：
http://www.cnblogs.com/djbone/archive/2008/08/20/1271816.html
http://www.cnblogs.com/wangtianxj/articles/1514982.html

位图排序原理及实现（C语言版）

相关阅读:

用户菜单

我的栏目

标题搜索

日历

我的存档

数据统计

RSS订阅