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、RoaringBitmap、中英对照文档、jar包、java; 使用方法:解压翻译后的API文档,用浏览器打开“index.html”文件,即可纵览文档内容。 人性化翻译,文档中的代码和结构保持不变,注释和说明精准...
标签:roaringbitmap、RoaringBitmap、中文文档、jar包、java; 使用方法:解压翻译后的API文档,用浏览器打开“index.html”文件,即可纵览文档内容。 人性化翻译,文档中的代码和结构保持不变,注释和说明精准翻译...
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
RoaringBitmap, 在Java中,一个更好的压缩 bitset RoaringBitmap Bitsets,也称为位图,通常用作快速数据结构。 不幸的是,他们可以使用太多的内存。 为了补偿,我们经常使用压缩位图。咆哮位图是压缩位图,它比传统...
绘制用纹理填充的图形,C#源代码Bitmap bitmap = new ... e.Graphics.DrawImage(bitmap, 0, 0, bitmap.Width, bitmap.Height); e.Graphics.DrawEllipse(texturedPen, 100, 20, 200, 100); VisualStudio2008创建
在计算机图形学和图像处理领域,Bitmap(位图)是一种常见的图像格式,它存储的是像素的二维数组。Bitmap Transform指的是对位图进行的各种变换操作,包括但不限于缩放、旋转、平移等。在这个"Bitmap_transform.rar_...
在实际应用中,我们可能需要根据需求动态调整图片大小或比例,这时可以使用Bitmap.createScaledBitmap方法。这个方法可以将Bitmap缩放到指定的尺寸,同时保持原图像的比例: ```java // 缩放Bitmap至新的尺寸 ...
最后,使用`Bitmap.createBitmap()`创建一个新的Bitmap,这个新的Bitmap就是按照指定比例缩放后的结果。 在实际开发中,需要注意Bitmap的内存管理。由于Bitmap占用大量内存,不恰当的使用可能导致内存溢出。因此,...
当应用程序尝试加载或操作一张超出虚拟机内存预算的`Bitmap`时,系统会抛出`java.lang.OutOfMemoryError: bitmap size exceeds VM budget`异常,导致应用崩溃。为了解决这个问题,开发者需要采取一些策略来优化图片...
bitmap.Save(memoryStream, ImageFormat.Jpeg); // 将Bitmap保存到MemoryStream ``` ### Stream到byte[]转换 MemoryStream是一个实现了Stream接口的类,它可以直接访问其内部的字节数组。我们可以使用ToArray()...
bitmap.LoadImage(_T("path_to_your_bitmap.bmp"), LR_LOADFROMFILE); ``` 显示BMP位图: MFC中的CView类通常用于显示文档内容,我们可以重写它的`OnDraw`方法来绘制位图。首先,确保你的视图类继承自`CView`,...
在编程和软件开发中,处理Bitmap文件需要使用特定的库或API,例如在Java中使用`java.awt.image.BufferedImage`,在C#中使用`System.Drawing.Bitmap`,而在Python中可以使用PIL(Pillow)库。这些库提供了读取、写入...
bitmap = Bitmap.createBitmap(imageView.getWidth(), imageView.getHeight(), Bitmap.Config.ARGB_8888); Canvas canvas = new Canvas(bitmap); imageView.draw(canvas); // 将ImageView的内容绘制到Bitmap } ``...
Bitmap bitmap = Bitmap.createBitmap(640, 480, Bitmap.Config.ARGB_8888); YuvToBitmap.convertYuvToBitmap(yuvData, 640, 480, bitmap); ``` 5. **优化性能**:考虑到Android的内存限制,尽可能使用高效的数据...
Android Bitmap.getPixels的正确理解演示源码,参考文章《Android Bitmap入门:getPixels的正确理解》
本示例 演示绘制位图,分两种方式 1. 绘制Bitmap对象 2.使用Drawable.draw方法绘制位图 详情请参见 http://blog.csdn.net/aduovip/article/details/6722949
Java中BitSet类是Java集合框架的一部分,它是一种用于处理位操作的高级数据结构。BitSet可以看作是一个只存储布尔值的数组,但相比于原始的布尔数组,BitSet更加内存高效,因为它以64位的块(word)来存储多个布尔值...
Bitmap-->List
jar包,官方版本,自测可用