文档章节

Python: 实现bitmap数据结构

陈亦
 陈亦
发布于 2014/02/17 00:03
字数 1916
阅读 4753
收藏 10

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

bitmap实现思路

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

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

初始化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 个元素。

计算索引

确定了数组大小后,也就可以创建这个数组了。如果要将一个整数保存进这个数组,首先需要知道保存在这个数组的第几个元素之上,然后要知道是在这个元素的第几位上。因此计算索引分为:

  1. 计算在数组中的索引

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

计算在数组中的索引

计算在数组中的索引其实是跟之前计算数组大小是一样的。只不过之前是对最大数计算,现在换成任一需要存储的整数。但是有一点不同,计算在数组中的索引是向下取整,所以需要修改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),)

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

别忘了是从第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

$ python bitmap.py
[1, 0, 0]

因为从第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

$ python bitmap.py
[1, 8, 0]
[0, 8, 0]
[0, 0, 0]

清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

$ python bitmap.py
原始数组为:   [45, 2, 78, 35, 67, 90, 879, 0, 340, 123, 46]
排序后的数组为:[0, 2, 35, 45, 46, 67, 78, 90, 123, 340, 879]

结束语

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

© 著作权归作者所有

陈亦
粉丝 241
博文 23
码字总数 53194
作品 0
浦东
高级程序员
私信 提问
加载中

评论(1)

国夫君
国夫君
79
Python: Trie树实现字典排序

一般语言都提供了按字典排序的API,比如跟微信公众平台对接时就需要用到字典排序。按字典排序有很多种算法,最容易想到的就是字符串搜索的方式,但这种方式实现起来很麻烦,性能也不太好。T...

陈亦
2014/02/18
4.6K
4
使用PyGtk Pixbuf及freetype-py 显示文本

使用PyGtk Pixbuf及freetype-py 显示文本 计算机上显示文本的过程大体上是,先将文本转换成一个一个的bitmap,然后再用图形系统将这些bitmap显示出来。freetype是一个open source的字体引擎,...

WolfCS
2013/06/01
1K
0
对比 Ruby 和 Python 的垃圾回收

注:这篇文章基于我在布达佩斯的RuPy大会上所作的演讲。我觉得与其直接将幻灯片发布出来,不如在我还有印象的时候将它写成博客来的更有意义。同 样,我会在将来发布RuPy大会的视频链接。我计...

oschina
2014/06/19
5K
28
LedisDB v0.1 发布,用Go实现的高性能NoSQL

高性能 NoSQL LedisDB v0.1 发布。 LedisDB 是一个底层采用LevelDB存储,用Go编写的高性能NoSQL,它在接口上面参考Redis,你可以很容易的从Redis进行迁移。 v0.1版本主要功能如下: 多种数据...

siddontang
2014/07/24
3.4K
11
常见数据结构的 Python 实现(建议收藏)

数据结构作为计算机基础的必修内容,也是很多大型互联网企业面试的必考题。可想而知,它在计算机领域的重要性。 然而很多计算机专业的同学,都仅仅是了解数据结构的相关理论,却无法用代码实...

实验楼
08/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
6
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
6
0
【技术分享】TestFlight测试的流程文档

上架基本需求资料 1、苹果开发者账号(如还没账号先申请-苹果开发者账号申请教程) 2、开发好的APP 通过本篇教程,可以学习到ios证书申请和打包ipa上传到appstoreconnect.apple.com进行TestF...

qtb999
昨天
10
0
再见 Spring Boot 1.X,Spring Boot 2.X 走向舞台中心

2019年8月6日,Spring 官方在其博客宣布,Spring Boot 1.x 停止维护,Spring Boot 1.x 生命周期正式结束。 其实早在2018年7月30号,Spring 官方就已经在博客进行过预告,Spring Boot 1.X 将维...

Java技术剑
昨天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部