python使用位图对数据进行排序

位图简介

BitMap是很常用的数据结构，可以用来无重复整数的排序等，通常位图需要借助列表进行实现，列表中的每一个数字，都是有一系列二进制的整数的集合。在python中，整数默认为有符合类型，因此，一个整数4个字节，最大能有31位存储数据，1位存储符号位。
位图实现

获取分组索引、修改bit位值（位运算）

array_index = num // 31 + 1

修改的值的bit位置

bit_index = num % 31

代码实现

# -*- coding:utf-8 -*-
# @Time     : 2020-08-26 12:47
# @Author   : 宋晓奎
# @Email    : austsxk@vip.qq.com
# @File     : 9_bitMap.py
# @Software : PyCharm


class BitMap(object):
    def __init__(self, num: int) -> None:
        """
        初始化数组的大小，并初始化数组
        :param num: 需要排序的最大数字
        """
        self.size = int(int(num) / 31) + 1
        self.array = [0 for _ in range(self.size)]

    @staticmethod
    def bit_index(number: int) -> int:
        """
        确认索引的位置
        :return: 索引的位置
        """
        return number % 31

    def setNumOne(self, number: int) -> None:
        """
        将数字保存在位图中，并设置为1
        :param number: 数字
        :return:
        """
        # 确定数据应该保存在数组的哪个索引
        element_index = number // 31
        byte_index = self.bit_index(number)
        element = self.array[element_index]
        # 将那一位置为1
        self.array[element_index] = element | (1 << byte_index)

    def haveNum(self, num: int) -> bool:
        """
        判断是否存在该数值
        :param num: 元素ascII
        :return:
        """
        element_index = num // 31
        byte_index = self.bit_index(num)
        if self.array[element_index] & (1 << byte_index):
            return True
        else:
            return False


if __name__ == '__main__':
    max_num = ord('z')
    print(max_num)
    b = BitMap(max_num)
    strings = "afsielhb"
    for i in strings:
        b.setNumOne(ord(i))
    result = []
    for i in range(0, max_num + 1):
        if b.haveNum(i):
            result.append(chr(i))
    print("原始数据为:", strings)
    print("排序后数据:", "".join(result))

~~ 欢迎 ~~

欢迎