性能优化 - 第八周

用户头像
X﹏X
关注
发布于: 2020 年 07 月 29 日

算法

复杂度

  • 时间复杂度: 算法执行语句的次数

  • 空间复杂度: 算法运行过程中临时占用的存储空间大小

  • 样例



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:重复本次操作的方法



发布于: 2020 年 07 月 29 日 阅读数: 4
用户头像

X﹏X

关注

还未添加个人签名 2018.04.25 加入

还未添加个人简介

评论

发布
暂无评论
性能优化 - 第八周