《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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

HDU5972Regular Number(ShiftAnd算法 bitset)

接下来\(n\)行,每行开头有一个整数\(num\)表示匹配串中该位置的字符可以在\(num\)个桅子花出现,接下来输入这\(num\)个位置

761
来自专栏栗霖积跬步之旅

HTML基础下

知识点一: HTML5的标准结构: <!DOCTYPE html> <html lang='en'> <head> <meat charset='utf...

1806
来自专栏前端儿

大小写互换

  现在给出了一个只包含大小写字母的字符串,不含空格和换行,要求把其中的大写换成小写,小写换成大写,然后输出互换后的字符串。

812
来自专栏软件开发

JavaSE学习总结(二)——Java语言基础

一、Java程序预览 Java的语法与C非常类似,这里先使用几个非常简单的程序以点带面来区分C语Java的区分再细讲每个知识点。该文仅针对有编程基础的朋友参考。...

1998
来自专栏数据结构与算法

LOJ#515. 「LibreOJ β Round #2」贪心只能过样例(bitset)

一共有 nnn个数,第 iii 个数 xix_ix​i​​ 可以取 [ai,bi][a_i , b_i][a​i​​,b​i​​] 中任意值。 设 S=∑xi2...

963
来自专栏和蔼的张星的图像处理专栏

两数之和 56,608暴力查找排序加双指针

看到了就一块做了,两个题的要求差不多,条件不同: 给一个整数数组,找到两个数使得他们的和等于一个给定的数 target。 你需要实现的函数twoSum需要返...

702
来自专栏null的专栏

数据结构和算法——旋转打印链表

1、问题描述 输入参数nnn为正整数,如输入n=5n=5n=5,则按行打印如下的数字: ? 2、问题的理解 这个问题是将数字1…n21…n21\dots n^2...

2903
来自专栏Python小屋

Python花式编程案例集锦(6)

问题描述:输出“水仙花数”。所谓水仙花数是指1个3位的十进制数,其各位数字的立方和等于该数本身。例如:153是水仙花数,因为153 = 1^3 + 5^3 + ...

3138
来自专栏极客生活

数据分析Excel技能之自动填充

将光标移动到选中的单元格的右下角的那个节点上光标会变成实心加号。然后可以上下左右拖动光标就会自动填充当前单元格中的内容。 根据当前单元格中的内容格式不同,ex...

873
来自专栏landv

C语言_基础代码_01

1513

扫码关注云+社区