[大数据量]BitMap即java.util.BitSet的应用

xusong 2012-08-01

Bitmap算法,

问题:对40亿个数据进行排序,数据类型为int,无相同数据。

思考:关于40亿个数据的排序,首先想如何存储呢?一个int4个字节,也就是160亿个字节,也就是大概有16GB的数据,现在所有的计算机估计

没有这么大的内存吧,所以我们就可以文件归并排序,也可以分段读入数据在进行Qsort,但是都需要不停地读入文件,可以想象不停地读取文件硬件操作会有多么浪费时间。

我们这样都是用4个字节来存储了一个数据,在计算机里都是用二进制进行表示,

例如5:00000000000000000000000000000101

现在引入Bitmap,所谓Bitmap就是用一个bit来表示一个数据。平时32位存储一个数据,我们可以换一种想法,用一个字节32位来存储0-31这32个数据,例如我们对2,1,5,12这四个数据进行由小到大的排序,首先把32位初始化为0,我们可以把这4个数据存储为00000000000000000001000000100110

我们就把32位中的分别把21512位置为1,然后从第0位开始遍历,看相应位是否为1,为1就进行输出,就完成了数据从小到大的排序。

再返回原题应用Bitmap就可以把16GB的存储空间缩小为16GB/32=512M,就可以大大减少读取文件的工作。直接读一次文件存入内存,然后遍历输出就完成了排序。

优点:既大量节省了空间,又把时间复杂度降低到O(n)。

不足:如果数据过于稀疏就会有大量无用遍历,浪费时间。

一个比较简单解释的介绍:

http://blog.csdn.net/lushuaiyin/article/details/7546144

(java.util.BitSet研究(存数海量数据时的一个途径))

相关推荐