专栏首页python3[Python]数据结构--Bitmap

[Python]数据结构--Bitmap

[Python]数据结构–Bitmap 位图

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python + PyQt4 实现记事本

    该部分设计类同Visval Studio内的设计,改下各部件的objectName!

    py3study
  • python 中的嵌套类

    能够看到 类中 又定义了 类 ,这种情况我们称之为嵌套类 。给一个简单 demo 来认识嵌套类 。

    py3study
  • 用Python编写一个简单的Http S

    原文地址:Write a simple HTTP server in Python http://www.acmesystems.it/python_htt...

    py3study
  • 清除远程桌面访问痕迹

    清除远程桌面访问痕迹。使用windows系统自带的“远程桌面协助”mstsc进行远程,如果连接的用户多了,会留下访问的痕迹。虽然能带来方便,但是如果对于公用...

    似水的流年
  • 清除远程桌面访问痕迹

    清除远程桌面访问痕迹。使用windows系统自带的“远程桌面协助”mstsc进行远程,如果连接的用户多了,会留下访问的痕迹。虽然能带来方便,但是如果对于公用电脑...

    似水的流年
  • Python中的魔法函数总结整理

    py3study
  • 如何理解 rust 中的 Sync、Send?

    Sync 和 Send 是 rust 安全并发中两个至关重要的 marker,但绝大多数的文档或书籍每当谈到它们就只是直接抛出它们的语义:

    MikeLoveRust
  • TMD的后劲

    日前,《财经》宋玮《对话沈南鹏:价值观的胜利》一文在互联网圈刷屏,不少问题都引发行业热议,我发现其中有一个话题特别有意思,涉及到当下炙手可热的三家超级独角兽:头...

    罗超频道
  • Django的拾遗

    django中设置返回的状态码和头部信息 下面先给出我工作中使用到的代码: response = ReturnJson(data, status...

    若与
  • pygame 笔记-2 模仿超级玛丽的弹跳

    https://www.youtube.com/watch?v=2-DNswzCkqk

    菩提树下的杨过

扫码关注云+社区

领取腾讯云代金券