How to implement bitmap data structure in Python

Bitmap is a very commonly used data structure, such as used in Bloom Filter, sorting of non-repeating integers, etc. Bitmap is usually implemented based on an array. Each element in the array can be regarded as a series of binary numbers, and all elements form a larger binary set. For Python, the integer type is a signed type by default, so the available number of bits for an integer is 31.

Bitmap implementation idea

Bitmap is used to operate on each bit. For example, if a Python array contains four 32-bit signed integers, the total available bits are 4 * 31 = 124 bits. If you want to operate on the 90th binary bit, you must first obtain the element of the operation array, then obtain the corresponding bit index, and then perform the operation.

The above figure shows a 32-bit integer type. In Python, it is a signed type by default. The highest bit is the sign bit, and bitmap cannot use it. The left is the high bit, the right is the low bit, and the lowest bit is the 0th bit.

Initialize bitmap

First you need to initialize bitmap. Take the integer 90 as an example. Since a single integer can only use 31 bits, dividing 90 by 31 and rounding up will tell you how many array elements are needed. The code is as follows:

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

Calculate index

After the array size is determined, the array can be created. If you want to save an integer into this array, you first need to know which element of the array it is saved on, and then you need to know which element it is on. So calculating the index is divided into:

1. Calculating the index in the array

2. Calculating the bit index in the array element

Calculating the index in the array

Calculating the index in the array is actually the same as calculating the array size before. It's just that the maximum number was calculated before, and now it is replaced by any integer that needs to be stored. But there is one difference. The index calculated in the array is rounded down, so the implementation of the calcElemIndex method needs to be modified. The code is changed to the following:

#!/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 个数组元素上。

So it is important to get the maximum integer, otherwise the created array may not be able to accommodate some data.

Calculate the bit index in the array element

The bit index in the array element can be obtained by taking the modulo operation. The bit index can be obtained by taking the integer to be stored modulo 31. The code is changed to the following:

#!/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 位上。

Don’t forget to count from the 0th position.

Set 1 operation

The default binary bit is 0. Setting a certain bit to 1 means data is stored in this bit. The code is changed to the following:

#!/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]

Because it starts from the 0th bit, if you need to store 0, you need to set the 0th bit to 1.

Clear 0 operation

Set a certain position to 0, that is, discard the stored data. The code is as follows:

#!/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]

Clearing 0 and setting 1 are reciprocal operations.

Test whether a certain bit is 1

To determine whether a certain bit is 1 is to retrieve the previously stored data. The code is as follows:

#!/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

Next, implement a sorting of non-duplicate arrays. It is known that the maximum element of an unordered non-negative integer array is 879, please sort it naturally. The code is as follows:

#!/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

If bitmap is implemented, it is very simple to use it for sorting. Other languages ​​can also implement bitmap, but for statically typed languages, such as C/Golang, because unsigned integers can be declared directly, the available bits become 32 bits. Just change 31 in the above code. Just change it to 32. Please pay attention to this.

Related recommendations:

Data structure - bitmap

C Implementing BitMap data structure

Detailed explanation of bitmap of data structure

[Data structure] BitMap usage

The above is the detailed content of How to implement bitmap data structure in Python. For more information, please follow other related articles on the PHP Chinese website!