描述

快速查找结合了二分查找和快速排序，在无序的数组中，每次都会去掉一般的元素进行选择。

时间复杂度

平均情况：O(n)

最坏情况：O(nlogn)

示例代码

golang

java

描述

通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。

时间复杂度

平均情况：O(nlogn)

最坏情况：O(n^2)

示例代码

golang

java

R.I.P @haoel

来到上海的第 1000 天，是我在这座城市最难过的一天。

如引言所见，”左耳朵耗子“陈皓老师突然去世，MegaEase 变成灰色，池大大也发微博确认，看来是真事，惊讶程度直逼科比。技术大佬不缺钱，当然要把革命的本钱照顾好，没想到是心梗，没认真对待身体实锤。

正经说话的人有，阴阳怪气的也大有人在。我一直不理解，为什么互联网总充斥着各色各样的人和各种各样的奇怪言论。逝者安息和死者为大是基本常识吧！还有人用这件事开玩笑，也不知道居心何在。Peace & Love

16 年我在库尔勒，看了吴军老师的《AA 之 B》系列丛书，特别是《浪潮之巅》，下定决心今后投身互联网，遂回到石河子转入计科系。如果吴军老师是我的灯塔，那陈皓老师就是我的路标。《左耳听风之程序员练级攻略》是对我职业生涯影响最大的系列文章，我知道合格程序员要有自己的技术修养、技术积累到底到何种程度、软件设计究竟如何取舍等等。感谢他吧，我还是会加油的，同时要照顾好自己的身体。

组内今天有同事晋升，也让我非常苦恼。被晋升的同事比我优秀，也更值得被晋升。如果让我来想和他差在哪里？1. 为人和善，和每一位同事都能相处融洽；2. 处理问题能力强。针对与同事相处融洽这点，我好像只欣赏自己看上的人，对一些普通同事，太苛责。还有就是自己爱骂人，虽然不是恶意。针对处理问题能力强这点，倒不是说我不行，而是我能寻迅速解决一些完全是自己掌控下出现的问题，非自己掌握的情况下，就非常便秘。进一步来说，自己或许擅长从流程和软件完整生命周期内，思考和解决问题，而不擅长投入到细碎和具体的业务中。我总是希望用一些方式，预防问题发生，减少问题的发生，而不是修复问题。在我看来，这是“战术上的勤奋”掩盖“战略上的懒惰”。难道公司需要有战斗力的员工，而非我这种从研发效率方面解决问题的人？

刚和父亲打了电话，聊了我的想法。父亲说了一些不痛不痒的话后，转头又给生哥拨过去，他的事说完到我这儿，就要做饭了。匆匆挂了电话，我认真思考起来：商业才能让技术产生价值。我想用自己掌握的技术，为社会创造出一丁点儿的贡献也好。努力地成长为 T 型的人，学习软件工程，实践软件架构，接触 React、Vue 和 Flutter，都是为了让自己能一个人承担起完整商业产品。这都是沉没成本。

可惜，不能说给某人听了。

描述

调用自身就是递归。

阅读顺序

1. 找出跳出递归的条件；
2. 查看跳出时，程序如何执行；
3. 查看跳出程序的前一步，程序如何执行；
4. 一直往前推；

补充

递归不会改变算法的时间复杂度。但递归作为算法的核心组件，会影响算法的速度。

递归适用于无法估计计算深度的问题。

示例代码

golang

java

Redis 中的流是包含零个或任意多个流元素的有序队列，队列中的每个元素都包含一个 id 和任意多个键值对，这些元素会根据 id 的大小在流中有序地进行排列。

流中元素 id

基本命令

XADD

将一个带有指定 id 和键值对的元素追加到 stream 中，并返回插入的 id。

id 的限制：

1. 同一个流中的不同元素是不允许使用相同ID的;

2. 新元素的ID必须比流中所有已有元素的ID都要大;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

-- 将 id = 1100000000000-12345，k1 v1 的键值对添加到 s1 中
-- id 由毫秒事件 millisecond 和顺序编号 sequcen number 组成
XADD s1 1100000000000-12345 k1 v1

-- 1000000000000-0. 只包含毫秒时间，没有编号。将编号设置为 0
XADD s1 1000000000000 k1 v1

-- 使用 * 来自动生成元素 id
XADD s1 * k2 v2

-- 使用先进先出的方式限制 s1 的长度为 2
XADD s1 MAXLEN 2 * k1 v1
XADD s1 MAXLEN 2 * k2 v2
-- 此时 s1 中保存 k2 和 k3
XADD s1 MAXLEN 2 * k3 v3

时间复杂度：O(logn)

XTRIM

将 streamn 修剪为最大长度，也是采用先进先出的方式，返回移除的个数。

1
2

-- 1
XTRIM s1 MAXLEN 1

时间复杂度：O(logn + m)

XDEL

根据 id 删除一个或多个元素，返回删除元素数量。

1
2
3

XDEL s1 1683948051401-0

XDEL s1 1683948051401-1 1683948051401-2

时间复杂度：O(logn * m)

XLEN

返回 stream 中元素个数，不合法就返回 0.

1
2
3
4
5
6

XADD s1 * k1 v1
XADD s1 * k2 v2
XADD s1 * k3 v3

-- 3. 返回 s1 中元素个数
XLEN s1

时间复杂度：O(1)

XRANGE

提供获取 stream 中元素的各种方式，如果不合法返回 nil。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

XADD s1 * k1 v1
XADD s1 * k2 v2
XADD s1 * k3 v3
XADD s1 * k4 v4
XADD s1 * k5 v5
XADD s1 * k6 v6
XADD s1 * k7 v7

-- 根据 id 获取指定元素
XRANGE s1 1683948592439-0 1683948592439-0
-- 获取 id 闭区间内的所有元素
XRANGE s1 1683948592251-0 1683948592773-0
-- 获取 stream 中所有元素
XRANGE s1 - +
-- 对返回元素数量做限制，根据 id 升序返回
XRANGE s1 - + COUNT 2

时间复杂度：O(logn + m)

XREVRANGE

同 XRANGE，唯一不同的是 id 的逆序版本。

XREAD

提供获取 stream 中元素的各种方式，如果不合法返回 nil。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

XADD s1 * k1 v1
XADD s1 * k2 v2
XADD s1 * k3 v3
XADD s1 * k4 v4
XADD s1 * k5 v5
XADD s1 * k6 v6
XADD s1 * k7 v7

XADD s2 * k1 v1
XADD s2 * k2 v2
XADD s2 * k3 v3
XADD s2 * k4 v4
XADD s2 * k5 v5
XADD s2 * k6 v6
XADD s2 * k7 v7

-- 返回 s1 中 id > 1683948592043-0 的前 3 个元素
XREAD COUNT 3 STREAMS  s1 1683948592043-0
-- 同时返回 s1 中 id > 1683948592043-0 的前 3 个元素，s2 中 id > 1683949330708-0 的前 3 个元素
XREAD COUNT 3 STREAMS  s1 s2 1683948592043-0 1683949330708-0
-- 阻塞式读取 s2 中 id > 1683949809119-0 的前 2 个元素，时间单位 ms， 0 表示一直等待
XREAD BLOCK 0 COUNT 2 STREAMS s2 1683949809119-0

时间复杂度：O(logn + m)

XGROUP

管理消费者组，增删改。

id 用来限定消费者能够接收到消息范围。

1
2
3
4
5
6

-- 在 s1 上创建一个名为 all-msg 的消费者组，可以接收 > 0-0 的消费者 时间复杂度：O(1)
XGROUP CREATE s1 all-msg 0-0
-- 修改消费者组的 id 时间复杂度：O(1)
XGROUP SETID s1 all-msg 10086
-- 删除消费者组 时间复杂度：O(n + m)
XGROUP DESTROY s1 all-msg

总结

• stream 用来支持消息队列；
• stream 中包含零个到多个元素的有序队列；
• stream 的 id 由“毫秒时间”和“顺序编号“组成；
• 消费者组允许将一个 stream 从逻辑上划分为多个不同的 stream，让 group 所属的 comsumer 消费；
• 消息的生命周期：不存在 -> 未递送 -> 待处理 -> 已确认