性能优化 - 第八周
算法
复杂度
时间复杂度: 算法执行语句的次数
空间复杂度: 算法运行过程中临时占用的存储空间大小
样例
NP问题
P问题
NP问题
NP-hard
递归算法
时间复杂度: n * log(n)
空间复杂度: log(n)
贪心算法
迪杰斯特拉算法(最快路径)
动态规划算法
将所求的目标值在几个维度展开,将大问题拆解为若干小问题,小问题的最优解,寻找大问题的最优解。
遗传算法
基因编码与染色体(随机)
适应函数与控制参数
选择算法
交叉遗传/可变异 (随机)
数据结构
数组
内存空间连续
存储数据类型相同
随机快速访问(依据下标访问)
链表
内存空间不连续
包含自身元素和其他地址指针
查询数据需要遍历,时间复杂度O(N)
增删时间复杂度O(1)
HASH表
通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
栈
后进先出
队列
先进先出
树
二叉树
排序二叉树
平衡二叉树
红黑树
跳表
类似可二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。
网络通信协议
web请求一次的网络通信历程
OSI七层模型和TCP/IP四层模型
网络数据包格式
tcp通信
连接:三次握手
关闭:四次挥手
HTTP 请求方法
GET:只读请求
HEAD:与GET相同,但仅返回响应头
POST:提交请求
PUT:上传请求
DELETE:删除URL标识的资源
TRACE:回显服务器的请求,用以测试或诊断
OPTIONS:请求服务器返回所有支持的HTTP请求方法
HTTP 响应状态
1xx消息: 请求已被服务器接收,继续处理
2xx成功:请求已成功被服务器接收
3xx重定向:需要后续操作才能完成这一请求
4xx请求错误:请求含有词法错误或者无法被执行
5xx服务器错误:服务器在处理某个正确请求时发生错误
HTTP 版本
HTTP1.0
短连接
无记录
HTTP1.1
持久连接
缓存处理
带宽优化及网络连接的使用
错误通知的管理
消息在网络中的发送
互联网地址的维护
安全性及完整性
HTTP2.0
多路复用
二进制分帧
首部压缩
服务端推送
阻塞与非阻塞
阻塞
如果请求数据结果不能立即获取,则等待
非阻塞
如果请求数据结果不能立即获取, 则返回错误码
同步
同一流程在同一线程中处理
异步
同一流程在不同线程中处理
select/poll
kernel内核就会轮询检查所有select/poll负责的文件描述符fd,当找到其中那个的数据准备好了文件描述符,会返回给select/poll,select/poll通知系统调用,将数据从kernel内核复制到进程缓冲区(用户空间)。
select的几大缺点:
(1)每次调用select,都需要把fd集合从用户态拷贝到内核态,这个开销在fd很多时会很大
(2)同时每次调用select都需要在内核遍历传递进来的所有fd,这个开销在fd很多时也很大
(3)select支持的文件描述符数量太小了,默认是1024
epoll
epoll与select/poll流程相反,无需主动查询,由中断产生假如列表中
数据库架构原理与性能优化
preparestatement预编译
效率高
防止SQL注入
数据库架构
索引
聚簇索引(B+树)
非聚簇索引(B+树)
删除无用索引,避免增加增删开销
使用更小的数据类型创建索引
事务ACID
Atomicity 原子性
一个事务必须被视为一个不可分割的最小工作单元。
Consistency 一致性
数据库总是从一个一致性的状态转换到另外一个一致性的状态。
Isolation 隔离性
通常来说,一个事务所做的修改在最终提交之前,对其他事物是不可见的。
Durability 持久性
一旦事务提交,则其所做的修改就会永久保存到数据库中。
事务日志
进行事务操作是,先记录更新前的数据记录,在更新数据库中的记录。如果全成功,事务结束;如果失败,整个事务回滚到之前的状态。
LSN: 一个按时间顺序分配的唯一事务记录日志序列号
TransID: 产生操作的事务ID
PageID:被修改数据磁盘上的位置
PrevLSN:同一个事务产生的上一条日志记录的指针
UNDO:取消本次操作的方法,按照此方法回滚
REDO:重复本次操作的方法
版权声明: 本文为 InfoQ 作者【X﹏X】的原创文章。
原文链接:【http://xie.infoq.cn/article/b03f71f647c56a785a2ae82a6】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论