美文网首页
漫画:什么是Bitmap算法?

漫画:什么是Bitmap算法?

作者: Yobhel | 来源:发表于2020-05-25 10:44 被阅读0次

原文来自公众号“程序员小灰”(ID:chengxuyuanxiaohui),原载于知乎

image image image image

两个月之前——

image image image image image

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

image

要想统计所有 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 后' ;

image

两个月之后——

image image image image

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

image image image image image

1. 给定长度是 10 的 bitmap,每一个 bit 位分别对应着从 0 到 9 的 10 个整型数。此时 bitmap 的所有位都是 0。

image

2. 把整型数 4 存入 bitmap,对应存储的位置就是下标为 4 的位置,将此 bit 置为 1。

image

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

image

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

image

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

image

要问此时 bitmap 里存储了哪些元素?显然是 4,3,2,1,一目了然。

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

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

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

image

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

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

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

    image image image image image image image image
image

一周之后......

image image image image

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

image

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

image

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

image

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

image image

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

image

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

image image image

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

image image image image image image image image image image.png image image image image image image image image image image image image image image image image image image image image image image

25769803776 L = 11000000000000000000000000000000000 B

8589947086 L = 1000000000000000000011000011001110 B

image image image image image image

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 当中。

最终插入结果如下:

image image image image image

官方说明如下:

* 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.

image

几点说明:

  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 算法?

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

  • 漫画:什么是Bitmap算法?

    原文来自公众号“程序员小灰”(ID:chengxuyuanxiaohui),原载于知乎。 两个月之前—— 为满足用...

  • 漫画算法:Bitmap算法(进阶篇)

    之前分享了Bitmap算法的基本概念,小伙伴们的互动十分积极,在此很感谢大家的热情。 没看过上一期漫画的朋友们可以...

  • 布隆过滤器

    什么是布隆过滤器 布隆过滤器(Bloom Filter) 是一种以Bitmap为基础的排重算法。由Bitmap和一...

  • 【算法与数据结构专场】BitMap算法基本操作代码实现

    上篇我们讲了BitMap是如何对数据进行存储的,没看过的可以看一下【算法与数据结构专场】BitMap算法介绍 这篇...

  • No.14 【大数据算法】BitMap的原理和实现

    0x00 前言 本篇是大数据算法系列 第一篇《BitMap的原理和实现》,BitMap 的思想的和原理是很多算法的...

  • 漫画:什么是AES算法?

    假设有一个发送方在向接收方发送消息。如果没有任何加密算法,接收方发送的是一个明文消息:“我是小灰” 如果消息被中间...

  • 漫画:什么是DES算法

    网络传输经常采用http的方式,假设一个发送方向接收方发送消息,如果没有任何加密算法。那么消息在被中间人截获到之后...

  • 算法:BitMap

    BitMap 算法 引导 如果我们现在有一堆数据,[0 ,3 ,4 ,7 ,9 ,1 ,2 ,5 ,6 ,8 ,2...

  • 算法 - BitMap

    基本思想: 所谓的BitMap就是用一个bit位来标记某个元素所对应的value,而key即是该元素,由于BitM...

网友评论

      本文标题:漫画:什么是Bitmap算法?

      本文链接:https://www.haomeiwen.com/subject/shgeahtx.html