位图排序-空间换时间


Warning: Undefined array key "HTTP_REFERER" in /www/wwwroot/prod/www.enjoyasp.net/wp-content/plugins/google-highlight/google-hilite.php on line 58

1M = 1024k
1K = 1024bit
1bit = 8位
一个整数占32位(4bit),那么1M共可存放的整数个数为:1024*1024/4=262144个

题目:一个最多包含n个正整数的文件,每个数都小于n,其中n=10^7,且所有正整数都不重复。求如何将这n个正整数升序排列。
约束:最多有1MB的内存空间可用,有充足的磁盘存储空间。
直接读取所有文件入内存进行排序是不现实的,因为最多有1MB空间,最大可存放的数字是262144个
,可以分段取:从头到尾一段一段的取数据,在0-250000的放入内存并排序输出
从头到尾一段一段的取数据, 在250000-500000的放入内存并输出
从头到尾一段一段的取数据, 在500000-750000的放入内存并输出
从头到尾一段一段的取数据, 在750000-1000000的放入内存并输出

位图法排序:hash对应
定义一字符串,长度为10^7,初始每位为0,每位的顺序对应每个数字,分段读入数字,将对应位设置为1,
如:对于数字3,将此字符串的第三位设置为1即可。
然后输出为1的位数即可,不需排序。
与上边的方法相比,上边的方法要40次全文件扫描,而此方法仅需一次,并用结果不用排序
以空间换时间。

应用范围:1,知道上限。2,数字没有重复

推广:
给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中
unsign int范围为0~2^32-1(4294967295≈5*10^9) 使用位图hash对应5*10^9/8/10^3/10^3 = 625MB.

1. 我们使用625M的字符串。每一位设置为0.
2. 将40亿个unsign int 遍历一遍。使用位图法将字符串中的对应位转化为1。
3. 读取“再给一个数i” 查看bit[i] 是否为1,1则有存在,0则不存在。