您正在使用IE低版浏览器,为了您的雷峰网账号安全和更好的产品体验,强烈建议使用更快更安全的浏览器
此为临时链接,仅用于文章预览,将在时失效
人工智能 正文
发私信给skura
发送

0

漫画:什么是Bitmap算法?

本文作者: skura 2019-03-08 22:09
导语:看漫画学知识

雷锋网 AI 科技评论按,本文本文来自公众号“程序员小灰”(ID:chengxuyuanxiaohui),原载于知乎,雷锋网获授权转载。

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?

两个月之前——

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?


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

漫画:什么是Bitmap算法?

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

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

Select count(distinct Name) as 用户数 from table whare age = '90后' and Occupation = '程序员' ;

要想统计所有使用苹果手机或者00后的用户总合该怎么做?

用一条求并集的SQL语句即可:

Select count(distinct Name) as 用户数 from table whare Phone = '苹果' or age = '00后' ;

漫画:什么是Bitmap算法?

两个月之后——

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

———————————————

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?

1. 给定长度是 10 的 bitmap,每一个 bit 位分别对应着从 0 到 9 的 10 个整型数。此时 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算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

  1. 建立用户名和用户 ID 的映射:

    漫画:什么是Bitmap算法?

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

漫画:什么是Bitmap算法?

3. 这样,实现用户的去重和查询统计,就变得一目了然:

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

  1. 如何查找使用苹果手机的程序员用户?

    漫画:什么是Bitmap算法?

  2. 如何查找所有男性或者00后的用户?

    漫画:什么是Bitmap算法?

    漫画:什么是Bitmap算法?

    漫画:什么是Bitmap算法?

    漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

一周之后......

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

我们以上一期的用户数据为例,用户基本信息如下。按照年龄标签,可以划分成 90 后、00 后两个 Bitmap:

漫画:什么是Bitmap算法?

用更加形象的表示,90 后用户的 Bitmap 如下:

漫画:什么是Bitmap算法?

这时候可以直接求得非90后的用户吗?直接进行非运算?

漫画:什么是Bitmap算法?

显然,非 90 后用户实际上只有 1 个,而不是图中得到的 8 个结果,所以不能直接进行非运算。

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

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

漫画:什么是Bitmap算法?

如何求出呢?我们可以使用异或操作,即相同位为 0,不同位为 1。

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?

【 图片来源:null  所有者:null 】

漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

25769803776 L  =  11000000000000000000000000000000000 B

8589947086 L = 1000000000000000000011000011001110 B

漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?

1.解析 Word 0,得知当前 RLW 横跨的空 Word 数量为 0,后面有连续 3 个普通 Word。

2.计算出当前 RLW 后方连续普通 Word 的最大 ID 是  64 X  (0 + 3) -1 = 191。

3. 由于 191 < 400003,所以新 ID 必然在下一个 RLW(Word4)之后。

4.解析 Word 4,得知当前 RLW 横跨的空 Word 数量为 6247,后面有连续 1 个普通 Word。

5.计算出当前 RLW(Word4)后方连续普通 Word 的最大 ID 是 191 + (6247 + 1)X64  = 400063。

6.由于 400003 < 400063,因此新 ID 400003 的正确位置就在当前 RLW(Word4)的后方普通 Word,也就是 Word 5 当中。

最终插入结果如下:

漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

官方说明如下:

* Though you can set the bits in any order (e.g., set(100), set(10), set(1),
* you will typically get better performance if you set the bits in increasing order (e.g., set(1), set(10), set(100)).
*
* Setting a bit that is larger than any of the current set bit
* is a constant time operation. Setting a bit that is smaller than an
* already set bit can require time proportional to the compressed
* size of the bitmap, as the bitmap may need to be rewritten.

漫画:什么是Bitmap算法?

几点说明:

  1. 该项目最初的技术选型并非Mysql,而是内存数据库hana。本文为了便于理解,把最初的存储方案写成了Mysq数据库。

  2. 文中介绍的Bitmap优化方法在一定程度上做了简化,源码中的逻辑要复杂得多。比如对于插入数据400003的定位,和实际步骤是有出入的。

  3. 如果同学们有兴趣,可以亲自去阅读源码,甚至是尝试实现自己的Bitmap算法。虽然要花不少时间,但这确实是一种很好的学习方法。

EWAHCompressedBitmap对应的maven依赖如下:

<dependency>
 <groupId>com.googlecode.javaewah</groupId>
 <artifactId>JavaEWAH</artifactId>
 <version>1.1.0</version>
</dependency>

雷峰网版权文章,未经授权禁止转载。详情见转载须知

漫画:什么是Bitmap算法?

分享:
相关文章
当月热门文章
最新文章
请填写申请人资料
姓名
电话
邮箱
微信号
作品链接
个人简介
为了您的账户安全,请验证邮箱
您的邮箱还未验证,完成可获20积分哟!
请验证您的邮箱
立即验证
完善账号信息
您的账号已经绑定,现在您可以设置密码以方便用邮箱登录
立即设置 以后再说