网站教人做核能灯,公司网站备案名称,宝安网站公司,漯河知名网站建设价格Redis提供了SETBIT、GETBIT、BITCOUNT、BITOP四个命令用于处理二进制位数组#xff08;bit array#xff0c;又称“位数组”#xff09;。
SETBIT命令用于为位数组指定偏移量上的二进制位设置值#xff0c;位数组的偏移量从0开始#xff0c;而二进制位的值可以是0或1bit 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.计算byteint(offset/8)byte值记录了offset偏移量指定的二进制位在位数组的哪个字节。
2.计算bitoffset%81bit值记录了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.计算lenint(offset/8)1len记录了保存offset偏移量指定的二进制位至少需要多少字节。
2.检查bitarray键保存的位数组即SDS的长度是否小于len如果是将SDS的长度扩展为len字节并将所有新扩展空间的二进制位的值设为0。
3.计算byteint(offset/8)byte值记录了offset偏移量指定的二进制位保存在位数组的哪个字节。
4.计算bitoffset%81bit值记录了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%81得出值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%81得出值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 二进制位统计算法3variable-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*(11 0000)结果取后8位后8位的最高4位值为abcdefgh。 最后通过右移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 二进制位统计算法4Redis的实现
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语言内置的位操作来实现。
