Redis提供了SETBIT
,GETBIT
,BITCOUNT
,BITOP
四个命令用于处理二进制位数组.
其中, SETBIT
命令用于为位数组指定偏移量上的二进制设置值, 位数组的偏移量从0开始计数, 而二进制位的值则可以是0
或者1
。
GETBIT
命令则用于获取位数组指定偏移量上的二进制位的值.
BIGCOUNT
命令用于统计维数组里面, 值为1的二进制位的数量.
BITOP
命令既可以对多个位数组进行按位与(and)
,按位或(or)
,按位异或(xor)
,取反操作(not)
运算
位数组的表示
Redis使用字符串对象来表示位数组, 因为字符串对象使用的SDS数据结构是二进制安全的, 所以程序可以直接使用SDS结构来保存位数组, 并使用SDS结构的操作函数来处理位数组.
在使用redisObject保存位数组时, buf数组保存位数组的顺序和我们平时书写位数组的顺序是完全相反的. 例如: buf[0] 字节中, 各个位的值分别是: 1,0,1,1,0,0,1,0
, 这表示buf[0]
字节保存的位数组为0100 1101
. 使用逆序来
保存为数组可以简化SETBIT
命令的实现。
GETBIT 命令的实现
GETBIT
命令用于返回位数组bitarray
在offset
偏移量上的二进制位的值:
GETBIT <bitarray> <offset>
GETBIT
命令的执行过程如下:
-
计算
byte=[offset / 8]0
,byte值记录了offset偏移量指定的二进制位保存在位数组的哪个字节. -
计算
bit=(offset mod 8) + 1
bit值记录了offset偏移量指定的二进制位是byte字节的第几个二进制位 -
根据
byte
值和bit
值, 在位数组bitarray
中定位offset
偏移量指定的二进制位, 并返回这个位的值.
GETBIT执行步骤
GETBIT <bitarray> 3
将执行以下操作:
-
[3/8]
的值为0
-
(3 mod 8) + 1
的值为4 -
定位到
buf[0]
字节上面, 然后取出该字节上的第四个二进制位的值 -
向客户端返回二进制位上的
1
NOTE: 因为
GETBIT
命令执行的所有操作都是可以在常数时间内完成, 所以该命令的算法复杂度为O(1)
SETBIT 命令的实现
SETBIT
用于将数组bitarray
在offset
偏移量上的二进制位的值设置为value
, 并向客户端返回二进制位被设置之前的旧值:
SETBIT <bitarray> <offset> <value>
以下是SETBIT
命令的执行过程:
-
计算
len=[offset / 8] + 1
,len
值记录了保存offset
偏移量指定的二进制位至少需要多少字节. -
检查
bitarray
键保存的位数组(也即是SDS)的长度是否小于len
, 如果是的话, 将SDS
的长度扩展为len
字节, 并将所有新扩展空间的二进制位的值设置为0
(此处还是会遵循SDS的扩展原则
) -
计算
byte=[offset / 8]
,byte
值记录了offset偏移量指定的二进制位保存在维数组的哪个字节 -
计算
bit=(offset mod 8) + 1
,bit
值记录了offset
偏移量指定的二进制位是byte
字节的第几个二进制位. -
根据
byte
值和bit
值, 在bitarray键保存的维数组中定位offset
偏移量指定的二进制位, 首先将指定二进制位在值保存在oldvalue
变量, 然后将新值value
设置为这个二进制位的值 -
向客户端返回
oldvalue
变量的值.
因为SETBIT
命令执行的所有操作都可以在常数时间内完成, 所以该命令的时间复杂度为O(1)
为什么SETBIT采用逆序存储???
BIGCOUNT 命令的实现
BITCOUNT命令用于统计给定位数组中, 值为1
的二进制位的数量。
二进制位统计算法(1): 遍历算法
实现BITCOUNT
命令最简单直接的办法, 就是遍历数组中的每个元素中的每个二进制位, 并在遇到值为1
的二进制位时, 将计数器的值增加1
尽管遍历算法对单个二进制位的检查可以在很短的时间内完成, 但是重复执行上亿次这种检查肯定不是一个搞笑程序应有的表现, 为了让BITCOUNT
命令的实现尽可能地高效, 程序必须尽可能地增加每次检查所能处理的二进制位的数量,从而减少检查操作执行的次数.
二进制统计算法(2): 查表算法
优化检查操作的一个办法是使用查找表:
-
对于一个有限集合来说, 集合元素的排列方式是有限的
-
而对于一个有限长度的位数组来说, 它能表示的二进制位排列也是有限的
根据这个原理,我们可以创建一个表, 表的键为某种排列的位数组, 而表的值则是相应位数组中, 值为1
的二进制位的数量。
创建了这种表之后, 我们可以根据输入的位数组进行查表, 在无须对位数组的每个位进行检查的情况下, 直接知道这个位数组包含了多少个值为1的二进制位。
存在的问题
-
因为查表法是典型的空间换时间策略, 算法在计算方面节约的时间是通过花费额外的内存换取而来的, 节约的时间越多, 花费的内存越大
-
除了内存大小的问题之外, 查表法的效果还会受到CPU缓存的限制: 对于固定大小的CPU缓存来说, 创建的表格越大, CPU缓存所能保存的内容比整个表格的比例就越少, 查表时出现缓存不命中的情况就会越高, 混村的换入和换出操作就会越频繁, 最终影响查表法的实际效率。
为了搞笑地实现BITCOUNT
命令, 我们需要一种不会带来内存压力, 并且可以在一次检查中统计多个二进制位的算法。
二进制位统计算法(3): variable-precision SWAR算法
BITCOUNT
命令要结局的问题——统计一个位数组中非0二进制位的数量, 在数学上被称为计算汉明重量
.
因为汉明重量经常被用于信息论, 编码理论和密码学, 所以研究人员针对计算汉明重量开发了多种不同的算法, 一些处理器甚至直接带有计算汉明重量的指令, 而对于不具备这种特殊命令的普通处理器来说, 目前已知效率最好的通用算法为variable-precision SWAR
算法, 该算法通过一系列位移和位运算操作, 可以在常数时间内计算多个字节的汉明重量, 并且不需要使用任何额外的内存。
uint32_t swar(uint32_t i) { // 步骤1 i = (i & 0x55555555) + ((i >> 1) & 0x55555555); // 步骤2 i = (i & 0x33333333) + ((i >> 2) & 0x33333333); // 步骤3 i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F); // 步骤4 i = (i * (0x01010101) >> 24); return i; }
SWAR的执行步骤
-
步骤1: 计算出的值i的二进制标识可以按每两个二进制位位一组进行分组, 各组的十进制表示就是该组的汉明重量
-
步骤2: 计算出的值i的二进制标识可以按每四个二进制位为一组进行分组, 各组的十进制表示就是该组的汉明重量
-
步骤3: 计算出的值i的二进制标识可以按每8个二进制位为一组进行分组, 各组的十进制的表示就是该组的汉明重量
-
步骤4的
i * 0x01010101
语句计算出bitarray的汉明重量并记录在二进制位的最高八位, 而>>24
语句则通过右移运算, 将bitarray
的汉明重量移动到最低八位, 得出的结果就是bitarray
的汉明重量。
二进制位统计算法(4): Redis的实现
BITCOUNT
命令的实现用到了查表和variable-precision SWAR
两种算法:
-
查表算法使用键长位
8位
的表, 表中记录了从0000 0000
到1111 1111
在内的所有二进制位的汉明重量 -
至于
variable-precision SWAR
算法方面,BITCOUNT
命令在每次循环中载入128
个二进制位, 然后调用四次
32位variable-precision SWAR
算法来计算128个二进制位的汉明重量
在执行BITCOUNT
命令时, 程序会根据未处理的二进制位的数量来决定使用哪种算法:
-
如果为处理的二进制位的数量大于等于
128
位, 那么程序使用variable-precision SWAR
算法来计算二进制位的汉明重量 -
如果未处理的二进制位的数量小于
128
位, 那么程序使用查表算法来计算二进制位的汉明重量
NOTE: 这个BITCOUNT实现的算法复杂度为
O(n)
,其中n为输入二进制位的数量
BITOP命令的实现
因为C语言直接支持对字节执行逻辑与(&)
,逻辑或(|)
,逻辑异或(^)
,逻辑非(~)
操作, 所以BITOP命令的AND
,OR
,XOR
,NOT
四个操作都是直接给予这些逻辑操作实现的:
-
在执行
BITOP AND
命令时, 程序会用&
操作计算出所有输入二进制位的逻辑与结果, 然后保存在指定的键上面 -
在执行
BITOP OR
命令时, 程序用|
操作计算出所有输入二进制位的逻辑或结果, 然后保存在指定的键上面 -
在执行
BITOP XOR
命令时, 程序用^
操作计算出所有输入二进制位的逻辑异或结果, 然后保存在指定的键上面 -
在执行
BITOP NOT
命令时, 程序用~
操作计算出输入二进制位的逻辑非结果, 然后保存在指定的键上面。
BITOP AND result x y
以上命令的执行步骤
-
创建一个空白的位数组
value
, 用于保存AND
操作的结果 -
对两个位数组的第一个字节执行
buf[0] & buf[0]
操作, 并将结果保存到value[0]
字节 -
对两个数组的第二个字节执行
buf[1] & buf[1]
操作, 并将结果保存到value[1]
字节 -
对连个数组的第三个字节执行
buf[2] & buf[2]
操作, 并将结果保存到value[2]
字节 -
经过前面的三次逻辑与操作, 程序得到结果, 并将结果保存在
result
上面
NOTE:
BITOP OR
,BITOP XOR
,BITOP NOT
命令的执行过程和这里列出的BITOP AND
的执行过程类似
因为BITOP AND
,BITOP OR
,BITOP XOR
三个命令可以接受多个位数组作为输入, 程序需要遍历输入的每个位数组的每个字节来进行计算, 所以这些命令的复杂度位O(N^2)
; 与此相反, 因为BITOP NOT
命令只接受一个位数组输入, 所以它的复杂度位O(n)
文章评论