没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
c# 实现位图算法(实现位图算法(BitMap))
主要介绍了c# 如何实现位图算法(BitMap),文中讲解非常细致,帮助大家更好的理解和学习,感兴趣的朋友
可以了解下
算法原理算法原理
BitMap的基本思想就是用一个bit位来标记某个元素对应的Value,而Key即是该元素。由于采用了Bit为单位来存储数据,因此
可以大大节省存储空间。
BitMap可以看成一种数据结构。
假设有这样一个需求:在20亿个随机整数中找出某个数m是否存在其中,并假设32位操作系统,4G内存。
在Java中,int占4字节,1字节=8位(1 byte = 8 bit)。
如果每个数字用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亿个位值),代码如下:
class BitMap
{
public int Length{ get{ return m_length;}
}
private int[] m_array;
private int m_length;
public BitMap(int length): this(length, false) { }
//索引根据需求添加
public bool this[int index]
{
get
{
return Get(index);
}
set
{
Set(index,value);
}
}
//分配空间以容纳长度位值, 位数组中的所有值都设置为defaultValue。
public BitMap(int length, bool defaultValue)
{
if (length < 0) {
throw new ArgumentOutOfRangeException("length", "长度值不能小于0");
}
int arrayLength = length > 0 ? (((length - 1) / 32) + 1) : 0;
m_array = new int[arrayLength];
m_length = length;
int fillValue = defaultValue ? unchecked(((int)0xffffffff)) : 0;
for (int i = 0; i < m_array.Length; i++) {
m_array[i] = fillValue;
}
}
//返回位置索引处的位值。
public bool Get(int index) {
if (index < 0 || index >= Length) {
throw new ArgumentOutOfRangeException("index", "索引值超出范围");
}
return (m_array[index / 32] & (1 << (index % 32))) != 0;
}
资源评论
weixin_38629939
- 粉丝: 11
- 资源: 926
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功