欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

c# 实现位图算法(BitMap)

程序员文章站 2022-04-11 09:57:20
算法原理bitmap的基本思想就是用一个bit位来标记某个元素对应的value,而key即是该元素。由于采用了bit为单位来存储数据,因此可以大大节省存储空间。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# 位图算法的资料请关注其它相关文章!