`
MyEyeOfJava
  • 浏览: 1141528 次
  • 性别: Icon_minigender_1
  • 来自: 北京
博客专栏
7af2d6ca-4fe1-3e9a-be85-3f65f7120bd0
测试开发
浏览量:70782
533896eb-dd7b-3cde-b4d3-cc1ce02c1c14
晨记
浏览量:0
社区版块
存档分类
最新评论

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

阅读更多
Bitmap算法,
问题:对40亿个数据进行排序,数据类型为 int,无相同数据。
思考:关于40亿个数据的排序,首先想如何存储呢?一个int 4个字节,也就是160亿个字节,也就是大概有16GB的数据,现在所有的计算机估计
没有这么大的内存吧,所以我们就可以文件归并排序,也可以分段读入数据在进行Qsort,但是都需要不停地读入文件,可以想象不停地读取文件硬件操作会有多么浪费时间。

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

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

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

优点:既大量节省了空间,又把时间复杂度降低到O(n)。
不足:如果数据过于稀疏就会有大量无用遍历,浪费时间。


一个比较简单解释的介绍:
http://blog.csdn.net/lushuaiyin/article/details/7546144
(java.util.BitSet 研究(存数海量数据时的一个途径))
分享到:
评论

相关推荐

    RoaringBitmap-0.7.45-API文档-中英对照版.zip

    标签:roaringbitmap、RoaringBitmap、中英对照文档、jar包、java; 使用方法:解压翻译后的API文档,用浏览器打开“index.html”文件,即可纵览文档内容。 人性化翻译,文档中的代码和结构保持不变,注释和说明精准...

    RoaringBitmap-0.7.45-API文档-中文版.zip

    标签:roaringbitmap、RoaringBitmap、中文文档、jar包、java; 使用方法:解压翻译后的API文档,用浏览器打开“index.html”文件,即可纵览文档内容。 人性化翻译,文档中的代码和结构保持不变,注释和说明精准翻译...

    安卓开发-Android 主流的图片浏览的全屏缩放效果SmoothImageDemo软件源码

    import android.graphics.Bitmap.Config; import android.os.Build; import android.os.Bundle; import android.os.Environment; import android.util.Log; import android.view.View; import android.view....

    生成字体图片工具Bitmap Font Builder.exe

    Bitmap Font Builder.exe生成字体图片工具Bitmap Font Builder.exe

    绘制用纹理填充的图形,C#源代码Bitmap bitmap = new Bitmap("..\\..\\test.jpg");

    绘制用纹理填充的图形,C#源代码Bitmap bitmap = new ... e.Graphics.DrawImage(bitmap, 0, 0, bitmap.Width, bitmap.Height); e.Graphics.DrawEllipse(texturedPen, 100, 20, 200, 100); VisualStudio2008创建

    Bitmap_transform.rar_Bitmap Transform_bitmap

    在计算机图形学和图像处理领域,Bitmap(位图)是一种常见的图像格式,它存储的是像素的二维数组。Bitmap Transform指的是对位图进行的各种变换操作,包括但不限于缩放、旋转、平移等。在这个"Bitmap_transform.rar_...

    Android下利用Bitmap切割图片

    在实际应用中,我们可能需要根据需求动态调整图片大小或比例,这时可以使用Bitmap.createScaledBitmap方法。这个方法可以将Bitmap缩放到指定的尺寸,同时保持原图像的比例: ```java // 缩放Bitmap至新的尺寸 ...

    androidbitmap的用法.pdf

    最后,使用`Bitmap.createBitmap()`创建一个新的Bitmap,这个新的Bitmap就是按照指定比例缩放后的结果。 在实际开发中,需要注意Bitmap的内存管理。由于Bitmap占用大量内存,不恰当的使用可能导致内存溢出。因此,...

    处理bitmap内存溢出问题

    当应用程序尝试加载或操作一张超出虚拟机内存预算的`Bitmap`时,系统会抛出`java.lang.OutOfMemoryError: bitmap size exceeds VM budget`异常,导致应用崩溃。为了解决这个问题,开发者需要采取一些策略来优化图片...

    RoaringBitmap, 在Java中,一个更好的压缩 bitset.zip

    RoaringBitmap, 在Java中,一个更好的压缩 bitset RoaringBitmap Bitsets,也称为位图,通常用作快速数据结构。 不幸的是,他们可以使用太多的内存。 为了补偿,我们经常使用压缩位图。咆哮位图是压缩位图,它比传统...

    C#中bitmap、stream、byte类型转换实例

    bitmap.Save(memoryStream, ImageFormat.Jpeg); // 将Bitmap保存到MemoryStream ``` ### Stream到byte[]转换 MemoryStream是一个实现了Stream接口的类,它可以直接访问其内部的字节数组。我们可以使用ToArray()...

    bitmap-BMP.rar_BITMAP bmp_bmp类

    bitmap.LoadImage(_T("path_to_your_bitmap.bmp"), LR_LOADFROMFILE); ``` 显示BMP位图: MFC中的CView类通常用于显示文档内容,我们可以重写它的`OnDraw`方法来绘制位图。首先,确保你的视图类继承自`CView`,...

    简析Bitmap文件格式.rar_bitmap_blanket477

    在编程和软件开发中,处理Bitmap文件需要使用特定的库或API,例如在Java中使用`java.awt.image.BufferedImage`,在C#中使用`System.Drawing.Bitmap`,而在Python中可以使用PIL(Pillow)库。这些库提供了读取、写入...

    Activity跳转时传递Bitmap对象

    bitmap = Bitmap.createBitmap(imageView.getWidth(), imageView.getHeight(), Bitmap.Config.ARGB_8888); Canvas canvas = new Canvas(bitmap); imageView.draw(canvas); // 将ImageView的内容绘制到Bitmap } ``...

    yuv转bitmap的动态库.so

    Bitmap bitmap = Bitmap.createBitmap(640, 480, Bitmap.Config.ARGB_8888); YuvToBitmap.convertYuvToBitmap(yuvData, 640, 480, bitmap); ``` 5. **优化性能**:考虑到Android的内存限制,尽可能使用高效的数据...

    本示例绘制位图,分两种方式1. 绘制Bitmap对象2.使用Drawable.draw方法绘制位图

    本示例 演示绘制位图,分两种方式 1. 绘制Bitmap对象 2.使用Drawable.draw方法绘制位图 详情请参见 http://blog.csdn.net/aduovip/article/details/6722949

    java 原生包 BitSet 源码

    Java中BitSet类是Java集合框架的一部分,它是一种用于处理位操作的高级数据结构。BitSet可以看作是一个只存储布尔值的数组,但相比于原始的布尔数组,BitSet更加内存高效,因为它以64位的块(word)来存储多个布尔值...

    BitmapUtil.java

    Bitmap-->List

    electric-minarea-bitmapjava-0.2.jar

    jar包,官方版本,自测可用

    图片缓存机制代码

    if (bitmap.compress(Bitmap.CompressFormat.JPEG, 100, fos)) { fos.flush(); } } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { // TODO Auto-...

Global site tag (gtag.js) - Google Analytics