返回> 网站首页

编程珠玑--位图法排序

yoours2010-11-05 15:46:29 阅读 1127

简介一边听听音乐，一边写写文章。

题目：一个最多包含n个正整数的文件，每个数都小于n，其中n=10^7,且所有正整数都不重复。求如何将这n个正整数升序排列。
约束：最多有1MB的内存空间可用，有充足的磁盘存储空间。

分析:这个题目的最大亮点是只有1MB的内存空间，我们可以通过计算得出，内存只有1MB可以储存的int（4byte）有10^3*10^3/4=250 000个号码。而包含正整数的文件约为10^7个int大小。这意味着无法将所有文件中的正整数一次读取进入到内存空间中去进行排序算法。因此衍生出下面两种方法：
方法2（位图法）：
我们想使用hash映射，将对应的正整数映射到位图集合中。即将正整数映射到bit集合中，每一个bit代表其映射的正整数是否存在。
比如{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
我们可以使用具有10^7位的字符串来表示这个文件。其中，当且仅当整数i在文件中存在时候，第i位为1

位图法方法：

创建有个10^7位（10^7/8/4≈1MB）的字符串，并将其每一bit设置为0；
读取包含正整数的文件，对每一个i，将内存中bit 位设置成1.
按位顺序读取字符串。当读取到bit[j] 为1时输出（int）j。

根据位图法演变解决以下QQ面试题目：
给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中

unsign int范围为0~2^32-1(4294967295≈5*10^9) 使用位图hash对应5*10^9/8/10^3/10^3 = 625MB.