ビットマップデータ構造のPython実装の詳細説明

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 << byteIndex)

if __name__ == '__main__':
 bitmap = Bitmap(90)
 bitmap.set(0)
 print bitmap.array

因为从第0位算起，所以如需要存储0，则需要把第0位置1。

清0操作

将某位置0，也即丢弃已存储的数据。代码如下：

复制代码 代码如下:

#!/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 << byteIndex)

 def clean(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  elem      = self.array[elemIndex]
  self.array[elemIndex] = elem & (~(1 << byteIndex))

if __name__ == '__main__':
 bitmap = Bitmap(87)
 bitmap.set(0)
 bitmap.set(34)
 print bitmap.array
 bitmap.clean(0)
 print bitmap.array
 bitmap.clean(34)
 print bitmap.array

清0和置1是互反操作。

测试某位是否为1

判断某位是否为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 << byteIndex)

 def clean(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  elem      = self.array[elemIndex]
  self.array[elemIndex] = elem & (~(1 << byteIndex))

 def test(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  if self.array[elemIndex] & (1 << byteIndex):
   return True
  return False

if __name__ == '__main__':
 bitmap = Bitmap(90)
 bitmap.set(0)
 print bitmap.array
 print bitmap.test(0)
 bitmap.set(1)
 print bitmap.test(1)
 print bitmap.test(2)
 bitmap.clean(1)
 print bitmap.test(1)

复制代码 代码如下:

$ python bitmap.py
[1, 0, 0]
True
True
False
False

次に、重複しない配列の並べ替えを実装します。順序のない非負の整数配列の最大要素は 879 であることが知られています。自然に並べ替えてください。コードは次のとおりです:

コードをコピー コードは次のとおりです:

#!/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 << byteIndex)

def clean(self, i):
elemIndex = self.calcElemIndex(i)
byteIndex = self.calcBitIndex(i)
elem = self.array[elemIndex]
self.array [elemIndex] = elem & (~(1 << byteIndex))

def test(self, i):
elemIndex = self.calcElemIndex(i)
byteIndex = self.calcBitIndex(i)
if self.array[elemIndex] & (1 << byteIndex):
true を返す false を返す
if __name__ == '__main__':

MAX = 879

suffle_array = [45, 2, 78, 35, 67, 90, 879, 0, 340, 123, 46]
結果 = []
bitmap = Bitmap(MAX)
for num in suffle_array:
bitmap.set(num)

for i in range(MAX + 1):
ビットマップの場合。 test(i):
result.append(i)

print '元の配列は: %s' % suffle_array

print 'ソートされた配列は: %s' % result

ビットマップが実装されている場合、それを並べ替えに使用するのは非常に簡単です。他の言語でもビットマップを実装できますが、C/Golang などの静的型付け言語の場合、符号なし整数を直接宣言できるため、使用可能なビットは上記のコードの 31 を 32 に変更するだけです。ご注意ください。