《Redis设计与实现》读书笔记(三十五) ——Redis 二进制位数组及SWAR汉明重量算法

《Redis设计与实现》读书笔记(三十五) ——Redis 二进制位数组及SWAR汉明重量算法

(原创内容,转载请注明来源,谢谢)

一、基本概念

redis提供了setbit、getbit、bitcount、bitop四个命令用于处理二进制数组,称为bit array,又叫位数组。

setbit命令用于位数组指定偏移量上的二进制设置值,偏移量从0开始计算,值可以是0或者是1。

getbit获取指定位置上的值。

bitcount统计位数组里面,值为1的二进制位的数量。

bitop可以有and、or、xor,即与、或、异或的位运算。

二、位数组的表示

redis使用字符串对象sds来表示位数组,因为其数据结构是二进制安全的。因此,其末尾也会用\0来表示结尾。

一字节长度的位数组,在结构中表示如下:

其中,buf[0]存放1字节的二进制数组,即长度是8位的二进制数组。buf[1]空字符即是\0。

为了便于查看,采用如下方式:

需要注意的是,实际上保持的数据,和日常习惯是相反的,如上图中,实际上保存的是二进制数01001101。采用逆序保存是为了便于setbit的实现。

三、getbit实现

getbit返回位于数组bitarray的offset偏移量的值,命令即getbit <bitarray> <offset>。命令执行流程如下:

1)计算byte=offset/8,向下取整。该值记录了保存在offset偏移量的位数保存在哪个字节中,即上述的获取buf数组的下标。

2)计算bit=(offset mod 8)+1,获取二进制的位数是哪一位,即上述buf[byte]数组具体的位置。

3)根据上述的结果,获取buf[byte][bit]的值。

4)将结果返回给客户端。

例如对于某个二进制数组,getbit<bitarray> 10:

getbit所有操作都可以在常数时间完成,时间复杂度是O(1)。

四、setbit实现

1、普通setbit

setbit设置位于数组bitarray的offset偏移量的值为value,命令即setbit <bitarray> <offset> <value>。命令执行流程如下:

1)执行getbit的1、2两步,确定需要修改的二进制的具体位置。

2)获取对应位置的值进行暂存到oldvalue,并且将新的值设置进去。

3)将oldvalue返回给客户端。

setbit时间复杂度也是O(1)。

2、带扩展操作的setbit

当设置的offset计算出的byte的结果超出现有的数组长度,即buf[byte]的下标超出现有的范围,则需要扩展。

例如,现有是1个字节,执行setbit<bitarray> 12 1,则算出byte=12/8取整,值是1,但是当前不存在buf[1],则redis会新开辟空间。另外,redis基于redis开辟空间的策略(以前文章有提到),会扩展到5字节,剩余的空间是预留空间。

接着,按照前面的方式setbit,并返回旧的bit值。

由于redis采用逆序保存二进制数组,因此在对buf进行扩展后,可以直接将值设置到对应的bit,而不必改动现有的二进制位。如果是采用顺序方式保存,则每次扩展后,需要将位数组中已有的位进行移动,然后才能执行写入操作,则过程复杂。

五、bitcount实现

bitcount返回给定二进制数组中,值为1的二进制位的数量。例如对于下图,返回的结果是12。

实现统计几个1,redis中用到一些有趣的算法。

1、遍历算法

遍历算法是最简单但也最低效的方法,即遍历每个二进制位,当是1的时候,计数器加1。

这种算法中,遍历100MB长度的二进制数组,需要执行操作近8亿次。

2、查表法

对于一个集合来说,集合元素的排列方式是有限的;对于一个有限长度的数组来说,它能表示的二进制位的排列也是有限的。

根据上述原理,可以创建一个表,表的键为某种排列的位数组,值是1的二进制位的数量。例如下图是以8位长度作为键的表。

创建这个表后,则无需对位数组进行检查,只要查表就可以知道结果。利用上述的8位长度的表,每次可以查出8位二进制的1的数量,进而100MB长度的二进制数组,查找的次数减少到1亿次。

同理,如果创建一个更大的表,如16位的表,则1次可以查出16位二进制数组的1的数量,进而100MB长度只需要5000万次查找。

理论上来说,是可以创建一个足够大的表,则查询的次数可以降到很低,但是表会收到实际情况的限制:

1)查表法是典型的以空间换时间的方式,节约计算时间带来的是花费更多的内存,创建键长度为16位的二进制表,只需要几百KB;而32位,则需要超过10GB。通常服务器接受几百KB消耗还可以,但是十几个GB难以接受。

2)除了内存消耗,查表法的效果还会收到CPU缓存的限制。对于固定大小的缓存来说,创建的表格越大,CPU能保存的缓存的内容相比整个表格的比例就越少,查表的缓存不命中的概率越高,导致缓存的换入换出频繁切换,影响实际效率。

因此,要使用查表法,通常会建立8位或者16位的表。

3、variable-precisionSWAR算法

bitcount需要实现的计算二进制位的数量,在数学上称为计算汉明重量。目前最好的算法是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);
}

具体说明如下:

1)步骤1

计算出值i的二进制表示,可以按每两个二进制位为一组进行分组,各组的十进制位就表示该组的汉明重量。

解释:

0x55555555 = 0b01010101010101010101010101010101,可以看到奇数位都是1,偶数位都是0。

因此,假设j = i& 0x55555555,即j的偶数位都是0,奇数位是原始i的奇数位的1的数量。

(i >> 1) & 0x55555555,是将i右移一位以后,此时得到的临时变量还是奇数位的1和i右移后的奇数位的1的数量一样。因此,也就是i右移之前的i的偶数位的1的数量。

因此,这两个数相加以后,得到的是两位一组的情况下,每两位的二进制位中1的数量。

2)步骤2

计算出值i的二进制表示,可以按每四个二进制位为一组进行分组,各组的十进制位就表示该组的汉明重量。

因为0x33333333= 0b00110011001100110011001100110011,具体过程同第一步。

3)步骤3

计算出值i的二进制表示,可以按每八个二进制位为一组进行分组,各组的十进制位就表示该组的汉明重量。

因为0x0F0F0F0F= 00001111000011110000111100001111,具体过程同第一步。

4)步骤4

i * (0x01010101) 计算出的是bitarray的汉明重量,并记录在二进制位的最高八位。通过>>24右移运算,将汉明重量移动到最低八位。得到的结果就是最终的结果。

这个要分两步来理解。

0x01010101 = 00000001000000010000000100000001 = (1 << 24) + (1<< 16) + (1 << 8) + 1,因此,

k * 0x01010101 = (k << 24) + (k << 16) + (k << 8)+ k

由于前三步已经将结果分好组,这一步即求出每组上面二进制的值即可。

至于右移24位,只是将结果移到最低位而已。

该算法每次执行,可以计算长度为32位的二进制数组。上面提到用查表法的时候,32位需要耗费内存超过10GB,无法接受。而采用此方式,不需要额外耗费内存,而速度又是查表法的2倍。

另外,再每次循环总的数组的时候,调用1次swar就相当于32位,但是如果调用4次,将等于128位的计算。当然,多次调用是有极限的,一旦循环中处理的位数组大小超过了缓存的大小,这种优化效果会降低。

4、redis的实现

redis的bitcount,同时实现了查表法和swar算法。查找法使用8位长度的表,swar方面使用每个循环调用4次,即128位。

在执行bitcount的时候,redis会根据二进制位的数量。如果大于128位,则用swar;否则用查表法。

基本流程是,先将二进制位数组转换成无符号整数;再判断其长度,对于大于128位的,循环中调用swar算法,每次循环调用四次算法,并且总长度减去128位;如果长度小于8位,则调用查找表算法,每次调用1次8位表,并且总长度减去8位。

bitcount的时间复杂度是O(n),n是二进制位数组的长度。使用swar时,共需要循环n/128向下取整次;使用查找表,共需要循环n mod 128次。

六、bitop实现

bitop接受选项and、or、xor、not,分别对应c语言中的&、|、^、~。

例如,键x、y分别保存的二进制位,如下图左右图所示。

执行bitop andresult x y,流程如下:

1)创建一个空白数组value,用于保存and操作的结果。

2)分别对两个数组的buf[0]~buf[2]进行&的计算,将结果分别保存在新的value中的buf[0]~buf[3]。

and、or、xor选项支持多个键,但是not只支持1个键的计算。

七、总结

1、redis使用sds数据结构来保存二进制位数组,每1个字节(8位)保存在buf的一个数组中,且采用逆序的方式保存。

2、bitcount结合查找表和swar算法实现,当数组长度超过128位用swar,否则用查找表。

——written by linhxx 2017.10.01

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-10-01

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

数据分析师(技术编程类)常见的10道面试题解答

1、海量日志数据,提取出某日访问百度次数最多的那个IP。   首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最...

2188
来自专栏MyBlog

Effective Java 读书笔记(7)避免finalizer

对于Finalizers他们的使用可能会造成错误的产生,糟糕的性能以及移植性的问题,当然Finalizers有着一些有用的优点,我们会在后续介绍这些,但是作为首...

732
来自专栏机器学习从入门到成神

牛客网刷题汇总(一)附解析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

682
来自专栏华章科技

10道Hadoop面试真题及解题思路

首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法, 比如模1000...

622
来自专栏Java后端生活

JavaWeb(八)MVC设计模式

1365
来自专栏工科狗和生物喵

【计算机本科补全计划】链式存储线性表的一些相关操作

正文之前 不管怎么说,好歹是吧王道的第二章看完了!线性表算法写的我都快吐了,不过成果也是有的,可以写一些稍微复杂的算法了!感动,希望尽早达到老师的要求,然后去实...

2666
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(二)No.50

上一次我们说完了用 HashSet 来进行计数了。我们可以发现,如果我们估计有N个数,那么我们至少需要N*32bit(按照int在32位操作系统下占用32个bi...

1858
来自专栏King_3的技术专栏

leetcode-39-组合总和(有趣的递归)

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

732
来自专栏企鹅号快讯

什么是B+Tree

推荐阅读 微服务: springboot系列教程学习 源码:Javaweb练手项目源码下载 调优:十五篇好文回顾 面试笔试:面试笔试整理系列 B+Tree的定义...

1786
来自专栏JAVA高级架构

Java数据结构与算法解析——2-3树

二叉查找树对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率,...

3277

扫描关注云+社区