python实现bitmap数据结构详解

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 << byteIndex)

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

代码如下:

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

接下来实现一个不重复数组的排序。已知一个无序非负整数数组的最大元素为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 '原始数组为:    %s' % suffle_array
 print '排序后的数组为: %s' % result

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

(0)

相关推荐

  • Python 过滤字符串的技巧,map与itertools.imap

    具体的实例 我们需要在目录中遍历,包括子目录(哈哈),找出所有后缀为:rmvb ,avi ,pmp 的文件.(天哪?!你要干什么?这可是我的隐私啊--) 复制代码 代码如下: import os def anyTrue(predicate, sequence): return True in map(predicate, sequence) def filterFiles(folder, exts): for fileName in os.listdir(folder): if os.path.

  • Python中的map()函数和reduce()函数的用法

    Python内建了map()和reduce()函数. 如果你读过Google的那篇大名鼎鼎的论文"MapReduce: Simplified Data Processing on Large Clusters",你就能大概明白map/reduce的概念. 我们先看map.map()函数接收两个参数,一个是函数,一个是序列,map将传入的函数依次作用到序列的每个元素,并把结果作为新的list返回. 举例说明,比如我们有一个函数f(x)=x2,要把这个函数作用在一个list [1, 2,

  • Python内置函数之filter map reduce介绍

    Python内置了一些非常有趣.有用的函数,如:filter.map.reduce,都是对一个集合进行处理,filter很容易理解用于过滤,map用于映射,reduce用于归并. 是Python列表方法的三架马车. 1. filter函数的功能相当于过滤器.调用一个布尔函数bool_func来迭代遍历每个seq中的元素:返回一个使bool_seq返回值为true的元素的序列. >>> N=range(10) >>> print filter(lambda x:x>

  • Python多线程同步Lock、RLock、Semaphore、Event实例

    一.多线程同步 由于CPython的python解释器在单线程模式下执行,所以导致python的多线程在很多的时候并不能很好地发挥多核cpu的资源.大部分情况都推荐使用多进程. python的多线程的同步与其他语言基本相同,主要包含: Lock & RLock :用来确保多线程多共享资源的访问. Semaphore : 用来确保一定资源多线程访问时的上限,例如资源池.  Event : 是最简单的线程间通信的方式,一个线程可以发送信号,其他的线程接收到信号后执行操作. 二.实例 1)Lock &a

  • python 基础教程之Map使用方法

    Python Map Map会将一个函数映射到一个输入列表的所有元素上.Map的规范为:map(function_to_apply, list_of_inputs) 大多数时候,我们需要将列表中的所有元素一个个传递给一个函数,并收集输出.例如: items = [1, 2, 3, 4, 5] squared = [] for i in items: squared.append(i**2) 使用Map的话,可以让我们以一种更加简便的方法解决这种问题. items = [1, 2, 3, 4, 5

  • 用map函数来完成Python并行任务的简单示例

    众所周知,Python的并行处理能力很不理想.我认为如果不考虑线程和GIL的标准参数(它们大多是合法的),其原因不是因为技术不到位,而是我们的使用方法不恰当.大多数关于Python线程和多进程的教材虽然都很出色,但是内容繁琐冗长.它们的确在开篇铺陈了许多有用信息,但往往都不会涉及真正能提高日常工作的部分. 经典例子 DDG上以"Python threading tutorial (Python线程教程)"为关键字的热门搜索结果表明:几乎每篇文章中给出的例子都是相同的类+队列. 事实上,

  • python中map、any、all函数用法分析

    本文实例讲述了python中map.any.all函数用法.分享给大家供大家参考.具体分析如下: 最近想学python,就一直比较关注python,昨天在python吧看到有个帖子提问怎么在python中怎么判断密码是否符合规范,回帖中有很多用循环的,除此外还有一个没有用循环,代码非常简练,下面是代码: def volid(pwd): a = any(map(str.isupper,pwd)) b = any(map(str.islower,pwd)) c = any(map(str.isdig

  • python中map()与zip()操作方法

    对于map()它的原型是:map(function,sequence),就是对序列sequence中每个元素都执行函数function操作. 比如之前的a,b,c = map(int,raw_input().split()),意思就是说把输入的a,b,c转化为整数.再比如: a = ['1','2','3','4'] print map(list,a) print map(int,a) 第一个map是把列表a中每个元素转化为列表,第二个map是把a中每个元素转化为整数. 而对于zip(),原型是

  • python实现bitmap数据结构详解

    bitmap是很常用的数据结构,比如用于Bloom Filter中:用于无重复整数的排序等等.bitmap通常基于数组来实现,数组中每个元素可以看成是一系列二进制数,所有元素组成更大的二进制集合.对于Python来说,整数类型默认是有符号类型,所以一个整数的可用位数为31位. bitmap实现思路 bitmap是用于对每一位进行操作.举例来说,一个Python数组包含4个32位有符号整型,则总共可用位为4 * 31 = 124位.如果要在第90个二进制位上操作,则要先获取到操作数组的第几个元素,

  • Python基础之数据结构详解

    一.列表 创建一个列表,只要把逗号分隔的不同的数据项使用方括号括起来 示例: list01 = ['a','b','c'] 1.1 列表更新元素 一个列表是可以储存不同的类型的数据结构,并且修改的新元素也不一定需要和原来的元素类型一致,但是要注意的是,更新列表的索引必须是已存在的索引,不能对超出列表的索引更新元素 1.2 列表增加元素 增加元素的方法: 1.append方法:在列表的最后增加一个元素. list01 = ['a', 'b', 'c'] list01 .append('d') pr

  • Python内建数据结构详解

    一.列表(List) list 是一个可以在其中存储一系列项目的数据结构.list 的项目之间需用逗号分开,并用一对中括号括将所有的项目括起来,以表明这是一个 list .下例用以展示 list 的一些基本操作: # 定义一个 list 对象 class_list: class_list = ['Michael', 'Bob', 'Tracy'] # 获得一个 class_list 的长度 print 'class have', len(class_list), 'students' # 访问c

  • Python Pandas学习之Pandas数据结构详解

    目录 1Pandas介绍 2Pandas数据结构 2.1Series 2.2DataFrame 1 Pandas介绍 2008年WesMcKinney开发出的库 专门用于数据挖掘的开源python库 以Numpy为基础,借力Numpy模块在计算方面性能高的优势 基于matplotlib,能够简便的画图 独特的数据结构 Numpy已经能够帮助我们处理数据,能够结合matplotlib解决部分数据展示等问题,那么pandas学习的目的在什么地方呢? 增强图表可读性 便捷的数据处理能力 读取文件方便

  • Python Pandas 中的数据结构详解

    目录 1.Series 1.1通过列表创建Series 1.2通过字典创建Series 2.DataFrame 3.索引对象 4.查看DataFrame的常用属性 前言: Pandas有三种数据结构:Series.DataFrame和Panel.Series类似于数组:DataFrame类似于表格:Panel可视为Excel的多表单Sheet 1.Series Series是一种一维数组对象,包含一个值序列,并且包含数据标签,称为索引(index),通过索引来访问数组中的数据. 1.1通过列表创

  • C++调用Python基础功能实例详解

    c++调用Python首先安装Python,以win7为例,Python路径为:c:\Python35\,通过mingw编译c++代码. 编写makefile文件,首先要添加包含路径: inc_path += c:/Python35/include 然后添加链接参数: ld_flag += c:/Python35/libs/libpython35.a 在源文件中添加头文件引用: #include "Python.h" Python解释器需要进行初始化,完成任务后需要终止: void s

  • python实现单向链表详解

    本文研究的主要是Python中实现单向链表的相关内容,具体如下. 什么是链表 链表顾名思义就是-链 链表是一种动态数据结构,他的特点是用一组任意的存储单元存放数据元素.链表中每一个元素成为"结点",每一个结点都是由数据域和指针域组成的.跟数组不同链表不用预先定义大小,而且硬件支持的话可以无限扩展. 链表与数组的不同点: 数组需要预先定义大小,无法适应数据动态地增减,数据小于定义的长度会浪费内存,数据超过预定义的长度无法插入.而链表是动态增删数据,可以随意增加. 数组适用于获取元素的操作

  • 使用C++调用Python代码的方法详解

    一.配置python环境问题 1.首先安装Python(版本无所谓),安装的时候选的添加python路径到环境变量中 安装之后的文件夹如下所示: 2.在VS中配置环境和库 右击项目->属性->VC++目录 1)包含目录: Python安装路径/include 2)库目录: Python安装路径/libs 右击项目->属性->连接器->输入->附加依赖库 debug下: python安装目录/libs/python37_d.lib release下: python安装目录

  • Python实现堆排序案例详解

    Python实现堆排序 一.堆排序简介 堆排序(Heap Sort)是利用堆这种数据结构所设计的一种排序算法. 堆的结构是一棵完全二叉树的结构,并且满足堆积的性质:每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点. 关于二叉树和完全二叉树的介绍可以参考:https://blog.csdn.net/weixin_43790276/article/details/104737870 堆排序先按从上到下.从左到右的顺序将待排序列表中的元素构造成一棵完全二叉树,然后对完全二叉树进行调整,使

  • Python heapq库案例详解

    Python heapq heapq 库是 Python 标准库之一,提供了构建小顶堆的方法和一些对小顶堆的基本操作方法(如入堆,出堆等),可以用于实现堆排序算法. 堆是一种基本的数据结构,堆的结构是一棵完全二叉树,并且满足堆积的性质:每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点. 堆结构分为大顶堆和小顶堆,在 heapq 中使用的是小顶堆: 大顶堆:每个节点(叶节点除外)的值都大于等于其子节点的值,根节点的值是所有节点中最大的. 小顶堆:每个节点(叶节点除外)的值都小于等于其

随机推荐