So implementieren Sie eine Bitmap-Datenstruktur in Python

Bitmap ist eine sehr häufig verwendete Datenstruktur, wie sie beispielsweise im Bloom-Filter, beim Sortieren sich nicht wiederholender Ganzzahlen usw. verwendet wird. Bitmap wird normalerweise basierend auf einem Array implementiert. Jedes Element im Array kann als eine Reihe von Binärzahlen betrachtet werden, und alle Elemente bilden einen größeren Binärsatz. Für Python ist der Ganzzahltyp standardmäßig ein vorzeichenbehafteter Typ, sodass die verfügbare Anzahl von Bits für eine Ganzzahl 31 beträgt.

Bitmap-Implementierungsidee

Bitmap wird verwendet, um jedes Bit zu bearbeiten. Wenn ein Python-Array beispielsweise vier 32-Bit-Ganzzahlen mit Vorzeichen enthält, sind insgesamt 4 * 31 = 124 Bits verfügbar. Wenn Sie das 90. Binärbit bearbeiten möchten, müssen Sie zuerst das Element des Operationsarrays abrufen, dann den entsprechenden Bitindex abrufen und dann die Operation ausführen.

Das obige Bild zeigt eine 32-Bit-Ganzzahl. In Python handelt es sich standardmäßig um einen vorzeichenbehafteten Typ, den Bitmap nicht verwenden kann. Das linke ist das High-Bit, das rechte ist das Low-Bit und das niedrigste Bit ist das 0. Bit.

Bitmap initialisieren

Zuerst müssen Sie die Bitmap initialisieren. Nehmen Sie als Beispiel die Ganzzahl 90. Da eine einzelne Ganzzahl nur 31 Bits verwenden kann, erfahren Sie durch Teilen von 90 durch 31 und Aufrunden, wie viele Array-Elemente benötigt werden. Der Code lautet wie folgt:

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

Index berechnen

Nachdem Sie die Array-Größe ermittelt haben, können Sie dieses Array erstellen. Wenn Sie eine Ganzzahl in diesem Array speichern möchten, müssen Sie zunächst wissen, auf welchem ​​Element des Arrays sie gespeichert ist, und dann müssen Sie wissen, auf welchem ​​Element sie gespeichert ist. Die Berechnung des Index ist also unterteilt in:

1. Berechnung des Index im Array

2. Berechnung des Bitindex im Array-Element

Berechnung des Index im Array

Die Berechnung des Index im Array ist eigentlich dasselbe wie die vorherige Berechnung der Array-Größe. Es ist nur so, dass die maximale Zahl zuvor berechnet wurde und jetzt durch eine beliebige Ganzzahl ersetzt wird, die gespeichert werden muss. Es gibt jedoch einen Unterschied: Der im Array berechnete Index wird abgerundet, daher muss die Implementierung der calcElemIndex-Methode geändert werden. Der Code wird wie folgt geändert:

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

Es ist also wichtig, die maximale Ganzzahl zu erhalten, da sonst das erstellte Array möglicherweise beschädigt wird nicht in der Lage sein, einige Daten aufzunehmen.

Berechnen Sie den Bitindex im Array-Element

Der Bitindex im Array-Element kann durch die Modulo-Operation ermittelt werden. Der Bitindex kann erhalten werden, indem die zu speichernde Ganzzahl Modulo 31 verwendet wird. Der Code wird wie folgt geändert:

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

Vergessen Sie nicht, ab der 0. Stelle zu zählen.

Vorgang 1 festlegen

Das Standard-Binärbit ist 0. Das Setzen eines bestimmten Bits auf 1 bedeutet, dass Daten in diesem Bit gespeichert werden. Der Code wird wie folgt geändert:

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

Da es beim 0. Bit beginnt, wenn Sie 0 speichern müssen, Sie müssen das 0. Bit an Position 1 speichern.

Vorgang löschen

Setzen Sie ein bestimmtes Bit auf 0, dh verwerfen Sie die gespeicherten Daten. Der Code lautet wie folgt:

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

Das Löschen von 0 und das Setzen von 1 sind reziproke Vorgänge.

Testen Sie, ob ein bestimmtes Bit 1 ist

Um festzustellen, ob ein bestimmtes Bit 1 ist, müssen die zuvor gespeicherten Daten abgerufen werden. Der Code lautet wie folgt:

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

Als nächstes implementieren Sie eine Sortierung nicht duplizierter Arrays. Es ist bekannt, dass das maximale Element eines ungeordneten, nicht negativen Ganzzahlarrays 879 beträgt. Bitte sortieren Sie es auf natürliche Weise. Der Code lautet wie folgt:

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

Fazit

Wenn Bitmap implementiert ist, ist es sehr einfach, es zu verwenden Sortierung. Andere Sprachen können ebenfalls Bitmaps implementieren, aber für statisch typisierte Sprachen wie C/Golang werden die verfügbaren Bits einfach zu 32 Bits im obigen Code geändert, da vorzeichenlose Ganzzahlen direkt deklariert werden können. Bitte beachten Sie dies.

Verwandte Empfehlungen:

Datenstruktur – Bitmap

C++ implementiert die BitMap-Datenstruktur

Detaillierte Erläuterung der Bitmap der Datenstruktur

[Datenstruktur] BitMap-Nutzung

Das obige ist der detaillierte Inhalt vonSo implementieren Sie eine Bitmap-Datenstruktur in Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!