Redis设计与实现 学习笔记 第二十二章 二进制位数组

embedded/2024/11/29 14:58:55/

Redis提供了SETBIT、GETBIT、BITCOUNT、BITOP四个命令用于处理二进制位数组（bit array，又称“位数组”）。

SETBIT命令用于为位数组指定偏移量上的二进制位设置值，位数组的偏移量从0开始，而二进制位的值可以是0或1：
在这里插入图片描述
GETBIT命令用于获取位数组指定偏移量上的二进制位的值：
在这里插入图片描述
BITCOUNT命令用于统计位数组里，值为1的二进制位的数量：
在这里插入图片描述
在这里插入图片描述
BITOP命令可对多个位数组进行按位与、按位或、按位异或运算：
在这里插入图片描述
BITOP命令也可对给定位数组进行取反：
在这里插入图片描述
22.1 位数组的表示

Redis使用字符串对象来表示位数组，因为字符串对象是用的SDS数据结构是二进制安全的，所以程序可以直接使用SDS结构来保存位数组，并使用SDS结构的操作函数来处理位数组。

图22-1展示了用SDS表示的，一字节长的位数组：
在这里插入图片描述
上图中：
1.redisObject.type的值为REDIS_STRING，表示这是一个字符串对象。

2.sdshdr.len的值为1，表示这个SDS保存了一个一字节长的字符串，用来表示位数组。

3.buf数组中的buf[0]字节保存了一字节长的位数组。

4.buf数组中的buf[1]字节保存了SDS程序自动追加到值末尾的空字符’\0’。

为了清晰地展示各个位的值，本章会对SDS中buf数组的展示方式进行修改，让各个位都可以清楚地展现出来，例如：
在这里插入图片描述
现在，buf数组的每个字节都用一行来表示，每行的第一个格子buf[i]表示这是buf数组的第i个字节，而buf[i]后的八个格子分别代表这一字节中的八个位。

图22-2中， buf[0]字节的各个位的值分别是10110010，是按逆序（小端字节序）保存的，左边是低位，右面是高位。使用逆序来保存位数组可以简化SETBIT命令的实现，稍后会介绍到。

图22-3展示了另一个位数组例子：
在这里插入图片描述
1.sdshdr.len属性的值为3，表示这个SDS保存了一个三字节长的位数组。

2.位数组由buf数组中的buf[0]、buf[1]、buf[2]三个字节保存，同样也是逆序保存的，上图位数组大端字节序表示是：11110000 11000011 10100101。

22.2 GETBIT命令的实现

GETBIT命令用于返回位数组bitarray在offset偏移量上的二进制位的值：
在这里插入图片描述
GETBIT命令的执行过程如下：
1.计算byte=int(offset/8)，byte值记录了offset偏移量指定的二进制位在位数组的哪个字节。

2.计算bit=offset%8+1，bit值记录了offset偏移量指定的二进制位是byte字节的第几个二进制位。

3.根据byte和bit值，在位数组bitarray中定位offset偏移量指定的二进制位，并返回这个位的值。

对于图22-2所示的位数组来说，命令：
在这里插入图片描述
将执行以下操作：
1.int(3/8)的值为0。

2.(3%8)+1的值为4。

3.定位到buf[0]字节上，然后取出该字节上的第4个二进制位的值（小端序，从左往右数）。

4.向客户端返回二进制位的值1。

命令执行过程如图22-4所示：
在这里插入图片描述
GETBIT命令的所有操作都可以在常数时间内完成，所以该命令的时间复杂度为O(1)。

22.3 SETBIT命令的实现

SETBIT用于将位数组bitarray在offset偏移量上二进制位的值设为value，并向客户端返回二进制位被设置前的旧值：
在这里插入图片描述
以下是SETBIT命令的执行过程：
1.计算len=int(offset/8)+1，len记录了保存offset偏移量指定的二进制位至少需要多少字节。

2.检查bitarray键保存的位数组（即SDS）的长度是否小于len，如果是，将SDS的长度扩展为len字节，并将所有新扩展空间的二进制位的值设为0。

3.计算byte=int(offset/8)，byte值记录了offset偏移量指定的二进制位保存在位数组的哪个字节。

4.计算bit=offset%8+1，bit值记录了offset偏移量指定的二进制位是byte字节的第几个二进制位。

5.根据byte和bit值，在bitarray键保存的位数组中定位offset偏移量指定的二进制位，首先将指定二进制位的当前值保存在oldvalue变量，然后将这个二进制位的值设为新值。

6.向客户端返回oldvalue变量的值。

SETBIT命令的所有操作都可以在常数时间内完成，所以该命令的时间复杂度为O(1)。

22.3.1 SETBIT命令的执行示例

我们对图22-2所示的位数组执行命令：
在这里插入图片描述
那么服务器将执行以下操作：
1.计算int(1/8)+1，得出值1，表示保存偏移量为1的二进制位至少需要1字节长的位数组。

2.检查位数组长度，发现SDS的长度不小于1字节，无须执行扩展操作。

3.计算int(1/8)，得出值0，说明偏移量1的二进制位位于buf[0]字节。

4.计算1%8+1，得出值2，说明偏移量为1的二进制位是buf[0]字节的第2个二进制位。

5.定位到buf[0]字节的第2个二进制位上，将二进制位现在的值0保存到oldvalue变量，然后将二进制位的值设为1。

6.向客户端返回oldvalue变量的值0。

图22-6展示了SETBIT命令的执行过程：
在这里插入图片描述
图22-7展示了SETBIT命令执行后，位数组的样子：
在这里插入图片描述
22.3.2 带扩展操作的SETBIT命令示例

现在我们看一个需要对位数组进行扩展的SETBIT命令的例子。

假设我们对图22-2所示的位数组执行命令：
在这里插入图片描述
那么服务器将执行以下操作：
1.计算int(12/8)+1，得出值2，这表示保存偏移量12的二进制位至少需要2字节长的位数组。

2.对位数组的长度进行检查，得知位数组现在的长度为1字节，这比执行命令所需的2字节要小，所以程序会要求将位数组的长度扩展为2字节。尽管程序只要求2字节长的位数组，但SDS的空间预分配策略会为SDS额外多分配2字节的未使用空间，再加上为保存空字符而额外分配的1字节，扩展后的buf数组的实际长度为5字节，如图22-8所示：
在这里插入图片描述
3.计算int(12/8)，得出值1，说明偏移量为12的二进制位位于buf[1]字节中。

4.计算12%8+1，得出值5，说明偏移量为12的二进制位是buf[1]字节的第5个二进制位。

5.定位到buf[1]字节的第5个二进制位，将二进制位现在的值0保存到oldvalue变量，然后将二进制位的值设为1。

6.向客户端返回oldvalue变量的值0。

图22-9展示了SETBIT命令定位并设置二进制位的过程：
在这里插入图片描述
图22-10展示了SETBIT命令执行后，位数组的样子：
在这里插入图片描述
因为buf数组使用逆序来保存位数组，所以当程序对buf数组进行扩展后，不必改动位数组原有的二进制位。

相反地，如果buf数组使用和书写位数组时一样的顺序（大端序）来保存位数组，那么在每次扩展buf数组后，程序都需要将位数组已有的位进行移动，然后才能执行写入操作，这次SETBIT命令目前的实现方式要复杂，并且移位带来的CPU时间消耗也会影响命令的执行速度。

图22-11至图22-14模拟了程序在buf数组按书写顺序保存位数组的情况下，对位数组0100 1101执行命令BITSET <bitarray> 12 1，将值改为0001 0000 0100 1101的整个过程：
在这里插入图片描述
22.4 BITCOUNT命令的实现

BITCOUNT命令用于统计给定位数组中，值为1的二进制位的数量。

例如，对于图22-15所示的位数组来说，BITCOUNT命令将返回4：
在这里插入图片描述
接下来对BITCOUNT命令可能使用的几种算法进行介绍，并最终给出BITCOUNT命令的具体实现。

22.4.1 二进制位统计算法（1）：遍历算法

实现BITCOUNT命令最简单直接的方法，就是遍历数组中的每个二进制位，并在遇到值为1的二进制位时，将计数器的值增1。

遍历算法虽然实现简单，但效率非常低，因为这个算法在每次循环中只能检查一个二进制位的值是否为1，所以检查操作的执行次数与数组包含的二进制位的数量成正比。

22.4.2 二进制位统计算法（2）：查表算法

优化检查操作的一个办法是使用查表法：
1.对于一个有限集合来说，集合元素的排列方式是有限的。

2.对于一个有限长度的位数组来说，它能表示的二进制位排列也是有限的。

根据这个原理，我们可以创建一个表，表的键是某种排列的位数组，而表的值是相应位数组中，值为1的二进制位数量。

创建了这种表后，我们就可以根据输入的位数组进行查表，从而在无须对位数组的每个位进行检查的情况下，直接知道这个位数组包含了多少个值为1的二进制位。

例如，对于8位长的位数组来说，我们可以创建表格22-1：
在这里插入图片描述
通过上表，我们可以一次从位数组中读入8个位，然后根据这8个位的值进行查表，直接知道这个值包含了多少个值为1的位，和之前介绍的算法相比，查表法的效率提升了8倍。

如果我们创建一个更大的表，那么一次查表能处理的位数就会更多，从而减少查表操作的次数。

看起来，只要我们创建一个足够大的表，那么统计工作就能轻易完成，但实际没有那么简单，因为查表法的实际效果会收到内存和缓存的限制：
1.查表法是典型的空间换时间策略，节约的时间越多，花费的内存越大。创建键长为8位的表仅需数百个字节，创建键长为16位的表也仅需数百KB，但创建键长为32位的表却需要十多GB。在实际中，服务器只可能接受数百字节或数百KB的内存消耗。

2.查表法的效果还受到CPU缓存的限制，对于固定大小的CPU缓存来说，创建的表越大，CPU缓存能保存的内容相比整个表格的比例就越少，查表时出现缓存不命中（cache miss）的情况就越多，缓存的换入和换出操作就会越频繁，最终影响查表法的实际效率。

由于以上两个原因，我们可以得出结论，查表法是一种比遍历算法更好的统计办法，但受限于查表法带来的内存压力，以及缓存不命中可能带来的影响，我们只能考虑创建键长为8或16位的表，而这两种表带来的效率提升，对于处理非常长的位数组来说仍然远远不够。

22.4.3 二进制位统计算法（3）：variable-precision SWAR算法

BITCOUNT命令要解决的问题——统计一个位数组中非0二进制位的数量，在数学上被称为“计算汉明重量（Hamming Weight）”。

因为汉明重量常被用于信息论、编码理论、密码学，所以研究人员针对计算汉明重量开发了多种不同算法，一些处理器甚至直接带有计算汉明重量的指令，而对于不具备这种特殊指令的普通处理器来说，目前已知效率最好的通用算法为variable-precision SWAR算法，该算法通过一系列位移和位运算操作，可以在常数时间内计算多个字节的汉明重量，并且不需要使用额外内存。

以下是一个处理32位长度位数组的variable-precision SWAR算法的实现：

uint32_t swar(uint32_t i) {// 步骤1i = (i & 0x55555555) + ((i >> 1) & 0x55555555);// 步骤2i = (i & 0x33333333) + ((i >> 2) & 0x33333333);// 步骤3i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);// 步骤4i = (i*(0x01010101) >> 24);return i;
}

步骤1：
i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
这一步中，掩码0x55555555（二进制形式为 01010101010101010101010101010101）用于选取i中所有奇数位置的位。
(i >> 1) & 0x55555555则是选取所有偶数位置的位。
然后将这两个结果相加，这样每两位中的1的个数就被计算出来并存放在原来的两位中。

步骤2：
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
掩码0x33333333（二进制形式为 00110011001100110011001100110011）用于选取每四位中的前两位。
(i >> 2) & 0x33333333用于选取每四位中的后两位。
通过相加，现在每四位存储的是原始四位中1的总数。

步骤3：
i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);
掩码0x0F0F0F0F（二进制形式为 00001111000011110000111100001111）用于选取每八位中的前四位。
(i >> 4) & 0x0F0F0F0F用于选取每八位中的后四位。
通过相加，现在每八位存储的是原始八位中1的总数。

步骤4：
i = (i*(0x01010101) >> 24);
乘以0x01010101（二进制形式为 00000001000000010000000100000001）将i的每个字节的值累加到最高字节上。举个例子，abcd efgh乘0001 0001，相当于abcd efgh*(1+1 0000)，结果取后8位，后8位的最高4位值为abcd+efgh。
最后通过右移24位，就可以得到整个32位数中1的总数量。

例如，对于调用swar(0x3A70F21B)，程序在第一步将计算出值0x2560A116，这个值的每两个二进制位记录了0x3A70F21B每两个二进制位的汉明重量，如表22-2所示：
在这里插入图片描述
之后，程序在第二步将计算出值0x22304113，这个值的每四个二进制位记录了0x3A70F21B每四个二进制位的汉明重量，如表22-3所示：
在这里插入图片描述
接下来，程序在第三步将计算出值0x4030504，这个值的每八个二进制位记录了0x3A70F21B每八个二进制位的汉明重量，如表22-4所示：
在这里插入图片描述
在第四步，程序首先计算0x4030504 * 0x01010101 = 0x100c0904，将汉明重量聚集到二进制位的最高八位，如表22-5所示：
在这里插入图片描述
之后程序计算0x100c0904 >> 24，将汉明重量移动到低八位，最终得出值0x10，即十进制值16，这个值就是0x3A70F21B的汉明重量，如表22-6所示：
在这里插入图片描述
swar函数每次执行可计算32个二进制位的汉明重量，它比之前介绍的遍历算法快32倍，比键长为8位的查表法快4倍，比键长为16位的查表法快2倍，并且因为swar函数是单纯的计算操作，所以它无须像查表法那样，使用额外的内存。

因为swar函数是一个常数复杂度的操作，所以我们可以根据自己的需要，在一次循环中多次执行swar，从而按倍数提升计算汉明重量的效率（这段有点问题，一次循环中调用多次swar函数也不会减少任何计算量，不会提升效率，这种方法只能减少循环次数，相当于循环展开，循环5次改写成把循环体复制5次，意义不大）：
1.例如，如果我们在一次循环中调用两次swar函数，那么计算汉明重量的效率就从之前的一次循环计算32位提升到了依次循环计算64位（错误的）。

2.又例如，如果我们在一次循环中调用四次swar函数，那么一次循环就可以计算128个二进制位的汉明重量，这次每次循环调用一次swar函数要快四倍（错误的）。

22.4.4 二进制位统计算法（4）：Redis的实现

BITCOUNT命令的实现用到了查表和variable-precision SWAR两种算法：
1.查表算法使用键长为8位的表，表中记录了从0000 0000到1111 1111在内的所有二进制位的汉明重量。

2.至于variable-precision SWAR算法方面，BITCOUNT命令在每次循环中载入128个二进制位，然后调用四次32位variable-precision SWAR算法来计算这128个二进制位的汉明重量。

在执行BITCOUNT命令时，程序会根据未处理的二进制位的数量来决定使用哪种算法：
1.如果未处理的二进制位数量大于等于128位，那么程序使用variable-precision SWAR算法来计算二进制位的汉明重量。

2.否则，程序使用查表法计算二进制位的汉明重量。

以下伪代码展示了BITCOUNT命令的实现原理：

# 一个表，记录了所有八位长位数组的汉明重量
# 程序将8位长的位数组转换成无符号整数，并在表中进行索引
# 例如，对于输入0000 0011，程序将二进制转换为无符号整数3
# 然后取出weight_in_byte[3]的值2
# 2就是0000 0011的汉明重量
weight_in_byte = [0,1,1,2,1,2,2,/*...*/,7,7,8]def BITCOUNT(bits):# 计算位数组包含了多少二进制位count = count_bit(bits)# 初始化汉明重量为零weight = 0# 如果未处理的二进制位大于等于128位# 那么使用variable-precision SWAR算法来处理while count >= 128:# 四个swar调用，每个调用计算32个二进制位的汉明重量# 注意：bits[i:j]中的索引j是不包含在取值范围内的weight += swar(bits[0:32])weight += swar(bits[32:64])weight += swar(bits[64:96])weight += swar(bits[96:128])# 移动指针，略过已处理的位，指向未处理的位bits = bits[128:]# 减少未处理位的长度count -= 128# 如果执行到这里，说明未处理的位数量不足128位# 那么使用查表法来计算汉明重量while count:# 将8个位转换成无符号整数，作为查表的索引（键）index = bits_to_unsigned_int(bits[0:8])weight += weight_in_byte[index]# 移动指针，略过已处理的位，指向未处理的位bits = bits[8:]# 减少未处理位的长度count -= 8# 计算完毕，返回输入二进制位的汉明重量return weight

这个BITCOUNT实现的算法复杂度为O(n)，其中n为输入二进制位的数量。更具体一点，第一个循环是消耗时间的大头，n位的二进制位需要循环n/32次，一次循环的时间复杂度为O(1)，因此总时间复杂度为O(n)。

22.5 BITOP命令的实现

因为C语言直接支持对字节执行逻辑与（&）、逻辑或（|）、逻辑异或（^）、逻辑非（~）操作，所以BITOP命令的AND、OR、XOR、NOT四个操作都是直接基于这些逻辑操作实现的：
1.执行BITOP AND命令时，程序用&操作计算出所有输入二进制位的逻辑与结果，然后保存在指定键上。

2.执行BITOP OR命令时，程序用|操作计算出所有输入二进制位的逻辑与结果，然后保存在指定键上。

3.执行BITOP XOR命令时，程序用^操作计算出所有输入二进制位的逻辑与结果，然后保存在指定键上。

4.执行BITOP NOT命令时，程序用~操作计算出所有输入二进制位的逻辑与结果，然后保存在指定键上。

例如，客户端执行命令：
在这里插入图片描述
其中，键x保存的位数组如图22-18所示，而键y保存的位数组如图22-19所示：
在这里插入图片描述
BITOP命令将执行以下操作：
1.创建一个空白位数组value，用于保存AND操作的结果。

2.对两个位数组的第一个字节执行buf[0] & buf[0]操作，并将结果保存到value[0]字节。

3.对两个位数组的第二个字节执行buf[1] & buf[1]操作，并将结果保存到value[1]字节。

4.对两个位数组的第三个字节执行buf[2] & buf[2]操作，并将结果保存到value[2]字节。

5.经过前面三次逻辑与操作，程序得到了图22-20所示的计算结果，并将它保存到result键上面：
在这里插入图片描述
22.6 重点回顾

1.Redis使用SDS来保存位数组。

2.SDS使用逆序来保存位数组，这种保存顺序简化了SETBIT命令的实现，使得SETBIT命令可以在不移动现有二进制位的情况下，对位数组进行空间扩展。

3.BITCOUNT命令使用了查表算法和variable-precision SWAR算法来优化命令的执行效率。

4.BITOP命令的所有操作都使用C语言内置的位操作来实现。


http://www.ppmy.cn/embedded/141499.html

相关文章

k8s中部署filebeat进行日志监听并发送到es中

k8s中部署filebeat进行日志监听并发送到es中

注意事项 1. 需要将namespace修改为自己项目中的命名空间 2. es换成对应的地址 3. filebeat-inputs中的两个配置&#xff08;根据需要用任意一个就可以&#xff09; 3.1 第一个配置是监听docker日志&#xff0c;由于系统日志太多所以这里只监听项目部署命名空间下的内容 -…
阅读更多...
【速通GO】基础结构和语法

【速通GO】基础结构和语法

独立站原文 基础结构以及执行方式 基础结构 // 包名 package main// 引入包 import "fmt"// main 函数是每一个可执行程序所必须包含的&#xff0c;一般来说都是在启动后第一个执行的函数&#xff08;如果有 init() 函数则会先执行该函数 // 注意 { 不能单独放在一…
阅读更多...
【C++笔记】数据结构进阶之二叉搜索树(BSTree)

【C++笔记】数据结构进阶之二叉搜索树(BSTree)

【C笔记】数据结构进阶之二叉搜索树(BSTree) &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;C笔记 文章目录 【C笔记】数据结构进阶之二叉搜索树(BSTree)前言一.二叉搜索树的概念二.二叉搜索树的性能分析三.二叉搜索树的实现3.1二叉树的中序…
阅读更多...
机器学习6-梯度下降法

机器学习6-梯度下降法

梯度下降法 目的 梯度下降法(Gradient Descent)是一个算法&#xff0c;但不是像多元线性回归那样是一个具体做回归任务的算法&#xff0c;而是一个非常通用的优化算法来帮助一些机器学习算法求解出最优解的&#xff0c;所谓的通用就是很多机器学习算法都是用它&#xff0c;甚…
阅读更多...
如何做好一份技术文档？

如何做好一份技术文档？

技术文档的创作与优化 一、技术文档的规划布局&#xff08;一&#xff09;明确文档目的与受众确定目的分析受众 &#xff08;二&#xff09;构建章节框架概述章节基础技术概念章节系统架构章节功能实现章节测试与验证章节结论与展望章节 二、技术文档的语言表达&#xff08;一&…
阅读更多...
初级数据结构——二叉搜索树题库（c++）

初级数据结构——二叉搜索树题库（c++）

目录 前言[1.——108. 将有序数组转换为二叉搜索树](https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/)[2.——LCR 052. 递增顺序搜索树](https://leetcode.cn/problems/NYBBNL/)[3.——897. 递增顺序搜索树](https://leetcode.cn/problems/increasi…
阅读更多...
c/c++ 用easyx图形库写一个射击游戏

c/c++ 用easyx图形库写一个射击游戏

#include <graphics.h> #include <conio.h> #include <stdlib.h> #include <time.h>// 定义游戏窗口的大小 #define WINDOW_WIDTH 800 #define WINDOW_HEIGHT 600// 定义玩家和目标的尺寸 #define PLAYER_SIZE 50 #define TARGET_SIZE 20// 玩家的结构…
阅读更多...
【qiankun】主应用css隔离、js隔离、日常通信机制

【qiankun】主应用css隔离、js隔离、日常通信机制

qiankun是一个微前端框架&#xff0c;它提供了多种机制来确保主应用与子应用之间的独立性&#xff0c;包括CSS隔离、JS隔离以及日常通信等。以下是对这些机制的详细解释&#xff1a; 一、CSS隔离 qiankun通过以下方式实现CSS隔离&#xff1a; 自动添加命名空间&#xff1a; …
阅读更多...
最新文章

Copyright @ 2022~2023