性能优化总结二
文件与硬盘 I/O：如何把硬盘的读写速度提高十万倍？
B+树
优点：索引树，每次加载一磁盘块，通过二分查找缺点数据位置。每个磁盘块可以存储大量数据，由于是 n 叉树，可以保证用较短的树的高度（一般不会超过 4），存储几千万数据。
缺点：数据可能分散在不同索引块，如果机械硬盘，需要引动磁头到指定区域。
LSM 树
文件控制块
文件系统将硬盘空间以块为单位进行划分，每个文件占据若干个块，然后再通过一个文件控制块 FCB 记录每个文件占据的硬盘数据块。
Linux iNode 文件控制块
RAID 独立硬盘冗余阵列
把相同的数据存储在多个硬盘的不同的地方的方法。通过把数据放在多个硬盘上，输入输出操作能以平衡的方式交叠，改良性能。因为多个硬盘增加了平均故障间隔时间（MTBF），储存冗余数据也增加了容错。
分布式文件系统 HDFS
Linux 文件控制块大小：4K
HDFS 文件控制块大小：64M
数据结构与 hash 表原理分析
时间复杂度与空间复杂度
时间复杂度
l 算法执行语句的次数
l O(2^n)表示对 n 数据处理需要进行 2^n 次计算
空间复杂度
l 一个算法在运行过程临时占用存储空间大小的量度。
l O(n)表示存储 n 个数据。
NP 问题
N 问题：能在多项式时间复杂度内解决的问题。
NP 问题：能在多项式时间复杂度内验证答案正确与否的问题。
数组
l 创建数组必须要内存中一块连续的空间。
l 数组中必须存放相同的数据类型。
l 能快速随机读写数组，时间复杂度 O(1)
l 增删元素时间复杂度 O(n)。
链表
l 使用零散的内存空间存储数据。
l 链表中每个数据元素都必须包含指向下一个数据元素内存地址指针。
l 如果想找一个元素，必须遍历链表，时间复杂度 O(N)。
l 增加删除一个元素时间复杂度 O(1)。
Hash 表
栈
l 数组和链表都被称为线性表。
l 栈就是在线性表的基础上加了操作限制条件：后进先出。
线程调用栈
队列
l 队列也是在线性表的基础上加了操作限制条件：先进先出。
典型应用场景：
l 生产消费者。
l 阻塞等待的线程被放入队列。
l 用队列搜索好友中关系最近的有钱人。
l 队列搜索最短路径。
红黑树原理与性能特性
二叉排序树
l 左子树上所有节点的值均小于等于它根节点上的值。
l 右子树上所有节点的值均大于或等于它根节点上的值。
l 左右子树分别是二叉排序树。
l 时间复杂度 O(logn)
问题：由于数据分布不均衡，导致不平衡二叉排序树出现。
平衡二叉排序树
从任何一个节点出发，左右子树深度之差的绝对值不超 1。
左右子树为平衡二叉树。
旋转二叉树恢复平衡
插入时最多旋转 2 次就会重新恢复平衡。
删除时需要维护从被删节点到根节点这条路径上所有节点的平衡性，时间复杂度 O(logN)。
红黑排序树
l 每个节点只有 2 种颜色：红色和黑色。
l 根节点是黑色。
l 每个叶子节点 NIL 都是黑色的空节点。
l 从根节点到叶子节点不会出现 2 个连续的红色节点。
l 从任何一个节点出发，到叶子节点，这个路径上都有相同数目的黑色节点。
红黑树 VS 平衡二叉树
l 红黑树最多只需 3 次旋转就会重新达到红黑平衡，时间复杂度 O(1)。
l 在大量增删情况下，红黑树效率更高。
l 红黑树的平衡性不如平衡二叉树，查找效率更差些。
跳表
经典算法
递归算法（快速排序）
时间复杂度 n*log(n)
贪心算法
在对问题求解时，总是做出当前看来是最好的选择。也就是，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
背包问题：只有满足条件，就认为是局部最优解，但不是全局最优解。
贪心算法改进-迪杰斯特拉算法（最快路径）
l 找出“最便宜”的节点，即在最短时间内到达的节点。
l 找出该节点邻居开销，检查是否有前往它们的更短路径，如果有，则更新。
l 重复上述过程，直到对图中每个节点都这样做了。
l 计算最短路径。
动态规划算法解决背包问题
通过找到合适角度，将所求解目标值在某几个维度展开，将一个大问题拆分成若干个小问题，从小问题最优解，寻找大问题最优解。
遗传算法解决背包问题
Generic Algorithm:GA，是模拟达尔文进化论的自然选择和遗传学机理的生物进化过程的计算机模型，是一种通过模拟自然进化过程搜索最优解的方法。
遗传算法是一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体设定、适应度函数设计、遗传操作设计、控制参数设定五个要素组成了遗传算法核心内容。
物品
重量
价值
1
10
15
2
15
25
3
20
35
4
25
45
5
30
55
6
35
65
基因编码和染色体
物品基因
物品 1
物品 2
物品 3
物品 4
物品 5
物品 6
染色体
1
1
1
1
1
1
111111
适应函数和控制参数
选择适应度函数：商品总价值
100100 = 15+45 = 60
010101 = 25+45+65 = 135
101011 = 15+35+55+65 = 170
选择控制参数：商品总重量
100100 = 10+25 = 35
010101 = 15+25+35 = 75
101011 = 10+20+30+35 = 95
选择算法
l 轮盘赌选择
l 随机竞争选择
l 均匀排序
交叉遗传
染色体
交叉点位置
交叉结果
101011
3
101101
010101
3
010011
染色体
交叉点位置
交叉结果
101011
4
101001
010101
4
010111
循环迭代，如果连续几代遗传都没有出现更强的染色体（价值总和更大），那么算法收敛，当前最大价值的染色体为最终解。
有时候会在遗传过程中进行基因突变，得到基因突变染色体。
遗传算法得到的不是最优解
遗传算法过程如下图
网络通信基本原理和性能优化
OSI 七层模型和 TCP/IP 四层模型
网络数据包格式
数据链路层负载均衡
详见：技术选型总结一，负载均衡架构
IP 负载均衡
详见：技术选型总结一，负载均衡架构
传输层（TCP 协议）
IP 协议是一个不可靠通信协议，不会建立稳定的通信链路，不会确保数据一定到达。要保证通信稳定可靠，需要传输层协议 TCP。
TCP 协议是一种面向链接的、可靠的、基于字节流的传输层协议。TCP 作为比较基础的通信协议，有很多机制保证 TCP 协议的可靠性和稳定性：
l 使用序号，对收到的报文段进行排序和检测重复数据。
l 无错传输，使用校验检测报文段错误。
l 使用确认和计时器检测和纠正丢包或者延时。
l 流量控制，避免主机分组发送的过快而使接收方来不及完全接收。
l 拥塞控制，发送方根据网络承载情况控制分组的发送量，已获得高性能的同时避免拥塞崩溃丢失包的重传。
TCP 建立连接的 3 次握手过程。
TCP 关闭连接的 4 次挥手过程。
应用层 HTTP 协议
HTTP 请求 7 种方法
l GET
l HEAD
l POST
l PUT
l DELETE
l TRACE
l OPTIONS
HTTP 响应的 5 中状态
1xx 消息—请求已被服务器接收，继续处理。
2xx 成功—请求已被服务器接收、理解并接受。
3xx 重定向—需要后续操作才能完成这一请求。
4xx 请求错误—请求含有词法错误或者无法被执行。
5xx 服务器错误—服务器正在处理某个正确请求时发生错误。
HTTP 协议版本
非阻塞网络 I/O
BIO:Blocking I/O
BIO：进行 I/O 操作时，用户线程会一直阻塞，直到读操作或者写操作完成。
Non-Blocking I/O
非阻塞 I/O:I/O 操作立即返回，发起线程不会阻塞等待。
非阻塞 read 操作：
l Socket 接收缓冲区有数据，读 n 个,不保证数据完整读取，可能需要多次读。
l Socket 接收缓冲区无数据，则返回失败。
非阻塞 write 操作：
l Socket 发送缓冲区满，则返回失败。
l Socket 发送缓冲区未满，写 n 个数据，不保证一次全部写入，可能需要多次写。
Socket 之 channel 通道建立过程
系统 I/O 复用方式：select、poll、epoll
Select
Select（poll）管理下 read 过程
Epoll 管理下的 read 过程
版权声明: 本文为 InfoQ 作者【Mars】的原创文章。
原文链接:【http://xie.infoq.cn/article/562498424f298d99d96d58bb5】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
还未添加个人签名 2018.06.12 加入
还未添加个人简介
评论