Comment implémenter une structure de données bitmap en Python

Bitmap est une structure de données très couramment utilisée, telle que celle utilisée dans le filtre Bloom, le tri d'entiers non répétitifs, etc. Le bitmap est généralement implémenté sur la base d'un tableau. Chaque élément du tableau peut être considéré comme une série de nombres binaires, et tous les éléments forment un ensemble binaire plus grand. Pour Python, le type entier est un type signé par défaut, donc le nombre de bits disponibles pour un entier est de 31.

idée d'implémentation bitmap

bitmap est utilisé pour opérer sur chaque bit. Par exemple, si un tableau Python contient quatre entiers signés de 32 bits, le total de bits disponibles est de 4 * 31 = 124 bits. Si vous souhaitez opérer sur le 90ème bit binaire, vous devez d'abord obtenir l'élément du tableau d'opération, puis obtenir l'index de bit correspondant, puis effectuer l'opération.

L'image ci-dessus montre un entier de 32 bits. En Python, il s'agit d'un type signé par défaut. Le bit le plus élevé est le bit de signe et le bitmap ne peut pas l'utiliser. La gauche est le bit haut, la droite est le bit bas et le bit le plus bas est le 0ème bit.

Initialiser le bitmap

Vous devez d'abord initialiser le bitmap. Prenons l'exemple de l'entier 90. Puisqu'un seul entier ne peut utiliser que 31 bits, diviser 90 par 31 et arrondir vous indiquera le nombre d'éléments du tableau nécessaires. Le code est le suivant :

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

Calculer l'index

Une fois la taille du tableau déterminée, le tableau peut être créé . Si vous souhaitez enregistrer un entier dans ce tableau, vous devez d'abord savoir sur quel élément du tableau il est stocké, puis vous devez savoir sur quel élément il se trouve. Le calcul de l'index est donc divisé en :

1. Calcul de l'index dans le tableau

2. Calcul de l'index des bits dans l'élément du tableau

Calcul de l'index dans le tableau

Le calcul de l'index dans le tableau est en fait la même chose que le calcul de la taille du tableau auparavant. C'est juste que le nombre maximum a été calculé auparavant, et maintenant il est remplacé par n'importe quel entier qui doit être stocké. Mais il y a une différence. L'index calculé dans le tableau est arrondi à l'inférieur, donc l'implémentation de la méthode calcElemIndex doit être modifiée. Le code est modifié comme suit :

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

Il est donc important d'obtenir l'entier maximum, sinon le tableau créé pourrait ne pas pouvoir accueillir certaines données.

Calculez l'indice de bit dans l'élément du tableau

L'indice de bit dans l'élément du tableau peut être obtenu en effectuant l'opération modulo. L'indice des bits peut être obtenu en prenant l'entier à stocker modulo 31. Le code est modifié comme suit :

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

N'oubliez pas de compter à partir de la 0ème position.

Opération Définir 1

Le bit binaire par défaut est 0. Définir un certain bit sur 1 signifie que les données sont stockées dans ce bit. Le code est modifié comme suit :

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

Parce qu'il commence à partir du 0ème bit, si vous devez stocker 0, vous devez stocker le 0ème bit 0 position 1.

Opération d'effacement

Définissez un certain bit sur 0, c'est-à-dire supprimez les données stockées. Le code est le suivant :

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

L'effacement de 0 et la mise à 1 sont des opérations réciproques.

Tester si un certain bit est 1

Déterminer si un certain bit est 1 consiste à récupérer les données précédemment stockées. Le code est le suivant :

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

Ensuite, implémentez un tri des tableaux non dupliqués. On sait que l'élément maximum d'un tableau d'entiers non négatifs non ordonnés est de 879, veuillez le trier naturellement. Le code est le suivant :

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

Si le bitmap est implémenté, il est très simple de l'utiliser pour tri. D'autres langages peuvent également implémenter le bitmap, mais pour les langages typés statiquement, tels que C/Golang, comme les entiers non signés peuvent être déclarés directement, les bits disponibles deviennent 32 bits. Changez simplement 31 dans le code ci-dessus. Veuillez y prêter attention.

Recommandations associées :

Structure des données - bitmap

C++ implémente la structure de données BitMap

Explication détaillée du bitmap de la structure des données

[Structure des données] Utilisation du BitMap

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!