Redis——7. 排序&位运算

排序

命令实现原理

位运算

基操实现原理

1. 命令

常用：alpha， asc/desc，limit start count.

1. SORT key //对set，list 数值排序 2. SORT key ALPHA //对set，lsit 字符串排序 3. SORT key DESC //默认升序ASC（可不写），DESC降序 4. SORT key LIMIT 0 4 //从第0条开始，一共返回4条 5. SORT key BY ... //后面讲 6. SORT ... GET ... //根据返回的排序再进行其他查找 7. SORT ... STORE ... //排序的同时，把排序结果再存到其他键值对中

摆放顺序：除了GET关键字，其他摆放顺序和大小写没影响。eg. sort list alpha desc = SORT list desc alpha

执行顺序：(1)先排序（alpha，desc/asc，by等）；（2）LIMIT；（3）GET；（4）STORE；（5）返回结果给客户端

其他：BY命令详解：ref:https://segmentfault.com/a/1190000002806846

假设现在有一张这样的表

lpush grid 1 2 3 4 set price_1 20 set price_2 40 set price_3 30 set price_4 10 set weight_1 3 set weight_2 2 set weight_3 4 set weight_4 1

默认情况下对gid排序，只会按gid的值来排序

127.0.0.1:6379> sort gid 1) "1" 2) "2" 3) "3" 4) "4"

但是通过BY描述符，可以指定gid按照别的key来排序。例如我想要按照商品的价格来排序：

127.0.0.1:6379> sort gid by price_* 1) "4" 2) "1" 3) "3" 4) "2"

可以看到，gid为4的商品价格最低，为10，gid为2的商品价格最高，为40。

在这里，price_*中的*是一个占位符，先会把gid的值取出，代入到*中，再去查找price_*的值。例如在本例中，price_*中的*会分别被1,2,3,4代替，然后去取price_1,price_2,price_3,price_4的值来进行排序。

2.实现原理

所有排序的实现原理相同：

（1）创建与待排序key长度大小相同数组：redisSortObject[]数组

（2）redisSortObject.obj指向待排序的元素地址，u.score存储排序的值。u.*cmpobj用于存储字符串（如果是ALPHA排序）

（3）根据u.score进行快速排序。

3.位运算

(1) getbit key offset

set gary "a" // "a" = 97 = 01100001 //getbit操作 127.0.0.1:6379> getbit gary 0 (integer) 0 127.0.0.1:6379> getbit gary 1 (integer) 1 127.0.0.1:6379> getbit gary 2 (integer) 1 127.0.0.1:6379> getbit gary 3 (integer) 0 127.0.0.1:6379> getbit gary 4 (integer) 0 127.0.0.1:6379> getbit gary 5 (integer) 0 127.0.0.1:6379> getbit gary 6 (integer) 0 127.0.0.1:6379> getbit gary 7 (integer) 1

(2) setbit key offset value

set gary "a" // "a" = 97 = 01100001 //将0110001变成0110010，即97变98。 //"a"变成了"b" 127.0.0.1:6379> setbit gary 7 0 (integer) 1 127.0.0.1:6379> setbit gary 6 1 (integer) 0 127.0.0.1:6379> get gary "b"

(3) bitcount key 统计1的个数

127.0.0.1:6379> set gary "a" // "a" = 01100001 OK 127.0.0.1:6379> bitcount gary //一共3个1 (integer) 3 127.0.0.1:6379> set tom "ab" // "ab" = 01100001 01100010 OK 127.0.0.1:6379> bitcount tom //一共6个1 (integer) 6

(4) bitop 参照文档，不做介绍

4.实现原理

（1）setbit和getbit

内部SDS是用二进制存储的，毕竟是用C语言写的

比如：get key 19

直接可以算出，19/8 = 2 ——>  对应buf[2]； 19%8 = 3 对应 index =3，即buf[2]的第四个元素。

注：

1.假如 set key "a"；执行指令setbit key 123，会引起扩展操作。

即原来“a”的SDS大小只有2+1=3个字节（一个字节存储a，一个字节预分配，一个字节结束符“/0”），执行后会扩展SDS长度。

2.SDS保存时逆序保存，如"a" = 01100001 , 保存时：10000110，为了方便setbit操作

（2）bitcount原理

redis实现方法：查表 + variable-precision SWAR算法

count = 需要计算的位数 answer = 0; //记录结果 while(count >= 128){ 用SWAR算法累加answer,每次处理128位 } while(count != 0){ 每次8位处理累加answer，查表 } return answer；

查表：表中记录了00000000到11111111所有二进制位的汉明重量

variable-precision SWAR算法：

目前已知效率最好的通用算法，主要通过一系列位移和位运算。

不使用额外内存，复杂度O（n）常数时间。