位图排序
最后更新于：2022-04-01 21:40:02
主要是阐述位图在排序中的使用.
### 问题描述
位图排序是一种效率极高(复杂度可达O(n))并且很节省空间的一种排序方法，但是这种排序方法对输入的数据是有比较严格的要求(数据不能重复，大致知道数据的范围)。位图排序即利用位图或者位向量来表示集合。可以说算法中用到位操作的很多，因为速度快，空间小，比如哈有bitmask dp。文中的问题可以抽象为对[1:10000000]区间内的随机排列进行排序，而且内存限制在1m左右。外部排序可能是第一个闪近脑子里的答案。作者在文中的解法就是利用bitmap算法，每一个bit代表一个数字，用10000000个比特位就可以将所有的数字表示出来。然后遍历，设置1为存在，0为不存在，然后顺序输出即可。
而且是更加贴近现实的：“你手中有一百万张纸，每张纸上是一个大学生的资料，你需要将他们按照年纪排序，你怎么做？谁更聪明，一个计算机科学博士还是你的母亲？在 Google 从事多年面试工作的 Paul Tyma 将这个问题交给他的母亲解答。从未学过计算机科学的 Tyma 夫人做的比受过高等教育的人还要出色。许多应试者会建议快速排序算法，而 Tyma 夫人的答案比他们的方法要快上 20 倍。有时候创造力只是常识。答案：将纸堆上的第一张拿下来，看看年龄，如果他是 21 岁，就放到 21 岁的纸堆里，如果下一个是 19 岁，就放到 19 岁的纸堆里。如此这般，任何记录你只需要看一次，当你完成后，将不同年龄的纸堆顺序排列即可。”不过这类问题的特殊性就是数据范围比较集中，比如1到10000000，年龄一般都在1-200之间，后一个题带有明显的计数排序和hash的影子。
再举个例子，假如有一个集合{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}的排序结果。这个就是位图排序的原理。****
### **实现概要**
由是观之，用位图或位向量表示集合。可用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合。例如，可以用如下字符串来表示集合{1, 2, 3, 5, 8, 13}：
|
~~~
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
~~~
|
|-----|
代表集合中数值的位都置为1，其他所有的位都置为0。
在我们的实际问题中，每个7位十进制整数表示一个小于1 000万的整数。我们使用一个具有1 000万个位的字符串来表示这个文件，其中，当且仅当整数i在文件中存在时，第i位为1。（那个程序员后来找到了200万个稀疏位，习题5研究了最大存储空间严格限制为1 MB的情况。）这种表示利用了该问题的三个在排序问题中不常见的属性：输入数据限制在相对较小的范围内；数据没有重复；而且对于每条记录而言，除了单一整数外，没有任何其他关联数据。
若给定表示文件中整数集合的位图数据结构，则可以分三个自然阶段来编写程序。第一阶段将所有的位都置为0，从而将集合初始化为空。第二阶段通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。第三阶段检验每一位，如果该位为1，就输出对应的整数，由此产生有序的输出文件。令n为位向量中的位数（在本例中为10 000 000），程序可以使用伪代码表示如下：
~~~
/* phase 1: initialize set to empty */
for i = [0, n)
bit[i] = 0
/* phase 2: insert present elements into the set */
for each i in the input file
bit[i] = 1
/* phase 3: write sorted output */
for i = [0, n)
if bit[i] == 1
write i on the output file
~~~
### 位图排序的应用
1. 给40亿个不重复的unsigned int的整数，没有排过序，然后再给一个数，如果快速判断这个数是否在那40亿个数当中。因为unsigned int数据的最大范围在在40亿左右，40*10^8/1024*1024*8=476，因此只需申请512M的内存空间，每个bit位表示一个unsigned int。读入40亿个数，并设置相应的bit位为1.然后读取要查询的数，查看该bit是否为1，是1则存在，否则不存在。
2. 给40亿个unsigned int的整数，如何判断这40亿个数中哪些数重复？同理，可以申请512M的内存空间，然后读取40亿个整数，并且将相应的bit位置1。如果是第一次读取某个数据，则在将该bit位置1之前，此bit位必定是0；如果是第二次读取该数据，则可根据相应的bit位是否为1判断该数据是否重复。
由于在C语言中没有bit这种数据类型，因此必须通过位操作来实现。假如有若干个不重复的正整数，范围在[1-100]之间，因此可以申请一个int数组，int数组大小为100/32+1。因此要进行置1位操作，必须先确定逻辑位置：字节位置(数组下标)和位位置。
字节位置=数据/32;(采用位运算即右移5位)
位位置=数据%32;(采用位运算即跟0X1F进行与操作)。
### C实现代码：
~~~
#include
#define MAX 1000000
#define SHIFT 5
#define MASK 0x1F
#define DIGITS 32
int a[1+MAX/DIGITS];
void setbit(int n) //将逻辑位置为n的二进制位置为1
{
a[n>>SHIFT] |= (1<<(n&MASK)); //n>>SHIFT右移5位相当于除以32求算字节位置，n&MASK相当于对32取余即求位位置，
} //然后将1左移的结果与当前数组元素进行或操作，相当于将逻辑位置为n的二进制位置1.
void clearbit(int n)
{
a[n>>SHIFT] &= ~(1<<(n&MASK)); //将逻辑位置为n的二进制位置0，原理同set操作
}
int test(int n)
{
return a[n>>SHIFT] & (1<<(n&MASK)); //测试逻辑位置为n的二进制位是否为1
}
int main(int argc, char *argv[])
{
int i,n;
for(i=0;i
#include
#define MAX 1000000
bitset bit;
int main(int argc, char *argv[])
{
using namespace std;
int n,i;
while(scanf("%d",&n)!=EOF)
{
bit.set(n,1);
}
for(i=0;i<=MAX+1;i++)
{
if(bit[i]==1)
printf("%d ",i);
}
return 0;
}
~~~
**转载请注明出处：**[http://blog.csdn.net/utimes/article/details/8759635](http://blog.csdn.net/utimes/article/details/8759635)
';