当前位置:  编程技术>python

python实现bitmap数据结构详解

    来源: 互联网  发布时间:2014-10-04

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

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

bitmap实现思路

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



上图所示为一个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


    
 
 

您可能感兴趣的文章:

  • 数据结构:图(有向图,无向图),在Python中的表示和实现代码示例
  • python数据结构树和二叉树简介
  • Python常用列表数据结构小结
  • python数据结构之二叉树的建立实例
  • python数据结构之二叉树的遍历实例
  • python数据结构之二叉树的统计与转换实例
  • Python常见数据结构详解
  • Python中类似printf的字符串格式化详解
  • Python文件操作类操作实例详解
  • Python break语句详解
  • Python代码的打包与发布详解
  • Python下的Mysql模块MySQLdb安装详解
  • python正则表达式re模块详解
  • Python Deque 模块使用详解
  • Mac OS X10.9安装的Python2.7升级Python3.3步骤详解
  • Python help()函数用法详解
  • python中的sort方法使用详解
  • Python ZipFile模块详解
  • python的dict,set,list,tuple应用详解
  • Python调用C/C++动态链接库的方法详解 iis7站长之家
  • 闭包在python中的应用之translate和maketrans用法详解
  • Python调用C/C++动态链接库的方法详解
  • Python命名空间详解
  • python基础教程之序列详解
  • Python内置数据类型详解
  • Python 列表(List)操作方法详解
  • python多线程编程方式分析示例详解
  • Python标准库与第三方库详解
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • python中定义结构体的方法
  • Python查询Mysql时返回字典结构的代码
  • Python GUI编程:tkinter实现一个窗口并居中代码
  • 让python同时兼容python2和python3的8个技巧分享
  • Python不使用print而直接输出二进制字符串
  • 使用setup.py安装python包和卸载python包的方法
  • Python中实现json字符串和dict类型的互转
  • 不小心把linux自带的python卸载了,导致安装一个依赖原python的软件不能安装,请问该怎么办?
  • python异常信息堆栈输出到日志文件
  • Python开发者社区整站源码 Pythoner
  • python下用os.execl执行centos下的系统时间同步命令ntpdate
  • python读取csv文件示例(python操作csv)
  • Python namedtuple对象json序列化/反序列化及对象恢复
  • python基础教程之python消息摘要算法使用示例
  • Python获取网页编码的方法及示例代码
  • 新手该如何学python怎么学好python?
  • Python异常模块traceback用法举例
  • 使用python删除nginx缓存文件示例(python文件操作)
  • python之平台独立的调试工具winpdb介绍
  • python学习手册中的python多态示例代码
  • 基于Python的Html/xml解析库Beautiful Soup 4.2.1发布
  • 请教:system("C:\python2.4\python.exe C:\aa.py");该语句有何错误?为什么运行界面一闪就消失了并且没有运行完,请给出正确语句!
  • 测试Python内部类型及type和isinstance用法区别
  • python版本的问题




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3