Csharp/C#教程:c# 实现位图算法(BitMap)分享

算法原理

BitMap的基本思想就是用一个bit位来标记某个元素对应的Value,而Key即是该元素。由于采用了Bit为单位来存储数据,因此可以大大节省存储空间。
BitMap可以看成一种数据结构。

假设有这样一个需求:在20亿个随机整数中找出某个数m是否存在其中,并假设32位操作系统,4G内存。
在Java中,int占4字节,1字节=8位(1byte=8bit)。
如果每个数字用int存储,那就是20亿个int,因而占用的空间约为(2000000000*4/1024/1024/1024)≈7.45G
如果按位存储就不一样了,20亿个数就是20亿位,占用空间约为(2000000000/8/1024/1024/1024)≈0.233G

优点和缺点

优点:由于采用了Bit为单位来存储数据并建立映射关系来查找位置,因此可以大大减少存储空间,加快在大量数据中查询的时间。(有点哈希表的意思,但哈希中的value值数据类型可以丰富多样,而BitMap最终查到的value只能表示简单的几种状态。)

缺点:BitMap中的查询结果(value)能表达的状态有限,且所有的数据不能重复。即不可对重复的数据进行排序和查找。

算法实现(C#)

.NET中已经实现了BitMap的数据结构——BitArray,建议使用BitMap算法解决问题时直接使用官方的BitArray。
我参照.NET源码实现了一个简化版的BitMap,以int数组存储位值(最多存21亿个位值),代码如下:

classBitMap { publicintLength{get{returnm_length;} } privateint[]m_array; privateintm_length; publicBitMap(intlength):this(length,false){} //索引根据需求添加 publicboolthis[intindex] { get { returnGet(index); } set { Set(index,value); } } //分配空间以容纳长度位值,位数组中的所有值都设置为defaultValue。 publicBitMap(intlength,booldefaultValue) { if(length<0){ thrownewArgumentOutOfRangeException("length","长度值不能小于0"); } intarrayLength=length>0?(((length-1)/32)+1):0; m_array=newint[arrayLength]; m_length=length; intfillValue=defaultValue?unchecked(((int)0xffffffff)):0; for(inti=0;i<m_array.Length;i++){ m_array[i]=fillValue; } } //返回位置索引处的位值。 publicboolGet(intindex){ if(index<0||index>=Length){ thrownewArgumentOutOfRangeException("index","索引值超出范围"); } return(m_array[index/32]&(1<<(index%32)))!=0; } //将位置索引处的位值设置为value。 publicvoidSet(intindex,boolvalue){ if(index<0||index>=Length){ thrownewArgumentOutOfRangeException("index","索引值超出范围"); } if(value){ m_array[index/32]|=(1<<(index%32)); }else{ m_array[index/32]&=~(1<<(index%32)); } } }

算法应用

问题1:

给40亿个不重复的unsignedint的整数,没有排过序,然后再给一个数,如果快速判断这个数是否在那40亿个数当中。(解决海量数据中的查询问题)

问题1解法:

建立一个位集合,全部初始化为0。遍历40亿个不重复的整数,通过上述提供的一种映射(每个不重复的整数映射到给定的位)找到其位的位置,标记为1。判断这个数是否在大整数集合中,即通过映射关系计算此整数的位位置,检查是否为1,若为1,则存在,若为0,则不存在

问题2:

数据库里存了很多800电话号码,数量特别大,以至于内存放不下,如何排序,时间比空间更重要?电话号码类似于800-810-5555。(高效排序)

问题2解法:

其实就是不重复的任意7位数及其之内的排序问题。我们用1位来表示电话是否出现,遍历整个电话号序列,设置相应的位,遍历位图收集位被设置的号码即可。查看上述的实现代码

上述就是C#学习教程:c# 实现位图算法(BitMap)分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注—计算机技术网(www.ctvol.com)

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ctvol.com/cdevelopment/903764.html

(0)
脚本是什么意思脚本是什么意思
上一篇 2021年10月21日
下一篇 2021年10月21日

精彩推荐