Python에서 비트맵 데이터 구조를 구현하는 방법

비트맵은 Bloom Filter, 반복되지 않는 정수 정렬 등에 사용되는 등 매우 일반적으로 사용되는 데이터 구조입니다. 비트맵은 일반적으로 배열을 기반으로 구현됩니다. 배열의 각 요소는 일련의 이진수로 간주될 수 있으며 모든 요소는 더 큰 이진수 집합을 형성합니다. Python의 경우 정수 유형은 기본적으로 부호 있는 유형이므로 정수에 사용 가능한 비트 수는 31입니다.

비트맵 구현 아이디어

비트맵은 각 비트에서 작동하는 데 사용됩니다. 예를 들어 Python 배열에 32비트 부호 있는 정수 4개가 포함된 경우 사용 가능한 총 비트는 4 * 31 = 124비트입니다. 90번째 이진 비트에 대해 연산을 수행하려면 먼저 연산 배열의 요소를 얻은 다음 해당 비트 인덱스를 얻은 다음 연산을 수행해야 합니다.

위 그림은 32비트 정수를 보여줍니다. Python에서는 기본적으로 가장 높은 비트가 부호 비트이며 비트맵은 사용할 수 없습니다. 왼쪽이 높은 비트, 오른쪽이 낮은 비트, 가장 낮은 비트가 0번째 비트입니다.

비트맵 초기화

먼저 비트맵을 초기화해야 합니다. 예를 들어 정수 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번째 위치부터 시작하는 것을 잊지 마세요.

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로 설정해야 합니다.

Clear Operation

특정 위치를 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]

Conclusion

비트맵을 구현하면 정렬에 사용하는 것이 매우 간단합니다. 다른 언어에서도 비트맵을 구현할 수 있지만, C/Golang과 같은 정적으로 유형이 지정된 언어의 경우 부호 없는 정수를 직접 선언할 수 있으므로 사용 가능한 비트는 32비트가 됩니다. 위 코드에서 31로 변경하면 됩니다. 이에 주의하시기 바랍니다.

관련 권장 사항:

데이터 구조 - 비트맵

C++에서는 BitMap 데이터 구조를 구현합니다.

데이터 구조 비트맵(bitmap)

[데이터 구조] BitMap 사용법

위 내용은 Python에서 비트맵 데이터 구조를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!