位图法

实现(c#):

一、定义
位图法就是bitmap的缩写。所谓bitmap,便是用每壹人来存放在某种情况,适用于广大数据,但数据状态又不是不少的图景。日常是用来剖断某些数据存不设有的。在STL中有三个bitset容器,其实正是位图法,引用bitset介绍:

位图法是大额管理中不时利用的才具,认为挺有趣,就来说几句,希望能把位图的思想解释清楚。

数据结构

unsigned int bit[N];

在那几个数组里面,能够积存
N*sizeof(int)*8个数据,可是最大的数只好是
N*sizeof(int)*8-1

当大家要拍卖的数据量不仅巨大,并且数据值也大幅度的时候,用一般的整数值类型(int,int6肆,long)会导致大气的内部存款和储蓄器消耗。

连锁操作

也得以用来去重,风乐趣的,能够团结实现以下。

写入数据

概念3个数组: unsigned char bit[8*1024];这样做,能存 8K*8=64K 个
unsigned short 数据。bit 存放的字节地方和位地点(字节0~8191,位 0~七)比如写1234,字节序:123百分之五十 = 15四; 位序: 1234 &0b11一 = 2 ,那么 1234放在 bit 的下标 15四 字节处,把该字节的 二 号位( 0~7)置为 1

字节位置: int nBytePos =1234/8 = 154;
位位置:   int nBitPos = 1234 & 7 = 2;

比如写入 1236 ,
字节位置: int nBytePos =1236/8 = 154;
位位置:   int nBitPos = 1236 & 7 = 4

// / 把数组的 154 字节的 4 位置为 1  
val = 1<<nBitPos;  
arrBit[nBytePos] = arrBit[nBytePos] |val;  // 再写入 1236 得到arrBit[154]=0b00010100  

代码达成

#define SHIFT 5    
#define MAXLINE 32    
#define MASK 0x1F    
void setbit(int *bitmap, int i){    
    bitmap[i >> SHIFT] |= (1 << (i & MASK));    
}  
  1. 亟需理解数据集的限定,方可神速明确知道需求创建多大的位图。

  2. 借使数据离散程度大,那么空间使用率低。如[1,2,3,4,5,900000,900001]

  3. 莫不较难精通。

A bitset is a special container class that is designed to store bits
(elements with only two possible values: 0 or 1,true or false,
…).The class is very similar to a regular array, but optimizing for
space allocation: each element occupies only one bit (which is eight
times less than the smallest elemental type in C++: char).Each element
(each bit) can be accessed individually: for example, for a given
bitset named mybitset, the expression mybitset[3] accesses its
fourth bit, just like a regular array accesses its elements.

[0] [1] [1] [0] [0] [0] [0] [1]
,如若当贰个因素的值为一时,大家就能够判断出其对应的索引值存在,这几个例子中代表1,2,柒存在。

位图法的行使

  • 应用位图法决断整形数组是或不是留存双重遍历数组,三个一个放入bitmap,并且检查其是不是在bitmap中出现过,假若没出现放入,不然即为重复的要素。

 

读钦赐位
bool getbit(int *bitmap1, int i){    
   return bitmap1[i >> SHIFT] & (1 << (i & MASK));    
}   

能够省略的说,数据内部存款和储蓄器占用率下落到了三分一二.

用位图法,也能够来火速判定,一个大数目集结中,是不是带有了某些特定的值。

那儿使用位图法,就会反映出其优势。

只要用int类型表示2个数值,那么2个数值就要求用到三1二个人的储存空间,倘若使用0可能一来代表方今目录对应值是不是存在,那么原来三个int所占领的长空,能够象征三10个整数。

那边是用位图法落成的排序方法。

 

思路:创建位图来反应数据集,用特定值作为目录,决断值是或不是为一,若为一,则表示该值存在于数据集结中。

public static Array BitSort(int[] arr, int largestNumber) //传入数组,以及数组的最大值
        {
            BitArray bitAry = new BitArray(largestNumber+1);//根据数据的最大值,创建相应的点阵列

            foreach (var item in arr) 
            {
                bitAry[item] = true;//把数组元素值作为索引,将该索引对应的值置为1,表示该值存在
            }
            //一次遍历之后,要排序的数组包含的所有值,在点阵列中被置为1

            int[] result = new int[arr.Length];

            var j = 0;
            for (var i = 0; i < bitAry.Length; i++) 
            {
                if (bitAry[i] == true) //遍历点阵列,如果对应的值为1,则将其索引值放置到新集合内,一次遍历,就可以完成排序
                {
                    result[j] = i;
                    j++;
                }
            }


            return result;
        }

位图法:Computer中意味数据的蝇头单位为Bit,存款和储蓄0恐怕1。而c#中int的尺寸为四个字节,即叁拾伍个bit。

村办通晓,如有错误,应接各路大神指正!

 

 

 

劣势:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图