[架构师训练营第 1 期] 第八周学习总结

本周了解了性能优化相关的一些底层或者基本的知识，它们是设计优化手段的基础。包括：

• 文件与硬盘 I/O

• 常见的数据结构

• 常见的经典算法

• 网络通讯基本原理

• 非阻塞网络 I/O

本周总结就不重复课程内容了，课程需要温故而知新。

这里就罗列一些自己关于算法和数据结构的理解。

关于排序

1. 总结一个可能不很成熟的规则

排序的对象可以分为三类：

1. 数值；

2. 单字符；

3. 字符串；

其中：

1. 桶排序和计数排序适用于数值或单字符的排序；

2. 基数排序适用于字符串排序，其过程中对每一个字符的排序则使用的是桶排序或计数排序；

它们有各自的限制：

1. 计数排序对于非自然数需要归化成自然数；

2. 计数排序的排序范围还不能太大；

3. 桶排序的排序范围比技术排序要大，但同样不能过大；

4. 基数排序对于长度不一需要补全成长度一致；

5. 基数排序还需要字符串各个位存在递进关系；

6. 基数排序逐个位比较需要依赖桶或计数排序；

7. 基数排序的字符串长度还不能太长；

场景：

1. 外部存储的而内存有限，可用桶排序；

2. 自然数排序且范围不大，可用计数排序；

3. 字符串排序可用基数排序。

2. 总结一个工业级排序算法的实现思路

首先是排序复杂度的选择：

对于小规模排序应选 O(n²)，

对于大规模排序应选 O(nlogn)；

然后是实现算法的选择：

对于 O(nlogn)，选归并还是快速？

归并排序是非原地算法，不会退化，

快速排序是原地算法，有概率退化，

从空间复杂度考虑，选择快速排序；

接着是如何解决快速排序的退化问题：

从原因入手，关键在于确定合理的分区，

最理想的分区是分区两边数量相近，

方法有三数取中法和随机法；

最后是一些极致优化措施。

一个实例是 C 语言的 qsort()：

它在数量小于等于 4 时，使用插入排序，

在数量大于 4 但不大时，使用归并排序，

在数量大到一定程度时，使用快速排序，

快速排序分区方法使用的是三数取中法，

另外还使用哨兵简化操作，极致化性能。

关于查找

1. 总结一个二分查找的思想

目标值每次都与待查区间中间值比较，相等则返回下标，不相等则缩小待查区间为原来的一半；循环直到返回下标（即找到）或待查区间长度为 0（即没找到）为止。

二分查找的时间复杂度：O(logn)。

二分查找的实现要注意：

循环退出条件（不仅小，还要等）

中间值的取值（避溢出，位优化）

高低值的更新（应避开死循环）

二分查找的应用局限性：

依赖顺序数据结构（因为要求随机访问）

依赖有序数据内容（导致动态维护成本）

不适合数据量太小（因为优势不够明显）

不适合数据量太大（导致申请不够内存）

2. 总结一个二分查找的变体问题思路

二分查找的基本思路：

目标值每次都与待查区间中间值比较，

相等则直接返回下标，不相等则缩小待查区间为原来的一半；

循环直到返回下标（即找到）或待查区间长度为 0（即没找到）为止。

对于以下变体问题，基于以上的常规二分思想，解决的问题在于：

相等的时候不能直接返回，因为返回的有可能不是第一个或最后一个

相等的时候应该进行判断，如果不是第一个或最后一个，则继续二分

变体一：查找第一个值等于给定值的元素

变体二：查找第一个大于等于给定值的元素

变体三：查找最后一个值等于给定值的元素

变体四：查找最后一个小于等于给定值的元素

关于跳表

跳表 = 链表 + 索引，采用的是空间换时间的思路，为链表建立一级或多级索引，从而实现随机访问 O(logn) 的时间复杂度。

跳表的空间复杂度为 O(n)，但它对实际空间占用的影响分两种情况：

1. 第一种是原始链表中的数据存储的是其对应对象的索引或关键值；

2. 第二种是原始链表中的数据存储的就是数据本身；

对于第一种情况，跳表占用的空间并不是数据本身（对象）的大小，而是其索引或关键值，因此相对影响较小；

对于第二种情况，跳表占用的空间就是数据本身的大小，所以相对影响较大；

解决方法是扩大同级中索引之间的跨度，从而减小索引层级，降低空间占用。

跳表的实现还要注意在插入和删除操作中索引的动态维护，否则可能导致两个索引之间的节点过多，造成时间复杂度的退化。

跳表索引动态维护的方法之一是在删除时删除索引，插入时随机在某级中建立相应索引，其中随机函数应该能够保证跳表的索引大小和数据大小的平衡性，不致于性能的过度退化。

关于哈希

“哈希算法”也叫“散列算法”。

定义是：将 任意长度的 二进制值串映射为 固定长度的二进制值串 的规则。

要求有：不可逆；输入敏感度高；冲突概率小；执行效率高。

应用于：安全加密；唯一标识；数据校验；散列函数；

负载均衡；数据分片；分布式存储。

不同应用中所关注的哈希算法要求也不同，如：

安全加密应用中，除了要求不可逆，还要求冲突概率尽可能小；

唯一标识应用中，不甚要求不可逆，只要求冲突概率尽可能小；

数据校验应用中，则要求输入敏感度要高；

散列函数应用中，则要求算法执行效率高。

这是因为，基于抽屉原理，哈希算法不可能做到零冲突，哈希值越长则冲突概率越小，但越复杂、越难破解的算法通常计算时间也越长，因此实际应用中往往需要根据具体情况权衡安全性和计算时间。

关于二叉树

树的节点概念：父节点、子节点、兄弟节点；无父为根、无子为叶。

树的度量概念：高度、深度、层数。

• 节点的高度：该节点到叶节点的最长路径（或边数）；

• 节点的深度：根节点到该节点经历的路径（或边数）；

• 节点的层数：节点的深度 + 1；

• 树的高度：= 根节点的高度。

所以，二叉树也就是每个节点<最多<只有两个子节点的树；

• 特别，每个节点都有两个子节点的二叉树，称为“满二叉树”；

• 特别，用数组存储时可完全利用数组空间的二叉树，称为“完全二叉树”。

二叉树的存储（或表示）方式有两种：

• 链式存储法：基于指针或引用，用于大部分二叉树；

• 数组存储法：基于数组，特别适用于完全二叉树（因为完全利用空间）。

二叉树的遍历方式有三种：（本的位置为前中后）

• 前序遍历：先遍其（本）身，再遍其左子，后遍其右子；

• 中序遍历：先遍其左子，再遍其（本）身，后遍其右子；

• 后序遍历：先遍其左子，再遍其右子，后遍其（本）身。

二叉查找树最大的特点是支持动态数据集合的快速插入、删除、查找。

这依赖于它的结构：对于树中任意节点：

其左子树中每个节点的值 < 该节点值；

其右子树中每个节点的值 < 该节点值。

二叉查找树还有一个重要的特性：中序遍历输出有序序列，时间复杂度 O(n)。

因此二叉查找树也称为“二叉排序树”。

当二叉查找树存储的是对象的键值时，可能存在重复情况，

此时稍微调整数据结构即可满足需求。有两种方法：

1. 把值相同的数据都存储在一个节点上；

2. 把值相同的数据当做值大于该值来存。

对于第二种方法，在查找和删除过程中，查找到一个数据之后还应继续查找。

二叉查找树的时间复杂度：

从 极度不平衡 到 完全二叉树 对应 从 O(n) 到 O(height)≈O(logn)。

二叉查找树与散列表相比特点

1. 有序（只需中序遍历）

2. 稳定（在使其平衡后）

3. 高效（在使其平衡后）

4. 简单（只需考虑平衡）

5. 低耗（无装载因子限制）

关于红黑树

为了解决二叉查找树性能退化的问题，出现了平衡二叉树的数据结构。

平衡二叉树的严格定义是：任一节点其左右子树高度之差不大于 1。

（完全二叉树一定是平衡二叉树，但平衡二叉树不只有完全二叉树）

平衡二叉树可以解决性能退化问题，但它需要在插入和删除的过程中进行维护，以保证其总是满足平衡二叉树的定义。这种维护的时间复杂度必须也是可以接受的，否则就仍然不是工程上令人满意的。

红黑树是一种不完全满足平衡二叉树严格定义的数据结构，但是它在维护其平衡性的过程（插入和删除节点）当中，时间复杂度都是 O(logn)。所以相对于 AVL、Treap 和 Splay Tree，红黑树的工程应用会更加广泛，这得益于它极其稳定的查找和维护性能。

据说现在用红黑树的较少，多用跳表替代了。