BITMAP - 知乎 - 程序猿·D·安宇雨 DeepMind

BITMAP - 知乎

安宇雨 - 随手采集
2023-05-19 12:12:22
随手采集
0000-未整理-等待研究

bitmap 常用的应用场景：

1.超大文件求交集：现有两个各有20亿行的文件，每一行都只有一个数字，求这两个文件的交集。

2.从海量电话号码中，统计不同号码的个数

3.统计APP的日活

4.bitmap实现大数据排序和去重

问题的引出：

有这样一种场景:一台普通PC，2G内存，要求处理一个包含40亿个不重复并且没有排过序的无符号的int整数，给出一个整数，问如果快速地判断这个整数是否在文件40亿个数据当中？

bitmap的建立：

40亿个int占（40亿*4（long int 是 4 byte））/1024（转为KB）/1024(转为MB)/1024（转为GB）大概为14.9G左右，很明显内存只有2G，放不下，因此不可能将这40亿数据放到内存中计算。

ps：_1_KB=1024B;_1_MB=1024KB=1024×1024B；_1_B(byte,_字节_)= 8 _bit_(位）

一个int整数在Python中是占4个字节的即要32bit位，如果能够用一个bit位来标识一个int整数那么存储空间将大大减少，算一下40亿个int需要的内存空间为40亿/8/1024/1024大概为476.83 mb，这样的话我们完全可以将这40亿个int数放到内存中进行处理。

具体思路(BitMap思想)：

1个int占4字节即4*8=32位，那么我们只需要申请一个int数组长度为 int tmp[1+N/32]即可存储完这些数据，其中N代表要进行查找的总数，tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:

tmp[0]:可表示0~31

tmp[1]:可表示32~63

tmp[2]可表示64~95

.......

那么接下来就看看十进制数如何转换为对应的bit位：

假设这40亿int数据为：6,3,8,32,36,......，那么具体的BitMap表示为：

(1)如何判断int数字放在哪一个tmp数组中：将数字直接除以32取整数部分(x/32)，例如：整数8除以32取整等于0，那么8就在tmp[0]上，而32/32取整数=1，所以是在tmp[1]，在Python直接就是32//32即可；

(2)如何确定数字放在32个位中的哪个位（从0开始）：将数字mod32(x%32)。上例中我们如何确定8在tmp[0]中的32个位中的哪个位，这种情况直接mod上32就ok，又如整数8，在tmp[0]中的第8mod上32等于8，那么整数8就在tmp[0]中的第八个bit位（从右边数起）。

综上：用num//32就得在哪个array里（某一行），具体是个下标用num%32（某一列）即可。

接下来的任务是怎么添加数字，和清除数字：

几个位运算的知识：

<< ： 1的二进制表示：00000001，1<<3 的结构是00001000，就是把所有的位都往左边移动3位

1：运算规则：0|0=0； 0|1=1； 1|0=1； 1|1=1；

例如:3|5　即 00000011 | 0000 0101 = 00000111 因此，3|5的值得7。　

&：运算规则：0&0=0; 0&1=0; 1&0=0; 1&1=1;

即：两位同时为“1”，结果才为“1”，否则为0

例如：3&5 即 0000 0011& 0000 0101 = 00000001 因此，3&5的值得1。

～：取反

1:Clear方法（将数组的所有bit位置0）

比如要将当前4对应的bit位置0的话，只需要1左移4位取反与B[0] & 即可。

2:Add方法（将bit置1操作）

同样也很简单，要将当前4对应的bit位置1的话，只需要1左移4位与B[0] | 即可。

3. search方法

要查找当前4对应的bit位置是否为1，只需要1左移4位与B[0]& 即可。

整体的Python 代码：

下面的代码实现了bitmap实现大数据排序和去重

# -*- encoding:utf-8 -*-
import math
class Bitmap():
    def __init__(self,max):
        '确定所需数组个数'
        self.size = math.ceil (max/ 32)
        self.array = [0 for i in range(self.size)]
    def bitindex(self,num):
        '确定数组中元素的位索引'
        return num % 32
    def set_1(self,num):
        '将元素所在的位置1'
        elemindex = num // 32
        byteindex = num % 32
        ele = self.array[elemindex]
        print(byteindex)
        print('the original array ele {}'.format(format( ( ele), 'b').zfill(32)))
        print('need  insert byteindex {}'.format(format((1 << byteindex), 'b').zfill(32)))
        self.array[elemindex] = ele | (1 << byteindex)
        print('after insert byteindex {} \n'.format(format((self.array[elemindex]), 'b').zfill(32)))

    def search_1(self,i):
        '检测元素存在的位置'
        elemindex = i // 32
        byteindex = self.bitindex(i)
        try:
            self.array[elemindex]
        except:
            print(elemindex)
        if self.array[elemindex] & (1 << byteindex):
            return True
        return False

if __name__ == '__main__':
    Max = ord('z')
    suffle_array = [x for x in 'qwelmfg']
    result = []
    bitmap = Bitmap(Max)
    for c in suffle_array:
        bitmap.set_1(ord(c))

    for i in range(Max+1):
        if bitmap.search_1(i):
            result.append(chr(i))
    print (u'原始数组为: %s' % suffle_array )
    print (u'排序后的数组为: %s' % result)

bitmap在线上系统的应用：

id表示用户的id

如上图是一个数据表有四列，下面是一个简单查询，查询有性别和婚姻状况两个维度，性别有两个取值，婚姻状况有三个取值，BitMap首先会在维度里面构建BitMap，第一步如何构建性别的BitMap，对于性别这个列，位图索引形成两个向量，男向量为10100...，向量的每一位表示该行是否是男，如果是则位1，否为0，同理，女向量位01011。第二部构建婚姻状况的BitMap，婚姻状况这一列，位图索引生成三个向量，已婚为11000...，未婚为00100...，离婚为00010...。这样就构建完需要查询的BitMap，首先将性别为男的标签拿出来，然后将婚姻状况为未婚的标签拿出来求交，这样就定为下标为2，就查出满足需要的结果。

可以看出上图的列数随着用户增多不断加长，这个是最后有上限，也是不利于分布式计算，因此需要将id分区