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

相关文章

来自专栏我是攻城师

在Scala里面如何使用元组

3674
来自专栏老九学堂

这是谁做的作业!C语言编码太不规范了...

1) 程序应采用缩进风格编写,每层缩进使用一个制表位(TAB),类定义、方法都应顶格书写;

1682
来自专栏linjinhe的专栏

Linux常用命令:sort

1636
来自专栏康怀帅的专栏

PHP 编码规范

PHP 编码规范。 关键字必须小写 true, false, null。 类 类的 属性 和 方法 必须添加访问修饰符(private、protected 以及...

3063
来自专栏Python爬虫与数据挖掘

Python正则表达式初识(八)

继续分享Python正则表达式的基础知识,今天给大家分享的特殊字符是“\w”和“\W”,具体的教程如下。

1255
来自专栏py+selenium

python爬虫笔记之re.match匹配,与search、findall区别

网上的定义【 从要匹配的字符串的头部开始,当匹配到string的尾部还没有匹配结束时,返回None;  当匹配过程中出现了无法匹配的字母,返回None。】 

2.1K3
来自专栏Spark学习技巧

Java动态代理原理及解析

代理:设计模式 代理模式是一种常用的设计模式,其目的就是为其他对象提供一个代理以控制对某个真实对象的访问。代理类负责为委托类预处理消息,过滤消息并转发消息,以及...

4505
来自专栏北京马哥教育

Python 面试问答 Top 25

Python 是一种解释型,交互式,面向对象的高级编程语言。和别的一些使用标点符号的语言不同,Python使用了大量的英语单词作为关键字,因而具有很好的可读性...

3556
来自专栏Python专栏

Python 面试问答 Top 25

Python 是一种解释型,交互式,面向对象的高级编程语言。和别的一些使用标点符号的语言不同,Python使用了大量的英语单词作为关键字,因而具有很好的可读性。...

1273
来自专栏小二的折腾日记

面试总结-C++

堆、栈、自由存储区、全局/静态存储区、常量存储区 自由存储区存储malloc申请的内存 (1)从静态存储区域分配 。内存在程序编译的时候就已经分配好,这块内存在...

1881

扫码关注云+社区

领取腾讯云代金券