bitmap算法的python实现

淡淡的烟草味﹌ 2023-03-03 13:27 16阅读 0赞

# 0 引入 #

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

本文使用python实现bitmap算法。  
由于算法储存数据的粒度到了位，因此代码中使用了很多位运算，先回顾一下python中的位运算操作。

# 或运算
    >>> bin(10), bin(8)
    ('0b1010', '0b1000')
    >>> bin(10 | 8)
    '0b1010'
    
    # 与预算
    >>> bin(10), bin(8)
    ('0b1010', '0b1000')
    >>> bin(10 & 8)
    '0b1000'
    
    # 位移运算
    >>> bin(10)
    '0b1010'
    >>> bin(10 << 3)
    '0b1010000'

# 1 设计思想 #

代码中使用n个4字节的整数来储存数据，每个整数有32位。  
![在这里插入图片描述][20200731171632645.png]  
假定我们要储存的客户的ID，元素个数n根据需要储存的最大ID计算得到。

然后循环的把ID存储bitmap中，储存每个ID时，先计算ID对应的元素下标和在元素中的存在第几位。  
例如我们要储存的ID是30，通过后面的`get_element_index`和`get_bit_index`函数的计算分别得到元素下标是0，储存位数是30。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTE5ODQwNg_size_16_color_FFFFFF_t_70]  
然后把第0个元素的第30位（从0开始）置为1即可。

# 2 代码 #

class BitMap(object):
        def __init__(self, max_value):
            """
            使用多个整型元素来储存数据，每个元素4个字节（32位）
            """
            self._size = int((max_value + 31 - 1) / 31)  # 计算需要的字节数，字节数也是数组的大小
            self.array = [0 for i in range(self._size)]  # 数组的元素都初始化为0，每个元素有32位
    
        @staticmethod
        def get_element_index(num):
            """
            获取该数即将储存的字节在数组中下标
            """
            return num // 31
    
        @staticmethod
        def get_bit_index(num):
            """
            获取该数在元素中的位下标
            """
            return num % 31
    
        def set(self, num):
            """
            将该数存在对应的元素的对应位置
            """
            element_index = self.get_element_index(num)
            bit_index = self.get_bit_index(num)
            self.array[element_index] = self.array[element_index] | (1 << bit_index)
    
        def find(self, num):
            """
            查找该数是否存在与bitmap中
            """
            element_index = self.get_element_index(num)
            bit_index = self.get_bit_index(num)
            if self.array[element_index] & (1 << bit_index):
                return True
            return False
    
        def count_one(self):
            """
            统计bitmap中数据的个数
            """
            count = 0
            for n in self.array:
                while n > 0:
                    n = n & (n - 1)
                    count += 1
            return count
    
    
    def main():
        array_list = [30, 32, 5, 45, 2, 78, 35, 67, 90, 879, 0, 340, 123, 46, 1, 5]
        # 根据最大数的值创建BitMap对象
        bitmap = BitMap(max_value=max(array_list))
    
        # 将数据逐个存入bitmap
        for num in array_list:
            bitmap.set(num)
    
        # 查询数据是否存在于bitmap中
        results = []
        for i in range(max(array_list) + 1):
            if bitmap.find(i):
                results.append(i)
        print(results)
    
    
    if __name__ == '__main__':
        main()

[20200731171632645.png]: /images/20230208/087c737b1e35440ead5e8d77aa89da64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTE5ODQwNg_size_16_color_FFFFFF_t_70]: /images/20230208/6e7bdff8df7741fcbe2427df7540163c.png