《Redis设计与实现》读书笔记(三十三) ——Redis排序命令sort的实现

《Redis设计与实现》读书笔记(三十三) ——Redis排序命令sort的实现

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

一、基本功能

redis的sort命令,可以对现有列表键、集合键或有序集合键的值进行排序。可以在sort命令后加上alpha参数,则表示按照字母表排序;加上asc、desc,分别是升序和降序。另外也可以通过by加上参数,对用户自定义的内容进行排序。

redis的排序,都是通过快速排序算法来实现的。快速排序算法见以前发过的文章。

二、sort <key>命令的实现

这个命令是对包含数字值的键进行排序。步骤如下:

1)创建一个和待排序元素(如列表、集合等,假设待排序元素为a)长度相同的数组,该数组的每一项都是一个redis.h/redisSortObject结构,该结构包含两个元素,obj与u。

2)遍历整个数组,将每个结构的obj指针,分别指向一个a中的一个元素,构成一对一的关系。

3)遍历整个数组,将每个obj指向的a的元素的值,都转成浮点数,存在数组元素u.score中。

4)根据u.score,对整个数组进行排序。

5)遍历数组,将数组中每个obj对应的列表元素作为返回值,返回给客户端。

排序前:

排序后:

三、alpha选项的实现

命令是sort<key> alpha,这是对字符串进行排序的方式。其和排序数字,区别在于没有利用到u.score,而是将obj指针指向元素之后,直接通过指针来找到相应的内容,并进行排序。

四、asc和desc选项的实现

默认情况,redis通过升序进行排序,结果按从小到大排列,字母从a开始。即:sort <key>和sort <key> asc是等价的,sort <key> desc是倒序。

升序和降序都由相同的快速排序算法执行。

五、by选项的实现

by是允许用户自定义权重,默认情况下是键对应的值就是本身的权重。

通过使用by选项,sort命令可以指定某些字符串的键,或某个哈希键所包含的某些域来作为元素的权重,对一个键进行排序。

例如:

mset fruits apple-price 8 banana-price 5.5 cherry-price 7
sort fruits by *-price

输出结果:

banana
cherry
apple

redis执行过程如下:

1)创建一个redisSortObject结构数组,数组长度等于fruits集合大小。

2)遍历数组,将各个数组项的obj指针分别指向fruits集合的各个元素。

3)遍历数组,根据各个数组项obj指针所指向的集合元素,以及by选项所给定的模式*-price,查找相应权重的键。

例如,对应apple元素,返回apple-price键。

4)将各个权重键对应的值,转成double类型的浮点数,保存到相应数组结构的u.score中。

例如apple-price对应的值是8,被转成8.0存到u.score中。

5)以u.score的值为权重,对数组进行排序。

6)遍历排序后的数组,将结果返回给客户端。

六、带有alpha选项的by选项

当每个键对应的结果是字符串,则需要带有alpha选项。

排序方法和不带alpha的by选项相似,区别在于u。对数字的排序,是保存在u.score中,而对字符串排序,则是利用到u.cmpobj指针,将其指向obj对应的字符串。再利用字符串进行排序,得到结果。

七、limit选项的实现

默认情况下,会将所有排序结果返回给客户端,通过limit可以只返回一部分内容给客户端。格式是limit <offset> <count>,例如:

sort lista limit 0 4

offset表示从第i个开始返回(从0开始是第一个),count表示一共返回几个给客户端。利用该选项,可以实现类似mysql中分页的功能。

详细步骤如下:

1)前几步骤同前面正常的排序,但是排序完成后不直接返回给客户端。

2)根据选项的offset和count,从排序后的第offset个元素开始的,逐个将结果返回给客户端,共返回count个元素。

八、get选项的实现

默认情况下,排序后返回的都是被排序键本身所包含的元素。通过get选项,可以让sort对键排序之后,根据被排序的元素,以及get选项所指定的模式,查找并返回某些键的值。

该选项,和前面的区别在于,返回的时候,会根据get选项指定的内容,将结果进行返回。

九、store选项的实现

默认情况下sort只返回结果,不保存排序结果,通过store可以保存结果,并且指定一个键,将结果保存在那个键。

例如sort listastore listb,会将对lista的排序结果保存在listb。

redis在将排序结果存入某个键的时候,会先查看该键是否存在。如果键已经存在,则会将该键先删除,再重新创建一个新的空白键,并将结果存入,再将结果返回给客户端。

十、多个选项执行的排序

1、执行顺序

sort的完整执行顺序如下:

1)排序,并查看是否有alpha、asc、desc、by这几个选项,有的话根据选项进行排序。

2)限制返回结果的长度,通过limit实现。

3)获取外部键,通过get命令,将外部的键整合到排序结果中。

4)保存排序结果,通过store实现。

5)向客户端返回结果集。

2、选项的摆放顺序

排序除了get命令,其他命令都是按照上述的顺序执行,因此选项放在任意的位置,都不会影响到排序的结果。即limit、store、asc、alpha、by等选项,可以随便混排,不会影响到排序的结果。

当加入了多个get命令,则多个get命令选项的pattern的顺序应该保持一致,才会保证结果顺序是一致的。

十一、总结

1、redis的排序,基本的是sort命令,会将数字集合按照升序进行排列;alpha选项后,会将字符串按照字母表顺序进行排列;asc和desc分别是升序和降序;by会通过特定的内容进行排序;get可以获取外部的键值;limit可以限制返回的结果数量;store是保存排序的结果。

2、redis排序前,会先创建一个和待排序元素大小相同的数组,如果排序的内容是数字,则会将其转成浮点数。

3、redis排序都是通过快速排序算法实现的。

4、除了get选项以外,其他选项的摆放位置不会影响到排序的结果。

——written by linhxx 2017.09.30

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

原文发表时间:2017-09-30

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏架构说

声明和定义的区别(深入理解)

问题 声明和定义区别 definition declared 微信排版支持makdown语法不友好 可以查看原文链接 先看一下 例子1 编译有没有问题? cl...

25310
来自专栏java闲聊

Shell入门

a. 单引号(括起来的字符都作为普通字符出现。特殊字符用单引号括起来以后,也会失去原有意义,而只作为普通字符解释)

1124
来自专栏Go入门系列

Golang 入门系列(二)Go语言基础语法及需要注意的坑

上一章节我们已经了解了 Go 环境的配置,不了解的,请查看前面的文章 https://www.cnblogs.com/zhangweizhong/p/94599...

30
来自专栏流媒体

C++输入输出流

461
来自专栏Crossin的编程教室

【Python 第17课】 类型转换

昨天又被微信后台给坑了,导致有些同学收了2遍消息。希望今天能顺利发成功。。。 #==== 类型转换 ====# python的几种最基本的数据类型,我们已经...

2516
来自专栏书山有路勤为径

生成括号

已知n组括号,开发一个程序,生成这n组括号所有的合法的组合可能例如:n = 3 结果为:["((())) "," (()())","()(()) "," ()...

471
来自专栏从零开始的linux

用python解释mapreduce

map import sys #输入为标准输出stdin for line in sys.stdin: #删除开头和结尾的空行 line = ...

3084
来自专栏python成长之路

类的父类object的一些属性、方法

1115
来自专栏Python小屋

Python组合列表中多个整数得到最小整数(一个算法的巧妙实现)

'''程序功能: 给定一个含有多个整数的列表,将这些整数任意组合和连接, 返回能得到的最小值。 代码思路: 将这些整数变为相同长度(按最...

3036
来自专栏L宝宝聊IT

Shell脚本应用(if语句的结构)

995

扫描关注云+社区