文章详情

登录

短信预约-IT技能 免费直播动态提醒

选择考试省份

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团

请输入下面的图形验证码

提交验证

短信预约提醒成功

Python: 实现bitmap数据结构

2023-01-31 02:41

关注


http://my.oschina.net/goal/blog/200347 

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并向上取整则可得知需要几个数组元素。代码如下：

?
1
2
3
4
5
6
7
8
9
10
#!/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

?
1
2
$ python bitmap.py
需要 3 个元素。

计算索引

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

  1. 计算在数组中的索引

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

计算在数组中的索引

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/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)

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

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

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#!/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),)

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

别忘了是从第0位算起哦。

置1操作

二进制位默认是0，将某位置1则表示在此位存储了数据。代码改为如下：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#!/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

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

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

清0操作

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#!/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

?
1
2
3
4
$ python bitmap.py
[1, 8, 0]
[0, 8, 0]
[0, 0, 0]

清0和置1是互反操作。

测试某位是否为1

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#!/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)

?
1
2
3
4
5
6
$ python bitmap.py
[1, 0, 0]
True
True
False
False

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#!/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

?
1
2
3
$ 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即可，这点请大家注意。


阅读原文内容投诉

免责声明：

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题

  • 2024年上半年信息系统项目管理师第二批次真题及答案解析（完整版）

    难度     813人已做
    查看

  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看

  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看

  • 2024年上半年软考高项第一、二批次真题考点汇总（完整版）

    难度     435人已做
    查看

  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机

Python: 实现bitmap数据结构

后端开发2023-01-31

[Python]数据结构--Bitmap

后端开发2023-01-31

C++如何实现BitMap数据结构

后端开发2024-04-02

go数据结构和算法BitMap原理及实现示例

后端开发2024-04-02

用python实现各种数据结构

后端开发2024-04-02

用Python实现数据结构之栈

后端开发2023-01-30

用Python实现数据结构之树

后端开发2023-01-30

用Python实现数据结构之链表

后端开发2023-01-30

Python实现基本线性数据结构

后端开发2022-06-04

Python 数据结构之队列的实现

后端开发2022-06-04

用Python实现数据结构之队列

后端开发2023-01-30

数据结构：链表（Python语言实现）

后端开发2023-09-24

怎么用python实现各种数据结构

后端开发2023-06-22

数据结构之——Python实现循环队列

后端开发2023-01-31

redis bitmap数据结构之java对等操作详解

后端开发2022-11-13

redis bitmap数据结构之java对等操作详解

后端开发2024-04-02

栈的实现：Python数据结构与算法

后端开发栈Python2024-11-30

python数据结构

后端开发2023-01-31

【数据结构】Java实现栈

后端开发2023-10-27

python 数据结构

后端开发2023-01-31
位置：首页-资讯-后端开发
咦！没有更多了？去看看其它编程学习网 内容吧
首页课程
资料下载问答资讯