这是我参与「第三届青训营 –后端场」笔记创造活动的第3篇笔记.
01 为什么要学习数据结构与算法
好的数据结构与算法能够提高程序的运转速度。
数据结构与算法简直存在于程序开发中的所有地方!
本文首要介绍的是排序算法。
02 经典排序算法
- 插入排序
- 快速排序
- 堆排序
堆排序其实是一种挑选排序，每次挑选出剩下元素中最大的放到最后面，只不过凭借大根堆，挑选最大元素的时刻复杂度能够降为O(logn)
理论时刻复杂度
| Best | Avg | Worst | |
|---|---|---|---|
| 插入排序 | O(n) | O(n^2) | O(n^2) |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) |
实践场景benchmark
测验的场景有
- 完全随机的状况(random)
- 有序/逆序的状况(sorted/reverse)
- 元素重复度较高的状况(模(mod)8处理)
在上面的基础上，还依据序列的长度进行了划分（16/128/1024）
Benchmark-random
定论：在随机的状况下：
- 插入排序在短序列中速度最快
- 快速排序在其他状况下速度最快
- 堆排序速度与最快算法差距不大
为什么快速排序和堆排序的期望时刻复杂度都是O(nlogn)，而快速排序要稍微快一点呢？
- 由于快速排序在partion的时分拜访的都是按顺序拜访元素，能够利用局部性原理，命中cache的几率更大
- 而堆排序在拜访儿子节点(
i*2,i*2+1)的时分是有跨度的
Benchmark-sorted
- 插入排序遇到了最好的状况：O(n)，速度最快
- 快速排序遇到了最坏的状况：O(n^2)，速度最慢
实践场景 benchmark 定论
- 所有短序列和元素有序的状况下，插入排序功用最好
- 在除了有序的状况的场景下，快速排序的功用最好
- 简直在任何状况下，堆排序的体现都比较稳定，与最快的相差不大
规划一个更好的算法？
能否规划一个算法，使得这个算法能一起拥有插入排序，快速排序，堆排序的优点？
| Best | Avg | Worst | |
|---|---|---|---|
| 插入排序 | O(n) | O(n^2) | O(n^2) |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) |
| ??? | O(n) | O(nlogn) | O(nlogn) |
这个算法就是下面要介绍的pdqsort算法
03 从零开始打造pdqsort
pdqsort(pattern-defeating-quicksort) 是一种不稳定的混合排序算法，它的不同版别被应用在C++ BOOST、Rust以及Go 1.19中。它对常见的序列类型做了特殊优化，使得在不同条件下都拥有不错的功用。
pdqsort-version1
思维是结合三种排序算法的优点
- 对于短序列（小于必定长度）咱们运用插入排序
- 其他状况，是哦那个快速排序来确保全体功用
- 当快速排序体现欠安时，运用堆排序来确保最坏状况下时刻复杂度仍为O(nlogn)
问题
- 短序列的长度详细是多少？
- 12~32，在不同语言和场景中会有不同，在泛型版别依据测验选定24
- 怎样知道快速排序体现欠安，以及何时切换到堆排序？
- 当终究pivot的位置离序列两端很挨近时（间隔小于length/8）判定其体现欠安
- 当这种状况的次数到达limit（bits.Len(length)）时，切换到堆排序
详细的流程
还能再改善吗？
- 快速排序中pivot的挑选会影响速度，改善：改善choose pivot，尽量使pivot为序列的中位数
- 改善partition（此优化在Go体现不好，略）
pdqsort-version2
回顾pivot的挑选战略：运用首个元素作为pivot：O(1)复杂度，但在某些状况下作用不好（当pivot常常离中位数比较远的时分）
为了确保快排的平均时刻复杂度为O(nlogn)，则挑选pivot的时刻复杂度就不能超过O(n)。
所以咱们优化的目标是：
- 挑选pivot的时刻复杂度尽或许的低，最多不能超过O(n)
- pivot尽或许地挨近中位数
即 “寻找pivot所需要的开销”和“pivot带来的功用优化”之间的平衡
如果要精确地找到序列中的中位数，则时刻复杂度至少是O(nlogn）的（计数排序虽然能够做到O(n)但是运用场景有限，所以不考虑），这样的时刻复杂度显然是不可的。
所以咱们只能近似地寻找中位数：经过采样去估计中位数（概率论里面的知识）。很显然，采样的个数占总个数的比例越高，估计中位数就或许越挨近真实中位数，但用时就会越高。所以会依据序列长度不同，来决定挑选战略：
- 短序列(<=8)，挑选固定元素
- 中序列(<=50），采样3个元素 median of three
- 长序列(>50），采样9个元素 median of medians
经过采样咱们能够猜测序列的状态：
- 采样的元素都是逆序排列 -> 序列或许现已逆序 -> 反转整个序列
- 采样的元素是都顺序排列 -> 序列或许现已有序 -> 运用插入排序
注：插入排序实践运用partialInsertionSort，即有约束次数的插入排序（由于序列只是有概率有序，如果不是的话，插入排序则会耗费大量的时刻）
详细的流程
version1升级到version2优化总结：
- 经过采样估计序列的信息：
- 序列的中位数 -> 改善了pivot的挑选战略
- 发现序列或许逆序，则反转序列 -> 应对了reverse场景
- 发现序列或许有序，运用有限插入排序 -> 应对了sorted场景
至此，咱们现已完成了大部分场景的优化，回顾最初提到的测验场景，咱们还没有对元素重复度比较高的序列进行优化。
pdqsort-final version
- 元素重复度较高或许会带来什么问题？
- 元素重复度较高，或许会导致两次partition生成的pivot相同，即进行了无效的切割。
- 采样的时分检查重复度能解决这个问题吗？
- 不是很好，由于采样数量有限，不必定能采样到相同元素
- 解决方案（partitionEqual）
- 当检测到此时的pivot和上次相一起（发生在leftSubArray），运用partitionEqual将重复元素排列在一起，削减重复元素对于pivot挑选的干扰
其他的优化：当pivot挑选战略体现欠安时，随机交换元素，防止一些极点状况使得快速排序总是体现欠安，以及一些黑客攻击状况。
详细流程：
至此，咱们总算能够完成最初的表格了：
| Best | Avg | Worst | |
|---|---|---|---|
| 插入排序 | O(n) | O(n^2) | O(n^2) |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) |
| pqdsort | O(n) | O(nlogn) | O(nlogn) |
一台云服务器上的测验
- 在有序或许逆序状况下提高10x
- 其他状况下有10~50%提高
其他
- 高功用的排序算法是怎么规划的？
- 依据不同状况挑选不同功用战略，取长补短
- 生产环境中运用的排序算法和课本上的排序算法有什么差异？
- 理论算法注重理论功用，例如时刻、空间复杂度等。生产环境中的算法需要面临不同的事情场景，愈加注重实践功用
- Go语言(<=1.18)的排序算法是快速排序么？
- 实践一直是混合排序算法，主体是快速排序。Go<=1.18时的排序发也是根据快速排序，和pdqsort的差异在于fallback机遇、pivot挑选战略、是否有针对不同pattern优化等。
参考资料
- 课程PPT：数据结构与算法.pptx
- Proposal: github.com/golang/go/i…
- Paper: arxiv.org/pdf/2106.05…
- Code: github.com/golang/go/b…
- 公众号文章：mp.weixin.qq.com/s/5HqfRGqPy…
