python实现bitmap数据结构详解

bitmap是很常用的数据结构,比如用于bloom filter中;用于无重复整数的排序等等。bitmap通常基于数组来实现,数组中每个元素可以看成是一系列二进制数,所有元素组成更大的二进制集合。对于python来说,整数类型默认是有符号类型,所以一个整数的可用位数为31位。bitmap实现思路 bitmap是用于对每一位进行操作。举例来说,一个python数组包含4个32位有符号整型,则总共可用位为4 * 31 = 124位。如果要在第90个二进制位上操作,则要先获取到操作数组的第几个元素,再获取相应的位索引,然后执行操作。上图所示为一个32位整型,在python中默认是有符号类型,最高位为符号位,bitmap不能使用它。左边是高位,右边是低位,最低位为第0位。

bitmap是用于对每一位进行操作。举例来说,一个python数组包含4个32位有符号整型,则总共可用位为4 * 31 = 124位。如果要在第90个二进制位上操作,则要先获取到操作数组的第几个元素,再获取相应的位索引,然后执行操作。

初始化bitmap

首先需要初始化bitmap。拿90这个整数来说,因为单个整型只能使用31位,所以90除以31并向上取整则可得知需要几个数组元素。代码如下:

代码如下:

#!/usr/bin/env python#coding: utf8

class bitmap(object): def __init__(self, max): self.size = int((max + 31 – 1) / 31) #向上取整

if __name__ == ‘__main__’: bitmap = bitmap(90) print ‘需要 %d 个元素。’ % bitmap.size

代码如下:

$ python bitmap.py需要 3 个元素。

计算在数组中的索引

计算在数组中的索引其实是跟之前计算数组大小是一样的。只不过之前是对最大数计算,现在换成任一需要存储的整数。但是有一点不同,计算在数组中的索引是向下取整,所以需要修改calcelemindex方法的实现。代码改为如下:

代码如下:

#!/usr/bin/env python#coding: utf8

class bitmap(object): def __init__(self, max): self.size = self.calcelemindex(max, true) self.array = [0 for i in range(self.size)]

def calcelemindex(self, num, up=false): ”’up为true则为向上取整, 否则为向下取整”’ if up: return int((num + 31 – 1) / 31) #向上取整 return num / 31

if __name__ == ‘__main__’: bitmap = bitmap(90) print ‘数组需要 %d 个元素。’ % bitmap.size print ’47 应存储在第 %d 个数组元素上。’ % bitmap.calcelemindex(47)

代码如下:

$ python bitmap.py数组需要 3 个元素。47 应存储在第 1 个数组元素上。

所以获取最大整数很重要,否则有可能创建的数组容纳不下某些数据。

计算在数组元素中的位索引

数组元素中的位索引可以通过取模运算来得到。令需存储的整数跟31取模即可得到位索引。代码改为如下:

代码如下:

#!/usr/bin/env python#coding: utf8

class bitmap(object): def __init__(self, max): self.size = self.calcelemindex(max, true) self.array = [0 for i in range(self.size)]

def calcelemindex(self, num, up=false): ”’up为true则为向上取整, 否则为向下取整”’ if up: return int((num + 31 – 1) / 31) #向上取整 return num / 31

def calcbitindex(self, num): return num % 31

if __name__ == ‘__main__’: bitmap = bitmap(90) print ‘数组需要 %d 个元素。’ % bitmap.size print ’47 应存储在第 %d 个数组元素上。’ % bitmap.calcelemindex(47) print ’47 应存储在第 %d 个数组元素的第 %d 位上。’ % (bitmap.calcelemindex(47), bitmap.calcbitindex(47),)

别忘了是从第0位算起哦。

置1操作

二进制位默认是0,将某位置1则表示在此位存储了数据。代码改为如下:

代码如下:

#!/usr/bin/env python#coding: utf8

class bitmap(object): def __init__(self, max): self.size = self.calcelemindex(max, true) self.array = [0 for i in range(self.size)]

def calcelemindex(self, num, up=false): ”’up为true则为向上取整, 否则为向下取整”’ if up: return int((num + 31 – 1) / 31) #向上取整 return num / 31

def calcbitindex(self, num): return num % 31

def set(self, num): elemindex = self.calcelemindex(num) byteindex = self.calcbitindex(num) elem = self.array[elemindex] self.array[elemindex] = elem | (1