<返回更多

用什么算法可以快速检索数据?Bitmap了解一下

2021-08-30    指尖java
加入收藏

一个关于用户标签的需求

为了帮助公司精准定位用户群体,咱们需要开发一个用户画像系统,实现用户信息的标签化。

用户标签包括用户的社会属性、生活习惯、消费行为等信息,例如下面这个样子。

用什么算法可以快速检索数据?Bitmap了解一下

 

通过用户标签,我们可以对多样的用户群体进行统计。例如统计用户的男女比例、统计喜欢旅游的用户数量等。

为了满足用户标签的统计需求,小灰利用关系数据库设计了如下的表结构,每一个维度的标签对应着数据库表中的一列:

用什么算法可以快速检索数据?Bitmap了解一下

 

要想统计所有“90后”的程序员,该怎么做呢?

用一条求交集的SQL语句即可。

用什么算法可以快速检索数据?Bitmap了解一下

 

看起来很简单嘛,嘿嘿……

事情没那么简单,现在标签越来越多,例如,用户去过的城市、消费水平、爱吃的东西、喜欢的音乐……都快有上千个标签了,这要给数据库表增加多少列啊!

筛选的标签条件过多的时候,拼出来的SQL语句像面条一样长……

不仅如此,当对多个用户群体求并集时,需要用distinct来去掉重复数据,性能实在太差了……

用BITMAP算法解决问题

你听说过Bitmap算法吗?在中文里叫作位图算法。

这里所说的位图并不是像素图片的位图,而是内存中连续的二进制位(bit)所组成的数据结构,该算法主要用于对大量整数做去重和查询操作。

举一个例子,假设给出一块长度为10bit的内存空间,也就是Bitmap,想要依次插入整数4、2、1、3,需要怎么做呢?

很简单,具体做法如下。

第1步,给出一块长度为10的Bitmap,其中的每一个bit位分别对应着从0到9的整型数。此时,Bitmap的所有位都是0(用紫色表示)。

用什么算法可以快速检索数据?Bitmap了解一下

 

第2步,把整型数4存入Bitmap,对应存储的位置就是下标为4的位置,将此bit设置为1(用黄色表示)。

用什么算法可以快速检索数据?Bitmap了解一下

 

第3步,把整型数2存入Bitmap,对应存储的位置就是下标为2的位置,将此bit设置为1。

用什么算法可以快速检索数据?Bitmap了解一下

 

第4步,把整型数1存入Bitmap,对应存储的位置就是下标为1的位置,将此bit设置为1。

用什么算法可以快速检索数据?Bitmap了解一下

 

第5步,把整型数3存入Bitmap,对应存储的位置就是下标为3的位置,将此bit设置为1。

用什么算法可以快速检索数据?Bitmap了解一下

 

如果问此时Bitmap里存储了哪些元素,显然是4、3、2、1,一目了然。

Bitmap不仅方便查询,还可以去掉重复的整数。

你仔细想一想,你所做的用户标签能不能用Bitmap的形式进行存储呢?

我的每一条用户数据都对应着成百上千个标签,怎么也无法转换成Bitmap的形式啊?

别急,我们不妨转换一下思路,为什么一定要让一个用户对应多个标签,而不是一个标签对应多个用户呢?

信息不一定非要以用户为中心存储,也能够以标签为中心来存储,让每一个标签存储包含此标签的所有用户ID,就像倒排索引一样!

第1步,建立用户名和用户ID的映射。

用什么算法可以快速检索数据?Bitmap了解一下

 

第2步,让每一个标签存储包含此标签的所有用户ID,每一个标签都是一个独立的Bitmap。

用什么算法可以快速检索数据?Bitmap了解一下

 

这样一来,每一个用户特征都变得一目了然。

例如,程序员和“00后”这两个群体,各自的Bitmap分别如下所示。

用什么算法可以快速检索数据?Bitmap了解一下

 

BitMap好处

1.高性能的位运算

2.相比使用哈希表的话,每一个用户ID都要用整型数据存储,少则占用4字节(32bit),多则占用8字节(64bit)。而一个用户ID在Bitmap中只占1bit,内存是使用哈希表所占用内存的1/32,甚至更少!

3.Bitmap在对用户群做交集和并集运算时也有极大的便利

如何取反操作呢

我们可以使用异或 运算进行操作,即相同位为0,不同位为1。

同样是刚才的例子,我们给出“90后”用户的Bitmap,再给出一个全量用户的Bitmap。最终要求出的是存在于全量用户,但又不存在于“90后”用户的部分。

用什么算法可以快速检索数据?Bitmap了解一下

 

实现方式

长度计算公式

int nSize = (width * bitPixel + 64) / 64 ;

(高效写法是(((width * bitPixel + 64)>>6)) )

通过位移操作,可以很方便的扩容

而且越往上就是指数扩容,满足过亿级别数据量的时间复杂度也是O(1)

class MyBitmap:
    def __init__(self,size):
        self.words=[0]*(self.get_word_index(size-1)+1)
        self.size=size
    def get_bit(self,bit_index):
        if bit_index<0 or bit_index>self.size-1:
            raise Exception("超过Bitmap有效范围!")
        word_index=self.get_word_index(bit_index)
        return (self.words[word_index]&(1<<bit_index))!=0
    def set_bit(self,bit_index):
        if bit_index<0 or bit_index>self.size-1:
            raise Exception("超过Bitmap有效范围!")
        word_index=self.get_word_index(bit_index)
        self.words[word_index] |=(1<<bit_index)
    def get_word_index(self,bit_index):
        #右移6位,相当于除以64
        return bit_index>>6

bitMap=MyBitmap(128)
bitMap.set_bit(126)
bitMap.set_bit(75)
print(bitMap.get_bit(126))
print(bitMap.get_bit(78))
声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多资讯 >>>