海量数据处理(二) 位图

xiaoxiao2021-02-28  91

    位图就是用一个bit为来标记某个元素对应的valuekey是元素,构成键值对。由于使用了bit这个最小单位,所以能够极大的节省内存。

 

    很简单的一个例子,比如现在要对从含有1~100的无序不重复数组排序,那么我们可以申请一个大小为2^7bit的数组(也就是128bit,合16个字节,有一些内存浪费),将其所有置为0。遍历这个无序数组,bit[ arr[i] ] = 1。最后遍历bit数组,写入文件。

 

当然,如果存在着重复现象,位图就不能够使用了。

 

 

难度提高,如果现在给10^7个数据,要求排序,并且内存只给了1M,并且时间越快越好。又该怎么处理呢?

    很明显,内存只给1M,并且对时间有要求,普通的堆排归并排是难以实现的,因为往磁盘里写入文件就要花费很长时间。所以,我们既要缩小内存使用,又要减小往磁盘里写入次数。方法依旧是申请内存,但是10^7 /8/1024/1024 = 1.2M,超过了限定的1M,所以,我们还得继续分。把10^7个数据分成两块,那就是1.2M/2=0.6M,排序后输出。第二次也是如此处理(使用同一块内存),最后再两路归并写入文件里,就实现了排序。

 

 

继续讨论,如果选择有5E个整数,现在要求找出不重复的数。那又该怎么做呢

 

    此时,一个位已经不能够满足 不存在,出现一次,出现多次这三种情况。所以我们选择使用00(不存在)  01(出现一次)  10(出现多次)来表达。

    假定选择给1G内存处理,那么1G = 2^30 BYTE = 2^30*8 BIT = 2^32*2  (最后的2代表使用两位表示一个数据),2^32超过5E,所以够用了。

 

开辟内存后,将其所有置为0,遍历一遍,往里面添,遍历结束以后再遍历一遍,把为01的写入文件里。

 

 

转载请注明原文地址: https://www.6miu.com/read-58312.html

最新回复(0)