python实现bitmap数据结构详解-Python教學-PHP中文網

首頁

後端開發

Python教學

python实现bitmap数据结构详解

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 16, 2016 am 08:45 AM

bitmap資料結構

bitmap是很常用的数据结构，比如用于Bloom Filter中；用于无重复整数的排序等等。bitmap通常基于数组来实现，数组中每个元素可以看成是一系列二进制数，所有元素组成更大的二进制集合。对于Python来说，整数类型默认是有符号类型，所以一个整数的可用位数为31位。

bitmap实现思路

bitmap是用于对每一位进行操作。举例来说，一个Python数组包含4个32位有符号整型，则总共可用位为4 * 31 = 124位。如果要在第90个二进制位上操作，则要先获取到操作数组的第几个元素，再获取相应的位索引，然后执行操作。

python实现bitmap数据结构详解

上图所示为一个32位整型，在Python中默认是有符号类型，最高位为符号位，bitmap不能使用它。左边是高位，右边是低位，最低位为第0位。

bitmap是用于对每一位进行操作。举例来说，一个Python数组包含4个32位有符号整型，则总共可用位为4 * 31 = 124位。如果要在第90个二进制位上操作，则要先获取到操作数组的第几个元素，再获取相应的位索引，然后执行操作。

初始化bitmap

首先需要初始化bitmap。拿90这个整数来说，因为单个整型只能使用31位，所以90除以31并向上取整则可得知需要几个数组元素。代码如下：

复制代码代码如下:

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

计算在数组中的索引

计算在数组中的索引其实是跟之前计算数组大小是一样的。只不过之前是对最大数计算，现在换成任一需要存储的整数。但是有一点不同，计算在数组中的索引是向下取整，所以需要修改calcElemIndex方法的实现。代码改为如下：

复制代码代码如下:

#!/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 '数组需要 %d 个元素。' % bitmap.size
print '47 应存储在第 %d 个数组元素上。' % bitmap.calcElemIndex(47)

复制代码代码如下:

$ python bitmap.py
数组需要 3 个元素。
47 应存储在第 1 个数组元素上。

所以获取最大整数很重要，否则有可能创建的数组容纳不下某些数据。

计算在数组元素中的位索引

数组元素中的位索引可以通过取模运算来得到。令需存储的整数跟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 '数组需要 %d 个元素。' % bitmap.size
print '47 应存储在第 %d 个数组元素上。' % bitmap.calcElemIndex(47)
print '47 应存储在第 %d 个数组元素的第 %d 位上。' % (bitmap.calcElemIndex(47), bitmap.calcBitIndex(47),)

别忘了是从第0位算起哦。

置1操作

二进制位默认是0，将某位置1则表示在此位存储了数据。代码改为如下：

复制代码代码如下:

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

if __name__ == '__main__':
bitmap = Bitmap(90)
bitmap.set(0)
print bitmap.array

因为从第0位算起，所以如需要存储0，则需要把第0位置1。

清0操作

将某位置0，也即丢弃已存储的数据。代码如下：

复制代码代码如下:

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

def clean(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  elem      = self.array[elemIndex]
  self.array[elemIndex] = elem & (~(1

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是为了取出之前所存储的数据。代码如下：

复制代码代码如下:

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

def clean(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  elem      = self.array[elemIndex]
  self.array[elemIndex] = elem & (~(1

def test(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  if self.array[elemIndex] & (1    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

接下来实现一个不重复数组的排序。已知一个无序非负整数数组的最大元素为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

def clean(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  elem      = self.array[elemIndex]
  self.array[elemIndex] = elem & (~(1

def test(self, i):
  elemIndex = self.calcElemIndex(i)
  byteIndex = self.calcBitIndex(i)
  if self.array[elemIndex] & (1    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 '原始数组为: %s' % suffle_array
print '排序后的数组为: %s' % result

bitmap实现了，则利用其进行排序就非常简单了。其它语言也同样可以实现bitmap，但对于静态类型语言来说，比如C/Golang这样的语言，因为可以直接声明无符号整型，所以可用位就变成32位，只需将上述代码中的31改成32即可，这点请大家注意。

陳述

本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn

Python與C：學習曲線和易用性Apr 19, 2025 am 12:20 AM

Python更易學且易用，C 則更強大但複雜。 1.Python語法簡潔，適合初學者，動態類型和自動內存管理使其易用，但可能導致運行時錯誤。 2.C 提供低級控制和高級特性，適合高性能應用，但學習門檻高，需手動管理內存和類型安全。

Python vs. C：內存管理和控制Apr 19, 2025 am 12:17 AM

Python和C 在内存管理和控制方面的差异显著。1.Python使用自动内存管理，基于引用计数和垃圾回收，简化了程序员的工作。2.C 则要求手动管理内存，提供更多控制权但增加了复杂性和出错风险。选择哪种语言应基于项目需求和团队技术栈。

科學計算的Python：詳細的外觀Apr 19, 2025 am 12:15 AM

Python在科學計算中的應用包括數據分析、機器學習、數值模擬和可視化。 1.Numpy提供高效的多維數組和數學函數。 2.SciPy擴展Numpy功能，提供優化和線性代數工具。 3.Pandas用於數據處理和分析。 4.Matplotlib用於生成各種圖表和可視化結果。

Python和C：找到合適的工具Apr 19, 2025 am 12:04 AM

選擇Python還是C 取決於項目需求：1)Python適合快速開發、數據科學和腳本編寫，因其簡潔語法和豐富庫；2)C 適用於需要高性能和底層控制的場景，如係統編程和遊戲開發，因其編譯型和手動內存管理。

數據科學和機器學習的PythonApr 19, 2025 am 12:02 AM

Python在數據科學和機器學習中的應用廣泛，主要依賴於其簡潔性和強大的庫生態系統。 1）Pandas用於數據處理和分析，2）Numpy提供高效的數值計算，3）Scikit-learn用於機器學習模型構建和優化，這些庫讓Python成為數據科學和機器學習的理想工具。

學習Python：2小時的每日學習是否足夠？Apr 18, 2025 am 12:22 AM

每天學習Python兩個小時是否足夠？這取決於你的目標和學習方法。 1)制定清晰的學習計劃，2)選擇合適的學習資源和方法，3)動手實踐和復習鞏固，可以在這段時間內逐步掌握Python的基本知識和高級功能。

Web開發的Python：關鍵應用程序Apr 18, 2025 am 12:20 AM

Python在Web開發中的關鍵應用包括使用Django和Flask框架、API開發、數據分析與可視化、機器學習與AI、以及性能優化。 1.Django和Flask框架：Django適合快速開發複雜應用，Flask適用於小型或高度自定義項目。 2.API開發：使用Flask或DjangoRESTFramework構建RESTfulAPI。 3.數據分析與可視化：利用Python處理數據並通過Web界面展示。 4.機器學習與AI：Python用於構建智能Web應用。 5.性能優化：通過異步編程、緩存和代碼優