[Python]数据结构--Bitmap
短信预约 -IT技能 免费直播动态提醒
‘Festinatione facit vastum’
- Bitmap简介
- Bitmap的实现和使用
Bitmap简介
bitmap是很常用的数据结构,比如用于Bloom Filter中、用于无重复整数的排序等等。bitmap通常基于数组来实现,数组中每个元素可以看成是一系列二进制数,所有元素组成更大的二进制集合。对于Python来说,整数类型默认是有符号类型,所以一个整数的可用位数为31位。
Bitmap的实现和使用
bitmap实现思路
bitmap是用于对每一位进行操作。举例来说,一个Python数组包含4个32位有符号整型,则总共可用位为4 * 31 = 124位。如果要在第90个二进制位上操作,则要先获取到操作数组的第几个元素,再获取相应的位索引,然后执行操作。
代码:
# encoding: utf-8
"""
@author: JYFelt
@contact: JYFelt@163.com
@site: www.JYFelt.com
@version: 1.0
@license: Apache Licence
@file: bitmap_demo.py
@time: 2018/1/13 13:46
这一行开始写关于本文件的说明与解释
"""
# 初始化bitmap
class Bitmap():
def __init__(self, max):
"""确定数组个数"""
self.size = int((max + 31 - 1) / 31)
# max需要传入的为要排序的最大数
self.array = [0 for i in range(self.size)]
def bitindex(self, num):
"""确定数组中元素的位索引"""
return num % 31
def set_1(self, num):
"""将元素所在的位——置1"""
elemindex = (num // 31) # 整除,否则为浮点值
byteindex = self.bitindex(num)
ele = self.array[elemindex]
self.array[elemindex] = ele | (1 << byteindex)
def test_1(self, i):
elemindex = (i // 31) # 整除,否则为浮点值
byteindex = self.bitindex(i)
if self.array[elemindex] & (1 << byteindex):
return True
return False
if __name__ == '__main__':
Max = ord('z') # ord('*')返回单字符在ASCII中对应的整数
shuffle_array = [x for x in 'qwelajkda']
ret = []
bitmap = Bitmap(Max)
for c in shuffle_array:
bitmap.set_1(ord(c))
for i in range(Max + 1):
if bitmap.test_1(i):
ret.append(chr(i))
print(u'原始数组是:%s' % shuffle_array)
print(u'排序以后的数组是:%s' % ret)
免责声明:
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341