【字节跳动】第十二讲 数据结构与算法 ｜ 青训营笔记

讲师介绍：

张云浩：字节跳动-程序语言团队成员，目前主要研究方向包括但不限于性能优化、(并发)数据结构和算法等领域。

GitHub：github.com/zhangyunhao116

目录

1. 为什么要学习数据结构和算法
2. 了解课本上学习到的算法和真正在生产实践中使用的算法之间的差异
3. 经典排序算法
4. 复现在课本上学习到的经典排序算法，讲解它们的原理以及特点
5. 从零开始打造pdqsort
6. 从零开始打造目前业界性能一流的排序算法pdqsort(Pattern-Defeating-QuickSort)

1. 为什么要学习数据结构和算法

1.1 列子-抖音直播排行榜功能

规则：某个时间段内，直播间礼物数TOP10房间获得奖励，需要在每个房间展示排行榜

解决方案：

• 礼物数量储存在Redis-zset中，使用skiplist使得元素整体有序
• 使用Redis集群，避免单机压力过大，使用主从复制算法、分片算法
• 保证集群原信息的稳定，使用一致性算法
• 后端使用缓存算法(LRU)降低Redis压力，展示房间排行榜

数据结构和算法几乎存在于程序开发中的所有地方（这是我之前从未实践过的）

什么是最快的排序算法？

Python-timsort C++-introsort Rust-pdqsort

Go的排序算法有没有提升空间？

Go(<=1.18)-introsort

之后有一个人给官方建议Go使用泛型实现Rust的pdqsort算法

发现在pdqsort快了十倍基础上，Go实现起来大约是2X~60X。

重新实现的Go排序算法，在某些常见场景中比之前算法快了大约10倍，成为Go1.19的默认排序算法

遗留问题

• Go 1.19 的排序算法是如何设计的？
• 生产环境中使用的排序算法和课本上的排序算法有什么区别？
• Go语言的排序算法是快速排序吗？

2. 经典排序算法

2.1 Insertion Sort 插入排序

将元素不断插入已经排序号的array中

• 起始只有一个元素5，其本身是一个有序序列
• 后续元素插入有序序列中，即不断交换，直到找到第一个比其小的元素

缺点：平均和最坏情况的时间复杂度高达O(n^2)

优点：最好情况时间复杂度为O(n)

遗留问题：插入排序有什么缺点？如果你来优化如何优化？

2.2 Quick Sort 快速排序

分治思想，不断分割序列直到序列整体有序

• 选定一个pivot(轴点)
• 使用pivot分割序列，分成元素比pivot大和元素比pivot小两个序列

缺点：最坏情况的时间复杂度高达O(n^2)

2.3 堆排序

利用堆的性质形成的排序算法

• 构造一个大顶堆
• 将根节点(最大元素)交换到最后一个位置，调整整个堆，如此反复

缺点：最好情况的时间复杂度高达O(n*logn)

2.4 Benchmark

2.4.1 经典算法理论印象：

• 插入排序平均和最坏情况时间复杂度都是O(n^2)，性能不好
• 快速排序整体性能处于中间层次
• 堆排序性能稳定，“众生平等”

2.4.2 实际场景 benchmark

根据序列元素排列情况划分

• 完全随机的情况(random)
• 有序/逆序的情况(sorted/reverse)
• 元素重复度较高的情况(mod8)

在此基础上，还需要根据序列长度的划分(16/128/1024)

2.4.3 Benchmark-random

• 插入排序在短序列中速度最快
• 快速排序在其他情况中速度最快
• 堆排序速度与最快算法差距不大

2.4.4 Benchmark-sroted

• 插入排序在序列已经有序的情况下最快

2.4.5 实际场景benchmark结论

• 所有短序列的元素有序情况下，插入排序性能最好
• 在大部分的情况下，快速排序有较好的综合性能
• 几乎任何情况下，堆排序的表现都比较稳定

我认为这个比例不是很好，并不能完全表达这三种排序

2.4.6 设计一个更好的算法？

我们市内出行的时候，常常会选择多种工具来到达目的地，排序算法是否也可以如此呢？

3 从零开始打造pdqsort

3.1 pdqsort简单介绍

是一种不稳定的混合排序算法，它的不同版本被应用在C++ BOOST、Rust以及Go1.19中。它对常见的序列类型做了特殊的优化，使得在不同条件下都拥有不错的性能

3.2 版本介绍

3.2.1 版本一

综合三种排序方法的优点

• 对于短序列(小于一定长度)我们使用插入排序
• 其他情况，使用快速排序来保证整体性能
• 当快速排序表现不佳时，使用堆排序来保证最坏情况下时间复杂度仍然为O(n*logn)

Q&A

1. 短序列的具体长度是多少呢？

12~32，在不同语言和场景中会有不同，在泛型版本根据测试选定24。为什么会不同，是因为每个语言的执行效率问题吗？

2. 如何得知快速排序表现不佳，以及何时切换到堆排序？

当最终pivot(中心点)的位置离序列两端很接近时(距离小于length/8)判定其表现不佳，当这种情况的次数达到 limit(限制) (即bits.Len(length))时，切换到堆排序

简单来说：数组中的已经排好的数中的中心值在未排序的数组中的位置距离两端很近（指离下标0和最length-1很接近），什么时候算近？小于lenght/8就表示快速排序效率不佳，需要换成堆排序

• 对于短序列(<=24)我们使用插入排序
• 其他情况，使用快速排序(选择首个元素作为pivot)来保证整体性能
• 当快速排序表现不佳时(limit==0)，使用堆排序来保证最坏的情况下时间复杂度仍然为O(n*logn)

3. 如何让pdqsort速度更快？

• 尽量使得QuickSort的pivot 为序列的中位数 -> 改进 choose pivot
• Partition速度更快 -> 改进partition，但是此优化在Go表现不好，略

3.2.2 版本二

1. 思考关于pivot的选择

• 使用首个元素作为pivot（最简单的方案）

实现简单，但是往往效果不好，例如在sorted情况下性能很差

• 遍历数组，寻找真正的中位数

遍历对代价很高，性能不好

问题描述：找到【寻找pivot所需要的开销】和【pivot带来的性能优化】两个方法的平衡点

解决方法：寻找近似中位数

2. 根据序列长度的不同，来决定选择策略（更加细节化的优化）

例如：优化-Pivot的选择

• 短序列(<=8),选择固定元素
• 中序列(<=50),采样三个元素，median of three
• 长序列(>50),采样九个元素，median of medians

3. Pivot 的采样方式使得我们有探知序列当前状态的能力

• 采样的元素都是逆序排列 -> 序列可能已经逆序 -> 翻转整个序列
• 采样的元素都是顺序排列 -> 序列可能已经顺序 -> 使用插入排序（插入排序在可能有序的情况下是最优的）

注意：插入排序实际使用partiallnsertionSort，即有限制次数的插入排序（说明：指插入排序如果在一定的限制次数下还没有排好序，我们就直接放弃，换其他方法，以防止继续浪费性能）

4. 总结：

Version1升级到Version2优化总结

• 升级pivot选择策略（近似中位数）
• 发现序列可能逆序，则翻转序列 -> 应对reverse 场景
• 发现序列可能顺序，使用有限插入排序 -> 应对sorted 场景

3.2.3 还有什么场景没有优化？

• 短序列情况
  • 使用插入排序(v1)
• 极端情况
  • 使用堆排序保证算法的可行性(v1)
• 完全随机的情况（random）
  • 更好的pivot选择策略(v2)
• 顺序/逆序的情况（sorted/reverse）
  • 根据序列状态翻转或者插入排序(v2)
• 元素重复度较高的情况（mod8） -> ?

1. 如何优化重复元素很多的情况？

• 采样pivot的时候检测重复度？

不是很好，因为采样数量有限，不一定能采样到相同元素

解决方案：

如果两次partition生成的pivot相同，即partition进行了无效分割，此时认为pivot的值为重复元素

• 优化-重复元素较多的情况(partitionEqual)

当检测到此时的pivot和上次相同时（发生在leftSubArray），使用partitionEqual将重复元素排列在一起，减少重复元素对于pivot选择的干扰

• 优化-当pivot选择策略表现不佳时，随机交换元素

避免一些极端情况使得QuickSort总是表现不佳，以及一些黑客攻击情况

2. 一台云服务器上的测试

• 在有序或者逆序情况下提升10倍
• 其他情况下有10~50%提升

4. 总结

高性能的排序算法是如何设计的？

根据不同情况选择不同策略，取长补短

生产环境中使用的排序算法和课本上的排序算法有什么区别？

理论算法注重理论性能，例如时间、空间复杂度等。生产环境中的算法需要面对不同的实践场景、更加注重实践性能

Go语言(<=1.18)的排序算法是快速排序么？

实际一直是混合排序算法，主体是快速排序。Go<=1.18版本的算法也是基于快速排序，和pdqsort的区别在于fallback时机、pivot选择策略、是否有针对不同pattern优化等

Proposal: <https://github.com/golang/go/issues/50154>

Paper:<https://arxiv.org/pdf/2106.05123.pdf>

Code:<https://github.com/golang/go/blob/master/src/sort/zsortinterface.go>

公众号文章:<https://mp.weixin.qq.com/s/5HqfRGqPyAhFt0krPgMHOQ>

课后作业：实现pdqsort-version1

实现一个堆排序和插入排序以及快速排序，进行书写方案一的混合排序