Week 8 性能优化

evildracula

关注

发布于: 2020 年 12 月 13 日

文件与硬盘 IO

Linux inode 文件控制块

inode 中记录着文件权限、所有者、修改时间和文件大小等文件属性信息，以及文件数据块硬盘地址索引。
inode 是固定结构的，能够记录的硬盘地址索引数也是固定的，只有 15 个索引。
每个 inode 最多可以存储 12+256+256256+256256*256 个数据块，如果每个数据块的大小为 4k，也就是单个文件最大不超过 70G。

Raid 独立硬盘冗余阵列

分布式文件系统 HDFS

数据结构与算法

时间/空间复杂度

时间复杂度
并不是计算程序具体运行的时间，而是算法执行语句的次数
O(2^n) 表示对 n 数据处理需要进行 2^n 次计算
O(1), O(log(n)), O(n^a) 多项式时间复杂度
O(a^n), O(n!) 非多项式时间复杂度
空间复杂度
一个算法在运行过程中临时占用存储空间大小的量度
O(n) 表示需要临时存储 n 个数据

NP 问题

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

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

NP ?= P

NP-hard 问题:比 NP 问题更难的问题(NP 问题的解法可以规约到 NP-hard 问题的解法)

NP 完全问题:是一个 NP-hard 问题，也是一个 NP 问题。

数组

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

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

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

链表

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

所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。

要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是 O(N)。

Hash 表

Hash 冲突

栈

数组和链表都被称为线性表。
栈就是在线性表的基础上加了这样的操作限制条件:后面添加的数据，在删除的时候必须先删除，即通常所说的“后进先出”。
线程运行时专有内存被称为线程栈

队列

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

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

树

二叉排序树

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

平衡二叉排序树

从任何一个节点出发，左右子树深度之差的绝对值不超过 1。
左右子树仍然为平衡二叉树。
旋转二叉树恢复平衡：
插入时，最多只需要两次旋转就会重新恢复平衡。
删除时，需要维护从被删节点到根节点这条路径上所有节点的平衡性，时间复杂度 O(logN)。

红黑（排序）树

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

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

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

跳表

常用算法

穷举算法
递归算法
贪心算法
动态规划

网络通信协议

WEB 请求通信历程

网络数据包格式

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

链路层

链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制。

链路层会定义帧的大小，这个大小也被称为最大传输单元。像 HTTP 要在传输的数据上添加一个 HTTP 头一样，数据链路层也会将封装好的帧添加一个帧头，帧头里记录的一个重要信息就是发送者和接受者的 MAC 地址。MAC 地址是网卡的设备标识符，是唯一的，数据帧通过这个信息确保数据送达到正确的目标机器。