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