Pythonでビットマップデータ構造を実装する方法

ビットマップは、ブルームフィルターや非反復整数の並べ替えなどで使用される、非常に一般的に使用されるデータ構造です。ビットマップは通常、配列に基づいて実装され、配列内の各要素は一連の 2 進数と見なすことができ、すべての要素がより大きな 2 進数のセットを形成します。 Python の場合、整数型はデフォルトで符号付き型であるため、整数に使用できるビット数は 31 です。

ビットマップの実装アイデア

ビットマップは、各ビットの操作に使用されます。たとえば、Python 配列に 4 つの 32 ビット符号付き整数が含まれる場合、使用可能なビットの合計は 4 * 31 = 124 ビットになります。 2 進数の 90 番目のビットを演算する場合は、まず演算配列の要素を取得し、次に対応するビット インデックスを取得して、演算を実行する必要があります。

上の図は 32 ビット整数を示しています。Python では、デフォルトでは最上位ビットが符号ビットであり、ビットマップでは使用できません。左側が上位ビット、右側が下位ビット、最下位ビットが 0 番目のビットです。

ビットマップを初期化する

まず、ビットマップを初期化する必要があります。整数 90 を例に挙げます。1 つの整数は 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 番目の位置から開始することを忘れないでください。

Set 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に設定します。これは、保存されているデータを破棄することを意味します。コードは次のとおりです。

#!/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__ == &#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):
		'''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__ == &#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):
		'''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__ == &#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]

結論

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

関連する推奨事項:

データ構造 - ビットマップ

C++はBitMapデータ構造を実装します

データ構造ビットマップ(ビットマップ)の詳細な説明

[データ構造] BitMapの使用法

以上がPythonでビットマップデータ構造を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。