当前位置:首页 > 开发 > 编程语言 > Java > 正文

JAVA海量数据处理之二(BitMap)

发表于: 2012-06-20   作者:周凡杨   来源:转载   浏览:
摘要:        路漫漫其修远兮,吾将上下而求索。想要更快,就要深入挖掘 JAVA 基础的数据结构,从来分析出所编写的 JAVA 代码为什么把内存耗尽,思考有什么办法可以节省内存呢? 啊哈!算法。这里采用了 BitMap 思想。   首先来看一个实验: 指定 VM 参数大小: -Xms256m -Xmx540m

       路漫漫其修远兮,吾将上下而求索。想要更快,就要深入挖掘 JAVA 基础的数据结构,从来分析出所编写的 JAVA 代码为什么把内存耗尽,思考有什么办法可以节省内存呢? 啊哈!算法。这里采用了 BitMap 思想。

 

首先来看一个实验:

指定 VM 参数大小: -Xms256m -Xmx540m

 

import java.util.TreeSet;

public class Test {

    public static void main(String[] args) {

       TreeSet set = new TreeSet();

       for(long i=10000000000L;i<900000000000L;i++){

           set.add(i);

           System.out.println("i="+i);

       }

    }

}
 

一个简单的 FOR 循环,运行该类,可以看到当输出: i=10011703526 的时候报错了

 

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
 

如果把上面的例子中的   set.add(i);  修改成 set.add(i+"");    那结果又是什么呢?

当输出 i=10005851762 时报了同样的错,内存溢出。为什么往内存里放 Long 型的比 String 型的多了近一半的数据呢?

 

1024 个字节 =1KB , 1024KB=1MB , 1024MB=1GB 

 

 

Long 8 个字节 (64 ) 11703526 Long 型数据约 91433KB  89M

String 内部是由 char 构成,一个 char 2 个字节, 11 位的数据是 22 个字节, 5851762 String 型数据 约合 125721KB 122M

11 位的 String 数据比 11 位的 Long 型数据要占内存多。

 

总结:内存溢出是由于自己没有做到节省内存,用 64 位的 Long 型数据或 176 位的 String 型数据来存储 11 位的数据。那能不能用内存里的 11 位即 11bit 来表示 11 位数据呢?

 

还是上一章(《 JAVA 海量数据处理之一》)的问题,我还能再快吗?答案是可以的!

我在编码中改用了 BitMap 思想,使效率又提升了一倍。

 

【什么是Bit-map

 

所谓的Bit-map 就是用一个bit 位来标记某个元素对应的Value , 而Key 即是该元素。由于采用了Bit 为单位来存储数据,因此在存储空间方面,可以大大节省。

详细资料可参考:

http://blog.csdn.net/hit_kongquan/article/details/6255673

http://wansishuang.appspot.com/?p=35003

 

例子:用位向量来表示数据: 1 3 6 10 100

 

import java.util.BitSet;

public class BitTest {

    public static void main(String[] args) {

       // 1 3 6 10 100

         BitSet bitSet = new BitSet(100);

         bitSet.set(1,true);

         bitSet.set(3,true);

         bitSet.set(6,true);

         bitSet.set(100,true);

         for(int i=0;i<bitSet.size();i++){

         boolean b = bitSet.get(i);

         if(b){

              System.out.println(i);

         }

         }

    }

}
 

BitMap 来实现数据过滤结果:

 

      * 371M 的文件( 3000 万的数据)   过滤数据耗时 : 27375 毫秒

      * 520M 的文件( 4200 万的数据)   过滤数据耗时 : 62000 毫秒 

 其中把 4200 万的数据用 BitSet 操作耗时约 20-30 秒,写入目标文件约 30 秒。所以 1 分钟可以搞定 4200 万的数据。效率已经得到了极大的提高。

 

 

 

 

 

 

 

JAVA海量数据处理之二(BitMap)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
一:简介 所谓的BitMap就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了bi
教你如何迅速秒杀掉:99%的海量数据处理面试题! 作者:July 出处:结构之法算法之道blog 前言 一般
有2.5E个整数数据,找出其中重复的,给定的内存是600M。 由于题目描述的不够清晰,现在假定整数指的
【什么是堆】 概念:堆是一种特殊的二叉树,具备以下两种性质 1)每个节点的值都大于(或者都小于,
作者: Fenng | 可以转载, 转载时务必以超链接形式标明文章原始出处和作者信息及版权声明 网址: http
项目组里因为需要,现要开发一个数据过滤软件,针对文本文件 (txt 文件 ) ,文本文件里的数据是 11
好几个地方看到这个 Facebook - Needle in a Haystack: Efficient Storage of Billions of Photos,
项目组里因为需要,现要开发一个数据过滤软件,针对文本文件 (txt 文件 ) ,文本文件里的数据是 11
Facebook 海量数据处理 作者: Fenng | 可以转载, 转载时务必以超链接形式标明文章原始出处和作者信
1.hashing 适用范围:快速查找,删除的基本数据结构,通常需要总数据量可以放入内存。 这里的hashin
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号