[Python]数据结构–Bitmap

• 2020 年 1 月 3 日
• 筆記

[Python]数据结构–Bitmap 位图

‘Festinatione facit vastum’

• Bitmap简介
• Bitmap的实现和使用

Bitmap简介

bitmap是很常用的数据结构，比如用于Bloom Filter中、用于无重复整数的排序等等。bitmap通常基于数组来实现，数组中每个元素可以看成是一系列二进制数，所有元素组成更大的二进制集合。对于Python来说，整数类型默认是有符号类型，所以一个整数的可用位数为31位。

Bitmap的实现和使用

bitmap实现思路

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

代码：

# encoding: utf-8  """  @author: JYFelt  @contact: [email protected]  @site: www.JYFelt.com    @version: 1.0  @license: Apache Licence  @file: bitmap_demo.py  @time: 2018/1/13 13:46    这一行开始写关于本文件的说明与解释  """      # 初始化bitmap  class Bitmap():      def __init__(self, max):          """确定数组个数"""          self.size = int((max + 31 - 1) / 31)          # max需要传入的为要排序的最大数          self.array = [0 for i in range(self.size)]        def bitindex(self, num):          """确定数组中元素的位索引"""          return num % 31        def set_1(self, num):          """将元素所在的位——置1"""          elemindex = (num // 31)  # 整除，否则为浮点值          byteindex = self.bitindex(num)          ele = self.array[elemindex]          self.array[elemindex] = ele | (1 << byteindex)        def test_1(self, i):          elemindex = (i // 31)  # 整除，否则为浮点值          byteindex = self.bitindex(i)          if self.array[elemindex] & (1 << byteindex):              return True          return False      if __name__ == '__main__':      Max = ord('z')  # ord('*')返回单字符在ASCII中对应的整数      shuffle_array = [x for x in 'qwelajkda']      ret = []      bitmap = Bitmap(Max)      for c in shuffle_array:          bitmap.set_1(ord(c))      for i in range(Max + 1):          if bitmap.test_1(i):              ret.append(chr(i))      print(u'原始数组是:%s' % shuffle_array)      print(u'排序以后的数组是:%s' % ret)