剑客
关注科技互联网

位图法以及相关应用

位图(bitmap)是一种非常常用的结构,在索引,数据压缩等方面有广泛应用。例如在ext2文件系统中的索引节点位图,linux内核中的pid位图等。正因为位图运算在空间方面的优越性,很多语言都有直接对它的支持。如在C++的STL库中就有一个bitset容器。而在Java中,在java.util包下也有一个BitSet类用来实现位图运算。在位图中,每一位只有0或1,一般情况下就表示存在或者不存在。下图为所有位都为0的位图,其存储空间为2字节:

位图法以及相关应用

c语言实现

#defineINT_BITS sizeof(int)

#defineSHIFT 5// 2^5=32

#defineMASK 0x1f//掩码

#defineMAX 1024*1024*1024//max number

intbitmap[MAX / INT_BITS];//位图数组

/*

* 设置第i位为1(先找到i所在的int元素,再设置对应的位)

* i >> SHIFT 相当于 i / (2 ^ SHIFT),结果为所在int的下标

* i&MASK相当于取i的最后5位,结果为所在int的对应位

*/

voidset(inti){

 bitmap[i >> SHIFT] |= 1<< (i & MASK);

}

//获取第i位

intget(inti){

returnbitmap[i >> SHIFT] & (1<< (i & MASK));

}

//清除第i位(置0)

intclear(inti){

returnbitmap[i >> SHIFT] & ~(1<< (i & MASK));

}

应用

  • 判断是否重复(存在)、去重

    给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。

    解决方法:申请512M的内存一个bit位代表一个unsigned int值读入40亿个数,设置相应的bit位读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。

  • 排序

    假设无重复数据,则位图法排序只需将存入位图的数据依次输出,便得到了排序后的数据。

  • 存储数据(压缩)

    压缩和判重很多时候都是组合使用的。

    • 在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数?
    • 给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
  • 搜索

    设计搜索剪枝时,需要保存已经搜索过的历史信息,有些情况下,可以使用位图减小历史信息数据所占空间。

总结

位图适用于数据规模大,但数据状态少的情况。同时位图在存在以下一些不足:

  • 存储离散数据利用率低 Bitmap申请空间时要根据最大的数来决定申请的空间大小,如果数据是离散的,那空间的利用率就会非常低。
  • 不适合多状态 一个bit只能表示两种状态,如果要表示更多的状态,就需要更多的状态位来实现。如果一个数字需要多个状态位来表示的话,Bitmap的优越性也会大打折扣,而且复杂度却在增加。
  • 可读性差 将数据抽象为bit不利于理解,尤其是用多个bit位来表示一个数时。
  • 性能一般 需要维护额外的逻辑,计算速度会受到一定的影响。
分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址