bitmap是很常用的數(shù)據(jù)結(jié)構(gòu)，比如用于Bloom Filter中；用于無(wú)重復(fù)整數(shù)的排序等等。bitmap通常基于數(shù)組來(lái)實(shí)現(xiàn)，數(shù)組中每個(gè)元素可以看成是一系列二進(jìn)制數(shù)，所有元素組成更大的二進(jìn)制集合。對(duì)于Python來(lái)說(shuō)，整數(shù)類型默認(rèn)是有符號(hào)類型，所以一個(gè)整數(shù)的可用位數(shù)為31位。
bitmap實(shí)現(xiàn)思路
bitmap是用于對(duì)每一位進(jìn)行操作。舉例來(lái)說(shuō)，一個(gè)Python數(shù)組包含4個(gè)32位有符號(hào)整型，則總共可用位為4 * 31 = 124位。如果要在第90個(gè)二進(jìn)制位上操作，則要先獲取到操作數(shù)組的第幾個(gè)元素，再獲取相應(yīng)的位索引，然后執(zhí)行操作。
上圖所示為一個(gè)32位整型，在Python中默認(rèn)是有符號(hào)類型，最高位為符號(hào)位，bitmap不能使用它。左邊是高位，右邊是低位，最低位為第0位。
bitmap是用于對(duì)每一位進(jìn)行操作。舉例來(lái)說(shuō)，一個(gè)Python數(shù)組包含4個(gè)32位有符號(hào)整型，則總共可用位為4 * 31 = 124位。如果要在第90個(gè)二進(jìn)制位上操作，則要先獲取到操作數(shù)組的第幾個(gè)元素，再獲取相應(yīng)的位索引，然后執(zhí)行操作。
初始化bitmap
首先需要初始化bitmap。拿90這個(gè)整數(shù)來(lái)說(shuō)，因?yàn)閱蝹€(gè)整型只能使用31位，所以90除以31并向上取整則可得知需要幾個(gè)數(shù)組元素。代碼如下：
class Bitmap(object):
def __init__(self, max):
self.size = int((max + 31 - 1) / 31) #向上取整
if __name__ == '__main__':
bitmap = Bitmap(90)
print '需要 %d 個(gè)元素。' % bitmap.size
計(jì)算在數(shù)組中的索引
計(jì)算在數(shù)組中的索引其實(shí)是跟之前計(jì)算數(shù)組大小是一樣的。只不過(guò)之前是對(duì)最大數(shù)計(jì)算，現(xiàn)在換成任一需要存儲(chǔ)的整數(shù)。但是有一點(diǎn)不同，計(jì)算在數(shù)組中的索引是向下取整，所以需要修改calcElemIndex方法的實(shí)現(xiàn)。代碼改為如下：
class 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
if __name__ == '__main__':
bitmap = Bitmap(90)
print '數(shù)組需要 %d 個(gè)元素。' % bitmap.size
print '47 應(yīng)存儲(chǔ)在第 %d 個(gè)數(shù)組元素上。' % bitmap.calcElemIndex(47)
所以獲取最大整數(shù)很重要，否則有可能創(chuàng)建的數(shù)組容納不下某些數(shù)據(jù)。
計(jì)算在數(shù)組元素中的位索引
數(shù)組元素中的位索引可以通過(guò)取模運(yùn)算來(lái)得到。令需存儲(chǔ)的整數(shù)跟31取模即可得到位索引。代碼改為如下：
class 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
if __name__ == '__main__':
bitmap = Bitmap(90)
print '數(shù)組需要 %d 個(gè)元素。' % bitmap.size
print '47 應(yīng)存儲(chǔ)在第 %d 個(gè)數(shù)組元素上。' % bitmap.calcElemIndex(47)
print '47 應(yīng)存儲(chǔ)在第 %d 個(gè)數(shù)組元素的第 %d 位上。' % (bitmap.calcElemIndex(47), bitmap.calcBitIndex(47),)
別忘了是從第0位算起哦。
置1操作
二進(jìn)制位默認(rèn)是0，將某位置1則表示在此位存儲(chǔ)了數(shù)據(jù)。代碼改為如下：
class 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__ == '__main__':
bitmap = Bitmap(90)
bitmap.set(0)
print bitmap.array
因?yàn)閺牡?位算起，所以如需要存儲(chǔ)0，則需要把第0位置1。
清0操作
將某位置0，也即丟棄已存儲(chǔ)的數(shù)據(jù)。代碼如下：
class 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__ == '__main__':
bitmap = Bitmap(87)
bitmap.set(0)
bitmap.set(34)
print bitmap.array
bitmap.clean(0)
print bitmap.array
bitmap.clean(34)
print bitmap.array
清0和置1是互反操作。
測(cè)試某位是否為1
判斷某位是否為1是為了取出之前所存儲(chǔ)的數(shù)據(jù)。代碼如下：
class 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 False
if __name__ == '__main__':
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)
接下來(lái)實(shí)現(xiàn)一個(gè)不重復(fù)數(shù)組的排序。已知一個(gè)無(wú)序非負(fù)整數(shù)數(shù)組的最大元素為879，請(qǐng)對(duì)其自然排序。代碼如下：
class 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 False
if __name__ == '__main__':
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 '原始數(shù)組為: %s' % suffle_array
print '排序后的數(shù)組為: %s' % result
bitmap實(shí)現(xiàn)了，則利用其進(jìn)行排序就非常簡(jiǎn)單了。其它語(yǔ)言也同樣可以實(shí)現(xiàn)bitmap，但對(duì)于靜態(tài)類型語(yǔ)言來(lái)說(shuō)，比如C/Golang這樣的語(yǔ)言，因?yàn)榭梢灾苯勇暶鳠o(wú)符號(hào)整型，所以可用位就變成32位，只需將上述代碼中的31改成32即可，這點(diǎn)請(qǐng)大家注意。
新聞熱點(diǎn)
疑難解答
圖片精選
