搜尋

首頁  >  文章  >  後端開發  >  Python如何實作bitmap資料結構

Python如何實作bitmap資料結構

零到壹度
零到壹度原創
2018-04-14 14:37:022534瀏覽

 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 个元素。

 

#計算索引

確定了陣列大小後，也可以建立這個陣列了。如果要將一個整數保存進這個數組，首先需要知道保存在這個數組的第幾個元素之上，然後要知道是在這個元素的第幾位上。因此計算索引分為：

  1. 計算在陣列中的索引

  2. 計算在陣列元素中的位元索引

計算在陣列中的索引

計算在陣列中的索引其實是跟之前計算陣列大小是一樣的。只不過之前是對最大數計算，現在換成任一需要儲存的整數。但是有一點不同，計算在陣列中的索引是向下取整，所以需要修改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__ == &#39;__main__&#39;:
	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):
		&#39;&#39;&#39;up为True则为向上取整, 否则为向下取整&#39;&#39;&#39;
		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__ == &#39;__main__&#39;:
	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):
		&#39;&#39;&#39;up为True则为向上取整, 否则为向下取整&#39;&#39;&#39;
		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__ == &#39;__main__&#39;:
	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):
		&#39;&#39;&#39;up为True则为向上取整, 否则为向下取整&#39;&#39;&#39;
		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__ == &#39;__main__&#39;:
	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 &#39;原始数组为:    %s&#39; % suffle_array	print &#39;排序后的数组为: %s&#39; % 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即可，這點請大家注意。

相關推薦：

資料結構－bitmap

#C 實作BitMap資料結構

資料結構之位圖(bitmap)詳解

【資料結構】BitMap使用

#

以上是Python如何實作bitmap資料結構的詳細內容。更多資訊請關注PHP中文網其他相關文章！

陳述：
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn
上一篇：總結關於python中的中文編碼問題下一篇：總結關於python中的中文編碼問題

相關文章

看更多