专栏首页AI科技评论干货 | 漫画:什么是Bitmap算法?

干货 | 漫画:什么是Bitmap算法?

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

知乎地址:https://zhuanlan.zhihu.com/p/54783053

两个月之前——

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

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

两个月之后——

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

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

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

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

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

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

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

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

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

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

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

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

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

一周之后......

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

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

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

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

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

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

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

25769803776 L = 11000000000000000000000000000000000 B

8589947086 L = 1000000000000000000011000011001110 B

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

最终插入结果如下:

官方说明如下:

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

几点说明:

  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>

本文分享自微信公众号 - AI科技评论(aitechtalk),作者:玻璃猫

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 动态 | 谷歌开源猎星代码,AI时代的天文爱好者们该换装备了!

    天文爱好者们或许该学学机器学习了,在人工智能时代,用望远镜来猎星已经略 low。 AI 科技评论按:在去年 12 月份,谷歌训练了一个神经网络,通过分析美国宇航...

    AI科技评论
  • CVPR2019 | 面对高度不均衡数据如何提高精度?这篇文章有妙招

    本文是对 CVPR 2019 论文「Class-Balanced Loss Based on Effective Number of Samples」的一篇点评...

    AI科技评论
  • ML&NLP顶会论文发表总榜:谷歌最狂,清北入前十,周明、张岳、刘挺华人前三

    伦敦帝国理工学院机器学习和自然语言处理著名学者Marek Rei 教授从2016年起,每年都会对ML&NLP相关的会议论文进行统计和分析,并一年一度发表分析结果...

    AI科技评论
  • 2020年抖音用户画像报告

    抖音整体人群画像,男女较均衡,19-30岁TGI高,新一线、三线及以下城市用户TGI高。

    朱小五
  • 知识点——Java中的String类

    char charAt(int index); 获取String字符串中指定下标位置的char类型字符,如果index超出有效范围 StringIndexO...

    用户7073689
  • 基于haar特征+adboost分类器的人脸检测算法----haar特征

    人脸检测由来已久 ,它属于计算机视觉范畴。在早期的人脸检测研究中主要侧重于人脸的识别和人物身份的鉴定,后来在复杂背景下的人脸检测需求越来越大,人脸检测也逐渐作...

    FPGA开源工作室
  • 度小满金融战略投资哈银消金,“AI+”或成2019消费金融关键字

    同一时间,中国银保监会官网刊发《关于核准哈尔滨哈银消费金融有限责任公司增加注册资本和调整股权结构的批复》,度小满金融战略投资哈尔滨哈银消费金融有限责任公司(以下...

    罗超频道
  • 孟德尔随机化研究中评估因果效应大小的方法

    孟德尔随机化研究借助遗传变异这一工具变量,来评估暴露因素与结局变量之间的因果效用。为了准确评估因果效应的大小,有多种方法相继被发明。本文重点看下其中常用的两种方...

    生信修炼手册
  • 创建数据集模块常见设置

    创建数据集的主要功能是从数据库查询出所需的数据,从而进行数据分析。在创建数据集处,可以对数据进行一些简单的处理,如数据级别的权限设置,字段信息修改,字段管理等。

    腾讯云商业智能分析团队
  • 服务器添加ssl证书,基于Nginx配置 php环境

    文章时间:2017年9月23日 23:55分 基于系统:wdlinux,cent os 7.3 系统环境:Nginx,php,mysql

    华创信息技术

扫码关注云+社区

领取腾讯云代金券