Python如何實作bitmap資料結構
- 零到壹度原創
- 2018-04-14 14:37:022509瀏覽
bitmap是很常用的資料結構，例如用於Bloom Filter中、用於無重複整數的排序等等。 bitmap通常基於數組來實現，數組中每個元素可以看成是一系列二進制數，所有元素組成更大的二進制集合。對Python來說，整數類型預設是有符號類型，所以一個整數的可用位數是31位元。
bitmap實作想法
bitmap是用於對每一位進行操作。舉例來說，一個Python數組包含4個32位元有符號整數，則總共可用位元為4 * 31 = 124位元。如果要在第90個二進位位上操作，則要先取得到操作陣列的第幾個元素，再取得對應的位元索引，然後執行操作。
上圖所示為一個32位元整數，在Python中預設是有符號類型，最高位元為符號位，bitmap不能使用它。左邊是高位，右邊是低位，最低位是第0位。
初始化bitmap
首先需要初始化bitmap。拿90這個整數來說，因為單一整數只能使用31位，所以90除以31並向上取整則可得知需要幾個陣列元素。程式碼如下：
#!/usr/bin/env python#coding: utf8class 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: utf8class 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 / 31if __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: utf8class 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 % 31if __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),)
$ python bitmap.py 数组需要 3 个元素。47 应存储在第 1 个数组元素上。47 应存储在第 1 个数组元素的第 16 位上。
別忘了是從第0位元算起喔。
置1操作
二進位位元預設為0，將某位置1則表示在此位元儲存了資料。程式碼改為如下：
#!/usr/bin/env python#coding: utf8class 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
$ python bitmap.py [1, 0, 0]
因為從第0位元算起，所以如需要儲存0，則需要把第0位1。
清除0作業
將某位置0，也即丟棄已儲存的資料。程式碼如下：
#!/usr/bin/env python#coding: utf8class 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
$ python bitmap.py[1, 8, 0][0, 8, 0][0, 0, 0]
清除0和置1是互反操作。
測試某位是否為1
判斷某位是否為1是為了取出先前所儲存的資料。程式碼如下：
#!/usr/bin/env python#coding: utf8class 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 Falseif __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]TrueTrueFalseFalse
#接下來實作一個不重複陣列的排序。已知一個無序非負整數數組的最大元素為879，請對其自然排序。程式碼如下：
#!/usr/bin/env python#coding: utf8class 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 Falseif __name__ == '__main__': MAX = 879 suffle_array = [45, 2, 78, 35, 67, 90, 879, 0, 340, 123, 46] result = [] bitmap = Bitmap(MAX) for num in suffle_array: bitmap.set(num) for i in range(MAX + 1): if bitmap.test(i): result.append(i) print '原始数组为: %s' % suffle_array print '排序后的数组为: %s' % result
$ python bitmap.py原始数组为： [45, 2, 78, 35, 67, 90, 879, 0, 340, 123, 46]排序后的数组为：[0, 2, 35, 45, 46, 67, 78, 90, 123, 340, 879]
#結束語
bitmap實作了，則利用其進行排序就非常簡單了。其它語言也同樣可以實現bitmap，但對於靜態類型語言來說，比如C/Golang這樣的語言，因為可以直接聲明無符號整數，所以可用位就變成32位，只需將上述代碼中的31改成32即可，這點請大家注意。
相關推薦：
#以上是Python如何實作bitmap資料結構的詳細內容。更多資訊請關注PHP中文網其他相關文章！
陳述：
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn