作业一：

（至少完成一个）

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。



请用代码（或伪代码）描述算法，并给出时间复杂度。

请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。

对象包括：客户端，NameNode，DataNode，元数据，时序图如下：



作业二：

• 根据当周学习情况，完成一篇学习总结



第8周 性能优化（二）

8.1 文件与硬盘 I/O：如何把硬盘的读写速度提高十万倍？

文件与硬盘I/O

机械硬盘





固态硬盘

固态硬盘有更快的速度





B+树





LSM锁





文件控制块

文件系统将硬盘空间以块为单位进行划分，每个文件占据若干个块，然后再通过一个文 件控制块 FCB 记录每个文件占据的硬盘数据块





Linux Inode 文件控制块

• inode中记录着文件权限、 所有者、修改时间和文件 大小等文件属性信息，以 及文件数据块硬盘地址索 引。

• inode是固定结构的，能 够记录的硬盘地址索引数 也是固定的，只有 15 个 索引。

• 每个inode最多可以存储 12+256+256*256+256*2 56*256 个数据块，如果每 个数据块的大小为 4k，也 就是单个文件最大不超过 70G。





RAID 独立硬盘冗余阵列







分布式文件系统HDFS





8.2 常见数据结构与Hash表原理分析

时间复杂度与空间复杂度

• 时间复杂度





•   空间复杂度

• 一个算法在运行过程中临时占用存储空间大小的量度。 

• O(n) 表示需要临时存储 n 个数据



 NP 问题

P 问题:能在多项式时间复杂度内解决的问题。

NP 问题:能在多项式时间复杂度内验证答案正确与否的问题。

NP ?= P

NP-hard 问题:比 NP 问题更难的问题(NP问题的解法可以规约到 NP-hard 问题的解法) NP 完全问题:是一个 NP-hard 问题，也是一个 NP 问题





数据结构

数组

创建数组必须要内存中一块连续的空间。

数组中必须存放相同的数据类型。

随机快速读写是数组的一个重要特性，根据数 组的下标访问数据，时间复杂度为 O(1)。





链表

链表可以使用零散的内存空间存储数据。 所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。 要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是 O(N)。





链表中增删数据要比数组性能好的多





数组链表结合，实现快速查找和快速增删





HASH表

如何既快速访问数据，又快速增删数据?





Hash 冲突





栈

数组和链表都被称为线性表。

栈就是在线性表的基础上加了这样的操作限 制条件:后面添加的数据，在删除的时候必 须先删除，即通常所说的“后进先出”。

线程运行时专有内存为什么被称为线程栈?





队列

队列也是一种操作受限的线性表，栈是后进先出，而队列是先进先出。 典型应用场景:生产者消费者;阻塞等待的线程被放入队列。





用队列搜索最短路径





8.3 红黑树原理与性能特性

树

二叉树

左子树上所有结点的值均小于或等于它的根结点的值。 右子树上所有结点的值均大于或等于它的根结点的值。 左、右子树也分别为二叉排序树。





不平衡的二叉排序树





 平衡二叉(排序)树

 从任何一个节点出发，左右子树深度之差的绝对值不超过1。 左右子树仍然为平衡二叉树。





旋转二叉树恢复平衡

插入时，最多只需要两次旋 转就会重新恢复平衡。

删除时，需要维护从被删节 点到根节点这条路径上所有 节点的平衡性，时间复杂度 O(logN)。





红黑(排序)树

 每个节点只有两种颜色:红色和黑色。

根节点是黑色的。

每个叶子节点(NIL)都是黑色的空节点。 从根节点到叶子节点，不会出现两个连续的红色节点。 从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点





增删节点的时候，红黑树通过染色和旋转，保持红黑树满足定义。





红黑树 VS 平衡二叉树

• 红黑树最多只需3次旋转就会重新达成红黑平衡，时间复杂度 O(1)。 

• 在大量增删的情况下，红黑树的效率更高。 

• 红黑树的平衡性不如平衡二叉树，查找效率要差一些。

跳表





8.4 经典算法

• 穷举算法

• 递归算法

• 贪心算法

• 动态规划

递归算法(快速排序算法)





 贪心算法

 背包问题:小偷背了一个4磅背包去商城偷东西，将哪些商品放入背包才能收益最大化。





 改进贪心算法 - 迪杰斯特拉算法(最快路径)

迪杰斯特拉算法(最快路径)





1. 找出“最便宜”的节点，即可在最短时间内到达的节点。

2. 更新该节点的邻居的开销，检查是否有前往它们的更短路径，如果有，就更新其开销。 

3. 重复这个过程，直到对图中的每个节点都这样做了。

4. 计算最终路径。





迪杰斯特拉算法的核心是找到起点到每个节点的最快路径





动态规划算法解决背包问题

通过找到合适的角度，将所求解的目标值在某(几)个维度上展开，将一个大问题拆解 为若干小问题，从小问题的最优解，寻找大问题的最优解





每个动态规划算法都从一个网格开始，背包问题的网格如下:





遗传算法解决背包问题

遗传算法(Genetic Algorithm, GA)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数 空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作;参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗 传算法的核心内容。

80公斤背包装哪些物品价值最大?





选择算法

遗传算法得到的不是最优解





8.5 网络通信基本原理与性能优化

 Web 请求的一次网络通信历





OSI 七层模型和 TCP/IP 四层模型





网络数据包格式





8.6 非阻塞网络I/O