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# 位图算法的资料请关注我们其它相关文章!

(0)

相关推荐

  • 使用C#编写自己的区块链挖矿算法

    什么是加密货币挖掘? 一个加密货币的价值体现在它的稀缺性上,如果任何人都可以任意构造一个比特币,那么比特币就毫无价值,所以比特币的区块链会让参与者完成一项"工作",根据这个工作的最终结果还分发比特币,这个过程就被叫做"挖矿".这就类似于一个黄金矿工花一些时间来工作,然后获得一点黄金. 挖矿的原理 如果你百度/谷歌搜索 比特币挖矿的原理 的话,都会给你说是计算一个复杂的数学问题而已,但是这么说的话太笼统而且也太简单.采矿引擎如何工作这是一个重要的知识点,所以我们需要了

  • C#深度优先搜索算法

    本文实例为大家分享了C#深度优先搜索算法的具体代码,供大家参考,具体内容如下 //论文要用到其改进算法,在此先demo测试一下 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace DFS { class Program { public int[,] map = new int[100, 100];

  • 同时兼容JS和C#的RSA加密解密算法详解(对web提交的数据加密传输)

    前言 我们在Web应用中往往涉及到敏感的数据,由于HTTP协议以明文的形式与服务器进行交互,因此可以通过截获请求的数据包进行分析来盗取有用的信息.虽然https可以对传输的数据进行加密,但是必须要申请证书(一般都是收费的),成本较高.那么问题来了,如果对web提交的敏感数据进行加密呢?web应用中,前端的数据处理和交互基本上都是靠javascript来完成,后台的逻辑处理可以C#(java)等进行处理. 微软的C#中虽然有RSA算法,但是格式和OpenSSL生成的公钥/私钥文件格式并不兼容.这个

  • KMP算法的C#实现方法

    本文实例简述了KMP算法的C#实现方法,分享给大家供大家参考.具体如下: 具体思路为:next函数求出模式串向右滑动位数,再将模式串的str的next函数值 存入数组next. 具体实现代码如下: static void GetNextVal(string str, int [] next) { int i = 0; int j = -1; next[0] = -1; while (i < str.Length - 1) { if (j == -1 || str[i] == str[j]) {

  • 少见的C# RSA算法

    当下最流行的RSA加密算法,只有公钥和私钥同时拥有才能破解加密信息,RSA加密算法的出现有利于数据安全性传输 1.C#中自带RSACryptoServiceProvider类可以让你很好的生成XML格式的公钥和私钥,两句代码就搞定 2.但是生成的XML格式前端不能很好的利用和读懂,所以在生成的XML格式里需要转换成PEM格式,这样才能直接Copy到验证工具里加密解密,非常方便 首先,我们先导入一个第三方库,因为下面涉及到的转换代码都是需要依赖这个库来实现,导入操作如下 控制台里输入 PM > I

  • c# 实现KMP算法的示例代码

    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特-莫里斯-普拉特操作(简称KMP算法).KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的.具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息.KMP算法的时间复杂度O(m+n) . 实现方式就不再这里献丑了,网上很多讲解,此处只是记录下c#实现的代码. public class KMP { public

  • 经典实例讲解C#递归算法

    一 .递归算法简介 在数学与计算机科学中,递归是指在函数的定义中使用函数自身的方法. 递归算法是一种直接或者间接地调用自身算法的过程.在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解. 递归算法解决问题的特点: (1) 递归就是在过程或函数里调用自身. (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口. (3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低.所以一般不提倡用递归算法设计程序. (4) 在递归调用的过程当中

  • C#实现拼手气红包算法

    本文实例为大家分享了C#实现拼手气红包算法的具体代码,供大家参考,具体内容如下 一.方案1:即开即中,考虑机会均等,减少金额差较大的几率 可以每次点击时候,随机产生 static double[] GetRandomMoney(double money, int n) { double[] array = new double[n]; RedPackage red = new RedPackage() { money = money, count = n }; for (int i = 0; i

  • C#实现简单的RSA非对称加密算法示例

    本文实例讲述了C#实现简单的RSA非对称加密算法.分享给大家供大家参考,具体如下: 界面控件 namespace RSA算法 { partial class Form1 { /// <summary> /// 必需的设计器变量. /// </summary> private System.ComponentModel.IContainer components = null; /// <summary> /// 清理所有正在使用的资源. /// </summary

  • C#字符串自增自减算法详解

    C#实现字符串自增和自减运算,供大家参考,具体内容如下 1.数字从 0-9 变化: 2.字母从 A-Z.a-z 变化: 3.其它字符跳过: 4.以上变化依据其Ascii码值: /// <summary> /// 字符串运算 /// </summary> public class StringOperation { /// <summary> /// 通过ASCII码值,对字符串自增1 /// </summary> /// <param name=&qu

  • C#实现的二维数组排序算法示例

    本文实例讲述了C#实现的二维数组排序算法.分享给大家供大家参考,具体如下: class Order { /// <summary> /// 对二维数组排序 /// </summary> /// <param name="values">排序的二维数组</param> /// <param name="orderColumnsIndexs">排序根据的列的索引号数组</param> /// <

  • C# 数独求解算法的实现

    前言 数独是一种有趣的智力游戏,但是部分高难度数独在求解过程中经常出现大量单元格有多个候选数字可以填入,不得不尝试填写某个数字然后继续推导的方法.不幸的是这种方法经常出现填到一半才发现有单元格无数可填,说明之前就有单元格填错了把后面的路堵死了.这时就需要悔步,之前的单元格换个数重新试.然而更坑的是究竟要悔多少步呢?不知道.要换数字的时候该换哪个呢?也不知道.手算时就需要大量草稿纸记录填写情况,不然容易忘了哪些试过哪些没试过. 在朋友那里玩他手机上的数独的时候就发现这个问题很烦,到这里其实就不是一

随机推荐