扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > Python >Python: 实现bitmap数据结构
  • 291

0
分享到

Python: 实现bitmap数据结构

数据结构Pythonbitmap 2023-01-31 02:01:53 291人浏览 薄情痞子

Python 官方文档：入门教程 => 点击学习

摘要

Http://my.oschina.net/Goal/blog/200347  bitmap是很常用的数据结构，比如用于Bloom Filter中、用于无重复整数的排序等等。bitmap通常基于数组来实现，数组中每个元


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即可，这点请大家注意。


您可能感兴趣的文档:

--结束END--

本文标题: Python: 实现bitmap数据结构

本文链接: https://lsjlt.com/news/186844.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • Python: 实现bitmap数据结构
    http://my.oschina.net/goal/blog/200347  bitmap是很常用的数据结构，比如用于Bloom Filter中、用于无重复整数的排序等等。bitmap通常基于数组来实现，数组中每个元...
    99+
    2023-01-31
    数据结构 Python bitmap
  • [Python]数据结构--Bitmap
    ‘Festinatione facit vastum’ Bitmap简介 Bitmap的实现和使用 Bitmap简介 bitmap是很常用的数据结构，比如用于Bloom Filter中、用于无重复整数的排序等等。bit...
    99+
    2023-01-31
    数据结构 Python Bitmap
  • C++如何实现BitMap数据结构
    目录一、BitMap位图二、C++实现分治，分布式。BitMap(位图)及其升级版bloom filter是处理海量数据常用的方法，这里先介绍BitMap概念及其c++实现。 一、B...
    99+
    2024-04-02
  • go数据结构和算法BitMap原理及实现示例
    目录1. BitMap介绍如何判断数字在bit数组的位置设置数据到bit数组从bit数组中清除数据数字是否在bit数组中2. Go语言位运算左移右移使用&^和位移运算来给某一...
    99+
    2024-04-02
  • 用Python实现数据结构之树
    树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树...
    99+
    2023-01-30
    数据结构 之树 Python
  • 用Python实现数据结构之栈
    栈是最简单的数据结构，也是最重要的数据结构。它的原则就是后进先出（LIFO），栈被使用于非常多的地方，例如浏览器中的后退按钮，文本编辑器中的撤销机制，接下来我们用Python来具体实现这个数据结构。 栈中的方法 作为一个栈（用S来表示...
    99+
    2023-01-30
    数据结构 Python
  • 用python实现各种数据结构
    目录快速排序选择排序插入排序归并排序堆排序heapq模块栈队列二分查找快速排序 def quick_sort(_list): if len(_li...
    99+
    2024-04-02
  • Python 数据结构之队列的实现
    Python 队列 Queue 队列是一种先进先出(FIFO)的数据类型, 新的元素通过 入队 的方式添加进 Queue 的末尾, 出队 就是从 Queue 的头部删除元素. 用列表来做 Queue: ...
    99+
    2022-06-04
    数据结构 队列 Python
  • Python实现基本线性数据结构
    数组 数组的设计 数组设计之初是在形式上依赖内存分配而成的，所以必须在使用前预先请求空间。这使得数组有以下特性： 1、请求空间以后大小固定，不能再改变（数据溢出问题）； 2、在内存...
    99+
    2022-06-04
    数据结构 线性 Python
  • 数据结构：链表（Python语言实现）
    链表分为单链表、双链表、循环单链表和循环双链表。 本文以单链表为例，用python创建一个单链表数据结构，同时定义链表节点的增加、删除、查询和打印操作。 一、创建节点类 创建一个名为Node的节点类，节点类里面包含2个属性和1个方法。...
    99+
    2023-09-24
    链表 数据结构 python 算法 Powered by 金山文档
  • 用Python实现数据结构之链表
    链表与栈，队列不一样，它是由一个个节点构成的，每个节点存储着本身的一些信息，也存储着其他一个或多个节点的引用，可以从一个节点找到其他的节点，节点与节点之间就像是有链连在一起一样，这种数据结构就叫做链表 单向链表是链表的最简单形式，链表...
    99+
    2023-01-30
    数据结构 链表 Python
  • 用Python实现数据结构之队列
    队列与栈的类型很相似，但它遵循的原则是先进先出（FIFO），也就是元素插入的时候只能在该数据结构的末端，而删除只能删除最前面的元素。队列同样应用广泛，例如打印机的队列或者是一个web服务器响应请求。 关于队列的方法 作为一个队列，同样...
    99+
    2023-01-30
    数据结构 队列 Python
  • python 数据结构
    list（列表）创建list方式1  ： 直接创建  theList = [1,2,3,4,5,6,7,8,9]                    ==> [1,2,3,4,5,6,7,8,9]方式2 ： 使用内建方法list()...
    99+
    2023-01-31
    数据结构 python
  • python数据结构
    一：数据结构  数据结构可以认为他们是用来处理一些数据的或者说是存储数据。  对于数据结构的介绍会关系到类和对象的定义，此处对这两个定义加以描述。  何为类：说道类首先我们能够想到类型，在数据结构中类型有哪些常用的类型有int整型，floa...
    99+
    2023-01-31
    数据结构 python
  • redis bitmap数据结构之java对等操作详解
    目录1. Redis基本的bitmap操作命令2. Java中的原生bitmap3. java和redis的bitmap互操作　　在之前的文章中，我们有说过bitmap，bitmap在很多场景可以应用，比如黑白名单，快速...
    99+
    2024-04-02
  • redis bitmap数据结构之java对等操作详解
    目录1. redis基本的bitmap操作命令2. java中的原生bitmap3. java和redis的bitmap互操作　　在之前的文章中，我们有说过bitmap，bitmap...
    99+
    2022-11-13
    redis bitmap数据结构 java对等操作 redis bitmap
  • 【数据结构】Java实现栈
    目录 1. 概念 2. 栈的使用  3. 自己动手实现栈（使用动态数组实现栈）  1. 创建一个MyStack类 2. push入栈 3. pop出栈 4. 查看栈顶元素 5. 判断栈是否为空与获取栈长 6. toString方法 4. 整...
    99+
    2023-10-27
    数据结构 jvm java
  • 怎么用python实现各种数据结构
    这篇文章主要为大家展示了“怎么用python实现各种数据结构”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“怎么用python实现各种数据结构”这篇文章吧。快速排序def quick_s...
    99+
    2023-06-22
  • 数据结构之——Python实现循环队列
    栈是先入后出，与之相反的是队列，队列是先进先出的线性结构。队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。 图1 队列的定义 队列的存储结构中使用的最多的是循...
    99+
    2023-01-31
    数据结构 队列 Python
  • python 数据结构篇
    在众多编程语言里，数据结构与算法都可以说是至关重要的基础。但是对于python而言，因为其本身就是用C实现的，其速度和效率本身较低，因而pyhon没有像其他语言那样那么重视数据结构与算法（python最引以为傲的应该是其功能强大而丰富的各种...
    99+
    2023-09-13
    python 开发语言 数据结构
软考高级职称资格查询
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作