专栏首页趣谈编程牛逼的Bitmap算法

牛逼的Bitmap算法

两个月之前——

为满足用户标签的统计需求,小灰利用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。

25769803776L = 11000000000000000000000000000000000B

8589947086L = 1000000000000000000011000011001110B

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

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

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

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

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

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

最终插入结果如下:

官方说明如下:

* 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数据库。

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

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

EWAHCompressedBitmap对应的maven依赖如下:
<dependency>
  <groupId>com.googlecode.javaewah</groupId>
  <artifactId>JavaEWAH</artifactId>
  <version>1.1.0</version>
</dependency>

本文分享自微信公众号 - 趣谈编程(qutanbiancheng)

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

原始发表时间:2019-09-18

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 深入浅出Spring IOC(二)

    上一篇文章 深入浅出Spring IOC(一)我们介绍了Spring的IOC,即控制反转,Spring来创建对象,程序中需要使用对象时,直接通过Spring容器...

    用户1260737
  • 二分查找

    面试官:写个二分热热身 我心想:不用热身,热的手已经出汗了 二分查找有着查找速度快,平均性能好等优点,但必须要求待查表为有序表,且插入删除困难,面试比较常考,今...

    用户1260737
  • 【面试现场】如何在10亿数中找出前1000大的数

    小史:我可以用分治法,这有点类似快排中partition的操作。随机选一个数t,然后对整个数组进行partition,会得到两部分,前一部分的数都大于t,后一部...

    用户1260737
  • 数据增长案例:中原地产用数据挽留22%流失用户,赋能6万经纪人

    最近在思考大宗高价产品的营销增长案例,看到了中原地产营销增长负责人在增长大会的分享,觉得还是比较全面和充分的,下面就分享大致的演讲内容:

    沉默的白面书生
  • 小朋友学C语言(30):局部变量和全局变量

    (一)局部变量 在某个函数或块的内部声明的变量称为局部变量。它们只能被该函数或该代码块内部的语句使用。局部变量在函数外部是不可知的。下面是使用局部变量的实例。在...

    海天一树
  • 深入浅出mybatis之映射器

    映射器是MyBatis中最核心的组件之一,在MyBatis 3之前,只支持xml映射器,即:所有的SQL语句都必须在xml文件中配置。而从MyBatis 3开始...

    2Simple
  • 前端技术观察第23期

    ConardLi
  • java数组的另一种用法

    每一个enum实例,一个不同的子类 你可以重载一个enum实例的方法。这将高效的给一个enum的实例一个自己的实现。

    用户5166556
  • FPGA/ASIC笔试面试题集锦(1)知识点高频复现练习题

    本文其实就是整合了一下去年秋招时总结的笔试题或者各大平台的练习题,只不过去年由于边笔试面试边总结,比较粗糙,这里再次整理润色一下,前人栽树,方便后人乘凉!注:个...

    Reborn Lee
  • 【AI基础】python:opencv—

    学习使用OpenCV画几何图形,主要的函数为:cv2.line(),cv2.circle(),cv2.rectangle(),cv2.ellipse(),cv2...

    py3study

扫码关注云+社区

领取腾讯云代金券