《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里面如何使用元组

3554
来自专栏用户2442861的专栏

STL源码剖析-hash_map / hash_multimap

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

1064
来自专栏北京马哥教育

Python工程师面试必备25条Python知识点

1.到底什么是Python?你可以在回答中与其他技术进行对比 下面是一些关键点: Python是一种解释型语言。这就是说,与C语言和C的衍生语言不同,Pytho...

3126
来自专栏Spark学习技巧

Java动态代理原理及解析

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

4135
来自专栏aCloudDeveloper

C++primer笔记之关联容器

在这一章中,有以下的几点收获: 1、pair类型的使用相当频繁,如果需要定义多个相同的pair类型对象,可考虑利用typedef简化其声明: typedef p...

2019
来自专栏linjinhe的专栏

Linux常用命令:sort

1396
来自专栏Vamei实验室

Python基础06 循环

循环用于重复执行一些程序块。从上一讲的选择结构,我们已经看到了如何用缩进来表示程序块的隶属关系。循环也会用到类似的写法。 for循环 for循环需要预先设定好循...

1896
来自专栏北京马哥教育

Python 面试问答 Top 25

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

1153
来自专栏北京马哥教育

Python 面试问答 Top 25

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

3506
来自专栏一个爱吃西瓜的程序员

Python基础学习-类

① 面向对象编程是最有效的软件编写方法之一。 ② 编写类时,你定义一大类对象都有的通用行为。 ③ 基于类创建对象时,每个对象都自动具备这种通用行为。 ④ 根据类...

4357

扫码关注云+社区