python实现bitmap数据结构详解

计算在数组中的索引

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

复制代码代码如下:
#!/usr/bin/envpython
#coding:utf8

classBitmap(object):
 def__init__(self,max):
  self.size =self.calcElemIndex(max,True)
  self.array=[0foriinrange(self.size)]

 defcalcElemIndex(self,num,up=False):
  """up为True则为向上取整,否则为向下取整"""
  ifup:
   returnint((num+31-1)/31)#向上取整
  returnnum/31

if__name__=="__main__":
 bitmap=Bitmap(90)
 print"数组需要%d个元素。"%bitmap.size
 print"47应存储在第%d个数组元素上。"%bitmap.calcElemIndex(47)

复制代码代码如下:
$pythonbitmap.py
数组需要3个元素。
47应存储在第1个数组元素上。

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

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

数组元素中的位索引可以通过取模运算来得到。令需存储的整数跟31取模即可得到位索引。代码改为如下：

复制代码代码如下:
#!/usr/bin/envpython
#coding:utf8

classBitmap(object):
 def__init__(self,max):
  self.size =self.calcElemIndex(max,True)
  self.array=[0foriinrange(self.size)]

 defcalcElemIndex(self,num,up=False):
  """up为True则为向上取整,否则为向下取整"""
  ifup:
   returnint((num+31-1)/31)#向上取整
  returnnum/31

 defcalcBitIndex(self,num):
  returnnum%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/envpython
#coding:utf8

classBitmap(object):
 def__init__(self,max):
  self.size =self.calcElemIndex(max,True)
  self.array=[0foriinrange(self.size)]

 defcalcElemIndex(self,num,up=False):
  """up为True则为向上取整,否则为向下取整"""
  ifup:
   returnint((num+31-1)/31)#向上取整
  returnnum/31

 defcalcBitIndex(self,num):
  returnnum%31

 defset(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)
 printbitmap.array

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

清0操作

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

复制代码代码如下:
#!/usr/bin/envpython
#coding:utf8

classBitmap(object):
 def__init__(self,max):
  self.size =self.calcElemIndex(max,True)
  self.array=[0foriinrange(self.size)]

 defcalcElemIndex(self,num,up=False):
  """up为True则为向上取整,否则为向下取整"""
  ifup:
   returnint((num+31-1)/31)#向上取整
  returnnum/31

 defcalcBitIndex(self,num):
  returnnum%31

 defset(self,num):
  elemIndex=self.calcElemIndex(num)
  byteIndex=self.calcBitIndex(num)
  elem     =self.array[elemIndex]
  self.array[elemIndex]=elem|(1<<byteIndex)

 defclean(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)
 printbitmap.array
 bitmap.clean(0)
 printbitmap.array
 bitmap.clean(34)
 printbitmap.array

清0和置1是互反操作。

测试某位是否为1

判断某位是否为1是为了取出之前所存储的数据。代码如下：

复制代码代码如下:
#!/usr/bin/envpython
#coding:utf8

classBitmap(object):
 def__init__(self,max):
  self.size =self.calcElemIndex(max,True)
  self.array=[0foriinrange(self.size)]

 defcalcElemIndex(self,num,up=False):
  """up为True则为向上取整,否则为向下取整"""
  ifup:
   returnint((num+31-1)/31)#向上取整
  returnnum/31

 defcalcBitIndex(self,num):
  returnnum%31

 defset(self,num):
  elemIndex=self.calcElemIndex(num)
  byteIndex=self.calcBitIndex(num)
  elem     =self.array[elemIndex]
  self.array[elemIndex]=elem|(1<<byteIndex)

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

 deftest(self,i):
  elemIndex=self.calcElemIndex(i)
  byteIndex=self.calcBitIndex(i)
  ifself.array[elemIndex]&(1<<byteIndex):
   returnTrue
  returnFalse

if__name__=="__main__":
 bitmap=Bitmap(90)
 bitmap.set(0)
 printbitmap.array
 printbitmap.test(0)
 bitmap.set(1)
 printbitmap.test(1)
 printbitmap.test(2)
 bitmap.clean(1)
 printbitmap.test(1)

复制代码代码如下:
$pythonbitmap.py
[1,0,0]
True
True
False
False

接下来实现一个不重复数组的排序。已知一个无序非负整数数组的最大元素为879，请对其自然排序。代码如下：

复制代码代码如下:
#!/usr/bin/envpython
#coding:utf8

classBitmap(object):
 def__init__(self,max):
  self.size =self.calcElemIndex(max,True)
  self.array=[0foriinrange(self.size)]

 defcalcElemIndex(self,num,up=False):
  """up为True则为向上取整,否则为向下取整"""
  ifup:
   returnint((num+31-1)/31)#向上取整
  returnnum/31

 defcalcBitIndex(self,num):
  returnnum%31

 defset(self,num):
  elemIndex=self.calcElemIndex(num)
  byteIndex=self.calcBitIndex(num)
  elem     =self.array[elemIndex]
  self.array[elemIndex]=elem|(1<<byteIndex)

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

 deftest(self,i):
  elemIndex=self.calcElemIndex(i)
  byteIndex=self.calcBitIndex(i)
  ifself.array[elemIndex]&(1<<byteIndex):
   returnTrue
  returnFalse

if__name__=="__main__":
 MAX=879
 suffle_array=[45,2,78,35,67,90,879,0,340,123,46]
 result      =[]
 bitmap=Bitmap(MAX)
 fornuminsuffle_array:
  bitmap.set(num)

 foriinrange(MAX+1):
  ifbitmap.test(i):
   result.append(i)

 print"原始数组为:   %s"%suffle_array
 print"排序后的数组为:%s"%result

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

本文地址： python实现bitmap数据结构详解

相关文章

• mt4 python_一个使用Python自动化交易外汇MT4脚本实现「建议收藏」
• 基于Python 输出字符HelloWorld简单总结
• python监控网站更新_Python 通过网站search功能监控网站内容更新[通俗易懂]
• Python开发系列课程(8) – 字符串和常用数据结构详解编程语言
• Python 基于python实现的http+json协议接口自动化测试框架源码（实用改进版）详解编程语言
• Linux上的Python之旅（linux自带python）
• Linux系统快速运行Python脚本（linux运行python脚本）
• MySQL与Python搭配，实现数据库操作。（mysql-python）
• Python结合MySQL实现信息交互（python与mysql交互）
• python学习Linux、Python，体验自由的乐趣（lexlinux）
• Python实现快速连接Redis数据库（python连接redis）
• 《Python官方文档》5.数据结构
• Python实现Oracle数据库连接（python连接oracle数据库）
• 使用Python连接MySQL数据库，实现高效数据交互（python连接mysql）
• 从 Python 连接到 MySQL：实现更多强大的数据库应用（python和mysql）
• Python脚本实现Linux命令快捷控制（python执行linux命令）
• Linux中如何离开Python环境（linux怎么退出python）
• python编程-将Python程序转化为可执行程序[整理]
• python基础教程之面向对象的一些概念