Week 8 作业 02

提高I/O 速度

• 机械硬盘用旋转来寻找数据元（B + 树数据结构）





• 固态硬盘使用类似RAM的储存，速度肯定比机械硬盘快







Linux Inode 文件控制块

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

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

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



RAID 提升读写速度





常见数据结构

时间复杂度与空间复杂度

时间复杂度

• 并不是计算程序具体运行的时间，而是算法执行语句的次数。

• O(2^n) 表示对 n 数据处理需要进行 2^n 次计算

• 多项式时间复杂度

• 非多项式时间复杂度



空间复杂度

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

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







数组

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

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

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



链表

• 链表可以使用零散的内存空间存储数据。

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

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

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



HASH表原理

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

Hash 冲突



栈

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

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

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

线程调用栈

void f(){

int x = g(1);

x++; //g 函数返回，当前堆栈顶部为f函数栈帧，在当前栈帧继续执行f函数的代码。

}

int g(int x){

return x + 1;

}



队列

• 队列也是一种操作受限的线性表，栈是后进先出，而队列是先进先出。

• 典型应用场景：生产者消费者；阻塞等待的线程被放入队列。



用队列搜索好友中关系最近的有钱人



用队列搜索最短路径



树



二叉排序树

• 左子树上所有结点的值均小于或等于它的根结点的值。

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



不平衡的二叉排序树



平衡二叉（排序）树

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



旋转二叉树恢复平衡

插入时，最多只需要两次旋 转就会重新恢复平衡。 删除时，需要维护从被删节 点到根节点这条路径上所有 节点的平衡性，时间复杂度 O(logN)。



红黑书原理

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

• 根节点是黑色的。

• 每个叶子节点（NIL）都是黑色的空节点。

• 从根节点到叶子节点，不会出现两个连续的红色节点。

• 从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。





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

红黑树 VS 平衡二叉树

红黑树最多只需3次旋转就会重新达成红黑平衡，时间复杂度 O(1)。 在大量增删的情况下，红黑树的效率更高。 红黑树的平衡性不如平衡二叉树，查找效率要差一些。



跳表



常用算法

• 穷举算法

• 递归算法

• 递归算法（快速排序算法）

• 时间复杂度： n * log(n)

• 要有退出条件，不然会容易溢出



• 贪心算法

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

• 改进贪心算法 - 迪杰斯特拉算法（最快路径）

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

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

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

• 计算最终路径。

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







• 动态规划

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

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

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





遗传算法解决背包问题

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

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

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







选择算法

在剩下的染色体中选择可以被遗传下去的染色体以及繁殖次数



选择算法

• 轮盘赌选择（Roulette Wheel Selection）：是一种回放式随机采样方法。每个染色体 进入下一代的概率等于它的适应度值与整体适应度值和的比例。

• 随机竞争选择（Stochastic Tournament）：每次按轮盘赌选择一对个体，然后让这两 个个体进行竞争，适应度高的被选中，如此反复，直到选满为止。

• 均匀排序：对群体中的所有个体按期适应度大小进行排序，基于这个排序来分配各个 个体被选中的概率。



交叉遗传

选择结果：101010 和 010101各繁殖两次

生产下一代：染色体交叉遗传



循环迭代，如果连续几代遗传都没有出现更强的染色体（价值总和更大），那么算法收 敛，当前最大价值的染色体为最终解。

有时候会在遗传过程中进行基因突变，得到基因突变染色体。



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



网络通信基本原理



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

1. 物理层负责数据的物理传输，计算机输入输出的只能是 0 1 这样的二进制数据，但是在 真正的通信线路里有光纤、电缆、无线各种设备。光信号和电信号，以及无线电磁信号 在物理上是完全不同的，如何让这些不同的设备能够理解、处理相同的二进制数据，这 就是物理层要解决的问题。

2. 数据链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以 帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制。 链路层会定义帧的大小，这个大小也被称为最大传输单元。像 HTTP 要在传输的数据上 添加一个 HTTP 头一样，数据链路层也会将封装好的帧添加一个帧头，帧头里记录的一 个重要信息就是发送者和接受者的 MAC 地址。MAC 地址是网卡的设备标识符，是唯一 的，数据帧通过这个信息确保数据送达到正确的目标机器。

3. 网络层 IP 协议使得互联网应用根据 IP 地址就能访问到目标服务器，请求离开 App 后， 到达运营服务商的交换机，交换机会根据这个 IP 地址进行路由转发，可能中间会经过很 多个转发节点，最后数据到达目标服务器。 网络层的数据需要交给链路层进行处理，而链路层帧的大小定义了最大传输单元，网络 层的 IP 数据包必须要小于最大传输单元才能进行网络传输，这个数据包也有一个 IP 头， 主要包括的就是发送者和接受者的 IP 地址。

4. 传输层（TCP协议） IP 协议不是一个可靠的通信协议，不会建立稳定的通信链路，并不会确保数据一定送达。要保证通 信的稳定可靠，需要传输层协议 TCP。 TCP协议是一种面向连接的、可靠的、基于字节流的传输层协议。TCP作为一个比较基础的通讯协 议，有很多重要的机制保证了TCP协议的可靠性和强壮性： 使用序号，对收到的TCP报文段进行排序和检测重复的数据 无错传输，使用校验和检测报文段的错误 使用确认和计时器来检测和纠正丢包或者延时 流量控制，避免主机分组发送得过快而使接收方来不及完全收下 拥塞控制，发送方根据网络承载情况控制分组的发送量，以获得高性能同时避免拥塞崩溃 丢失包的重传



网络数据包格式















HTTP/1.1 试图引入保持连接的概念来解决这些问题，它允许客户端复用 TCP 连接，从 而分摊了建立初始连接和针对多个请求缓慢启动的成本。但任意时点上每个连接只能执 行一次请求 / 响应交换。 随着网络的发展，网站所需资源（CSS、JavaScript 和图像等）不断增长，浏览器在获 取和呈现网页时需要越来越多的并发性。但由于 HTTP/1.1 只允许客户端同时进行一次 HTTP 请求 / 响应交换，因此在网络层上获得并发能力的唯一方法是并行使用多个 TCP 连接。



HTTP/2 引入了 HTTP“流”的概念，允许将不同的 HTTP 并发地复用到同一 TCP 连接 上， 使浏览器更高效地复用 TCP 连接。HTTP/2 解决了单个 TCP 连接的使用效率低的 问题，现在可以通过同一连接同时传输多个请求 / 响应。但是，TCP并不理解HTTP流， 当多个HTTP请求复用一个TCP连接，如果前面的请求/响应没有处理完，后面的请求/响 应也无法处理，也就是会出现队头堵塞现象。



HTTP/3 不是使用 TCP 作为会话的 传输层，而是使用 QUIC （一种新 的互联网传输协议）。该协议在传 输层将流作为一等公民引入。多个 QUIC 流共享相同的 QUIC 连接， 因此不需要额外的握手和慢启动来 创建新的 QUIC 流。但 QUIC 流是 独立的，因此在大多数情况下，只 影响一个流的丢包不会影响其他流， 这是因为 QUIC 数据包封装在 UDP 数据包。



非阻塞网络I/O

计算机之间如何进行网络请求？ Socket、端口











非阻塞 I/O（ Non-Blocking I/O ）

非阻塞 I/O：I/O 操作立即返回,发起线程不会阻塞等待。

非阻塞 read 操作：

• Socket 接收缓冲区有数据，读 n 个（不保证数据被读完整，因此有可能需要多次读）。

• Socket 接收缓冲区没数据，则返回失败（不会等待）。

非阻塞write：

• Socket 发送缓冲区满，返回失败（不会等待）。

• Socket 发送缓冲区不满，写 n 个数据（不保证一次性全部写入，因此可能需要多次写）。