python實(shí)現(xiàn)bitmap數(shù)據(jù)結(jié)構(gòu)詳解
bitmap是很常用的數(shù)據(jù)結(jié)構(gòu)，比如用于Bloom Filter中；用于無重復(fù)整數(shù)的排序等等。bitmap通常基于數(shù)組來實(shí)現(xiàn)，數(shù)組中每個元素可以看成是一系列二進(jìn)制數(shù)，所有元素組成更大的二進(jìn)制集合。對于Python來說，整數(shù)類型默認(rèn)是有符號類型，所以一個整數(shù)的可用位數(shù)為31位。
bitmap實(shí)現(xiàn)思路
bitmap是用于對每一位進(jìn)行操作。舉例來說，一個Python數(shù)組包含4個32位有符號整型，則總共可用位為4 * 31 = 124位。如果要在第90個二進(jìn)制位上操作，則要先獲取到操作數(shù)組的第幾個元素，再獲取相應(yīng)的位索引，然后執(zhí)行操作。
上圖所示為一個32位整型，在Python中默認(rèn)是有符號類型，最高位為符號位，bitmap不能使用它。左邊是高位，右邊是低位，最低位為第0位。
bitmap是用于對每一位進(jìn)行操作。舉例來說，一個Python數(shù)組包含4個32位有符號整型，則總共可用位為4 * 31 = 124位。如果要在第90個二進(jìn)制位上操作，則要先獲取到操作數(shù)組的第幾個元素，再獲取相應(yīng)的位索引，然后執(zhí)行操作。
初始化bitmap
首先需要初始化bitmap。拿90這個整數(shù)來說，因?yàn)閱蝹€整型只能使用31位，所以90除以31并向上取整則可得知需要幾個數(shù)組元素。代碼如下：
#!/usr/bin/env python
#coding: utf8
class 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 個元素。
計(jì)算在數(shù)組中的索引
計(jì)算在數(shù)組中的索引其實(shí)是跟之前計(jì)算數(shù)組大小是一樣的。只不過之前是對最大數(shù)計(jì)算，現(xiàn)在換成任一需要存儲的整數(shù)。但是有一點(diǎn)不同，計(jì)算在數(shù)組中的索引是向下取整，所以需要修改calcElemIndex方法的實(shí)現(xiàn)。代碼改為如下：
#!/usr/bin/env python
#coding: utf8
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 個元素。' % bitmap.size
print '47 應(yīng)存儲在第 %d 個數(shù)組元素上。' % bitmap.calcElemIndex(47)
$ python bitmap.py
數(shù)組需要 3 個元素。
47 應(yīng)存儲在第 1 個數(shù)組元素上。
所以獲取最大整數(shù)很重要，否則有可能創(chuàng)建的數(shù)組容納不下某些數(shù)據(jù)。
計(jì)算在數(shù)組元素中的位索引
數(shù)組元素中的位索引可以通過取模運(yùn)算來得到。令需存儲的整數(shù)跟31取模即可得到位索引。代碼改為如下：
#!/usr/bin/env python
#coding: utf8
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 個元素。' % bitmap.size
print '47 應(yīng)存儲在第 %d 個數(shù)組元素上。' % bitmap.calcElemIndex(47)
print '47 應(yīng)存儲在第 %d 個數(shù)組元素的第 %d 位上。' % (bitmap.calcElemIndex(47), bitmap.calcBitIndex(47),)
別忘了是從第0位算起哦。
置1操作
二進(jìn)制位默認(rèn)是0，將某位置1則表示在此位存儲了數(shù)據(jù)。代碼改為如下：
#!/usr/bin/env python
#coding: utf8
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)閺牡?位算起，所以如需要存儲0，則需要把第0位置1。
清0操作
將某位置0，也即丟棄已存儲的數(shù)據(jù)。代碼如下：
#!/usr/bin/env python
#coding: utf8
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是互反操作。
測試某位是否為1
判斷某位是否為1是為了取出之前所存儲的數(shù)據(jù)。代碼如下：
#!/usr/bin/env python
#coding: utf8
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)
$ python bitmap.py
[1, 0, 0]
True
True
False
False
接下來實(shí)現(xiàn)一個不重復(fù)數(shù)組的排序。已知一個無序非負(fù)整數(shù)數(shù)組的最大元素為879，請對其自然排序。代碼如下：
#!/usr/bin/env python
#coding: utf8
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)行排序就非常簡單了。其它語言也同樣可以實(shí)現(xiàn)bitmap，但對于靜態(tài)類型語言來說，比如C/Golang這樣的語言，因?yàn)榭梢灾苯勇暶鳠o符號整型，所以可用位就變成32位，只需將上述代碼中的31改成32即可，這點(diǎn)請大家注意。
相關(guān)文章
本文給大家分享的是python 無向圖最短路徑算法：請各位大大指教，繼續(xù)改進(jìn)。(修改了中文字符串，使py2exe中文沒煩惱）,需要的朋友可以參考下2015-03-03
這篇文章主要給大家介紹了關(guān)于在java中如何定義一個抽象屬性示例詳解的相關(guān)資料,需要的朋友可以參考下2017-08-08
詳解使用python3.7配置開發(fā)釘釘群自定義機(jī)器人(2020年新版攻略)
這篇文章主要介紹了詳解使用python3.7配置開發(fā)釘釘群自定義機(jī)器人(2020年新版攻略)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-04-04
關(guān)于numpy.concatenate()函數(shù)的使用及說明
這篇文章主要介紹了關(guān)于numpy.concatenate()函數(shù)的使用及說明,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
分析python動態(tài)規(guī)劃的遞歸、非遞歸實(shí)現(xiàn)
本文小編給大家詳細(xì)分析了python動態(tài)規(guī)劃的遞歸、非遞歸實(shí)現(xiàn)過程以及相關(guān)代碼，有興趣的朋友可以學(xué)習(xí)下。2018-03-03
python實(shí)現(xiàn)簡單的計(jì)算器功能
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)簡單的計(jì)算器功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-07-07
Python被人詬病最多的大概就是性能差，在這里講一下 Python 的多進(jìn)程，多線程與協(xié)程。首先聲明這不是教程，看完這篇文章，大概能夠?qū)?Python 的多進(jìn)程與多線程有一定的了解。2016-07-07
這篇文章主要介紹了Python腳本的常見參數(shù)獲取和處理方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-09-09
python獲取天氣接口給指定微信好友發(fā)天氣預(yù)報(bào)
這篇文章主要介紹了python獲取天氣接口給指定微信好友發(fā)天氣預(yù)報(bào)的步驟，幫助大家更好的理解和學(xué)習(xí)python，感興趣的朋友可以了解下2020-12-12
這篇文章主要介紹了python定時器使用示例,需要的朋友可以參考下2014-02-02