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; } //将位置索引处的位值设置为value。 public void Set(int index, bool value) { if (index < 0 || index >= Length) { throw new ArgumentOutOfRangeException("index", "索引值超出范围"); } if (value) { m_array[index / 32] |= (1 << (index % 32)); } else { m_array[index / 32] &= ~(1 << (index % 32)); } } }
算法应用
问题1:
给40亿个不重复的unsigned int的整数,没有排过序,然后再给一个数,如果快速判断这个数是否在那40亿个数当中。(解决海量数据中的查询问题)
问题1解法:
建立一个位集合,全部初始化为0。遍历40亿个不重复的整数,通过上述提供的一种映射(每个不重复的整数映射到给定的位)找到其位的位置,标记为1。判断这个数是否在大整数集合中,即通过映射关系计算此整数的位位置,检查是否为1,若为1,则存在,若为0,则不存在
问题2:
数据库里存了很多800电话号码,数量特别大,以至于内存放不下,如何排序,时间比空间更重要?电话号码类似于800-810-5555。(高效排序)
问题2解法:
其实就是不重复的任意7位数及其之内的排序问题。我们用1位来表示电话是否出现,遍历整个电话号序列,设置相应的位,遍历位图收集位被设置的号码即可。查看上述的实现代码
以上就是c# 实现位图算法(BitMap)的详细内容,更多关于c# 位图算法的资料请关注猪先飞其它相关文章!
相关文章
- 我们在使用C#做项目的时候,基本上都需要制作登录界面,那么今天我们就来一步步看看,如果简单的实现登录界面呢,本文给出2个例子,由简入难,希望大家能够喜欢。...2020-06-25
- 这篇文章主要介绍了C# 字段和属性的的相关资料,文中示例代码非常详细,供大家参考和学习,感兴趣的朋友可以了解下...2020-11-03
- 这篇文章主要介绍了C#中截取字符串的的基本方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
- 这篇文章主要介绍了C#实现简单的Http请求的方法,以实例形式较为详细的分析了C#实现Http请求的具体方法,需要的朋友可以参考下...2020-06-25
- 本文给大家分享C#连接SQL数据库和查询数据功能的操作技巧,本文通过图文并茂的形式给大家介绍的非常详细,需要的朋友参考下吧...2021-05-17
- 本文主要介绍了C#中new的几种用法,具有很好的参考价值,下面跟着小编一起来看下吧...2020-06-25
使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序)
这篇文章主要介绍了使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序),小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25- 这篇文章主要介绍了C#开发Windows窗体应用程序的简单操作步骤,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-04-12
- 这篇文章主要介绍了C#从数据库读取图片并保存的方法,帮助大家更好的理解和使用c#,感兴趣的朋友可以了解下...2021-01-16
- 最近做一个小项目不可避免的需要前端脚本与后台进行交互。由于是在asp.net中实现,故问题演化成asp.net中jiavascript与后台c#如何进行交互。...2020-06-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 轻松学习C#的基础入门,了解C#最基本的知识点,C#是一种简洁的,类型安全的一种完全面向对象的开发语言,是Microsoft专门基于.NET Framework平台开发的而量身定做的高级程序设计语言,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#变量命名规则小结,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-09
- 这篇文章主要介绍了C#绘制曲线图的方法,以完整实例形式较为详细的分析了C#进行曲线绘制的具体步骤与相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C# 中取绝对值的函数。具有很好的参考价值。下面跟着小编一起来看下吧...2020-06-25
- 这篇文章主要介绍了c#自带缓存使用方法,包括获取数据缓存、设置数据缓存、移除指定数据缓存等方法,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了c#中(&&,||)与(&,|)的区别详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 下面小编就为大家带来一篇C#学习笔记- 随机函数Random()的用法详解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 这篇文章主要介绍了C#中list用法,结合实例形式分析了C#中list排序、运算、转换等常见操作技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25