为非计算机图形专业人士写的位图算法图

两个月前——

为了满足用户标签的统计需求，小灰使用MySQL设计了如下表结构。人物的每个维度都对应Mysql One表中的一列：

如果我们想统计所有90年代出生的程序员该怎么办？

使用 SQL 语句进行交集：

从表中选择用户数（分隔名），年龄 = '90 后'和职业 = '程序员'；

如果你想要 Apple 使用，则所有用户应该怎样做我们对总用户数还是2000年以后出生的手机怎么办？

使用SQL语句查找并集：

从表中选择用户数（不同名称）Phone = 'Apple'或age = '00'；

两个月后—

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

1.给定长度为 10 的位图，10 的每一位对应于 0 到 9 之间的整数。目前，位图中的所有位都是 0。

2。将整数 4 存储在位图中。对应的存储位置为下标4位置。将此位设置为 1。

3。将整数 2 存储在位图中。对应的存储位置为下标2位置。将此位设置为 1。

4。将整数 1 存储在位图中。对应的存储位置为下标1的位置。将此位设置为 1。

" data-src="https://user-gold-cdn.xitu.io/2019/1/29/16897cf44b282f35?imageView2 /0/w/1280/h/960/format /webp/ignore-error /1" height="20" data-width="705" data-height="91" />

5.将整数3存储在位图中，对应的存储位置为下标3.将该位设置为1。

请问位图中当前存储了哪些元素？显然是4,3,2,1，一目了然。

Bitmap不是既方便查询，又可以去除双精度整数。

1.创建用户名和用户ID之间的映射：

2.让每个标签存储包含该标签的所有用户ID，每个标签都是一个独立的位图。

3。这样，用户重复和查询统计就一目了然了：

1。如何找到使用苹果手机的程序员用户？

2。如何找到所有男性或2000后用户？

一周后...

我们以前期的用户数据为例。用户基本信息如下。根据年龄标签，可以分为两种位图：

采用更有特色的表达方式，90后用户的位图如下：

目前可直接获取 非 90后用户90年代？不直接进行操作吗？

显然，实际上只有1个非90后用户，而不是图像中的8个结果，所以不能直接进行NOT。

和现在一样。我们给出 20 世纪 90 年代出生的用户的位图，然后给出所有用户的位图。最终需要的是所有用户中都存在，但90后用户中不存在的部分。如何找到

？我们可以使用异或运算 OR ，即相同位为0，不同位为1。

25769803776L = 110000000000000000000000000000000 8589947086L = 100 0000000000 0000000011000011001110B

1。解析Word0，发现当前RLW覆盖的空字数为0，后面是3个连续的常规字。

2。计算当前RLW后面连续正则字的最大ID 64 X (0 + 3) -1 = 191。

3。由于 191 4。分析Word4，发现当前RLW中的空字数量为6247，后面跟着1个连续的规则字。

5。计算当前RLW后面连续正则字的最大ID（Word4）191+（6247+1）X64=400063。

6。由于400003 最终输入结果如下：

官方说明如下：

* 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。文中介绍的位图优化方法有些简化，源码逻辑要复杂很多。例如，输入数据400003的位置与实际步骤不同。

2。如果学生有兴趣，可以自己阅读源代码，甚至尝试实现自己的位图算法。虽然需要花费很多时间，但这确实是一个很好的学习方法。

EWAHCompressedBitmap对应的maven依赖如下：

复制代码

<dependency>
  <groupId>com.googlecode.javaewah</groupId>
  <artifactId>JavaEWAH</artifactId>
  <version>1.1.0</version>
</dependency>复制代码

作者：程序员小灰
链接：https://juejin.im/post/5c4fd2af51882525da267385
来源：掘金。版权归作者所有 商业转载请联系作者授权。非商业转载请注明出处。