写点什么

第八周学习性能优化 2 总结

用户头像
三板斧
关注
发布于: 2020 年 11 月 13 日

数据结构与算法

时间复杂度与空间复杂度

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



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



NP问题

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

  • NP:能在多项式时间复杂度内验证答案正确与否的问题(例如数独)

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

  • NP 完全问题:是一个 NP-hard 问题,也是一个 NP 问题



数组

  • 连续的内存空间

  • 存放相同类型的数据

  • 随机快速读写,根据下标访问,时间复杂度 O(1)



链表

  • 可以使用零散的内存空间

  • 每个元素包括指向下一个元素的指针

  • 不能随机访问,需要顺序访问,时间复杂度 O(N)

  • 增删数据比数组更容易,不需要搬动原有数据

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



Hash 表

  • 快速访问

  • 快速增删

  • key 可能发生冲突



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

  • 在线性表的基础加上增删操作的限制条件:后进先出

  • 应用场景:函数调用中的参数与局部变量



队列

  • 也是操作受限的线性表:先进先出

  • 应用场景:生产者、消费者;搜索最短路径



二叉排序树

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

  • 右子树上所有结点的值均大于或等于它的根结点的值

  • 左、右子树也分别为二叉排序树



平衡二叉(排序)树

  • 从任何一个节点出发,左右子树高度相差不超过1

  • 左右子树也是平衡二叉树

  • 插入时,最多只需要两次旋转就会重新恢复平衡

  • 删除时,需要维护从被删节点到根节点这条路径上所有节点的平衡性,时间复杂度 O(logN)



红黑(排序)树

  • 每个节点为两种颜色之一:红或黑

  • 根节点为黑色

  • 每个叶子节点 (NIL) 都是黑色的空节点

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

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

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

  • 最多只需3次旋转就会重新达到红黑平衡,时间复杂度 O(1)

  • 在大量增删的情况下,效率比平衡二叉树高

  • 平衡性不如平衡二叉树,查找效率比平衡二叉树低一些



跳表

  • 降低已排序链表的查找时间复杂度(每次跳过更多的元素)

  • 空间复杂度更高(空间换时间)



算法

  • 穷举算法

  • 递归算法

  • 贪心算法

  • 动态规划

  • 遗传算法



网络通讯协议

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



非阻塞网络 I/O

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

  • 系统 I/O 复用方式:select, poll, epoll



数据库架构原理与性能优化

  • PrepareStatement 预编译,提前生成执行计划,效率更好,并且可以防止 SQL 注入攻击

  • 数据库连接池,减少反复建立连接的开销

  • 聚簇索引:记录和索引存储在一起

  • 非聚簇索引:叶子节点不记录数据行记录,而是主键。通过非聚簇索引找到主键,再通过主键索引找到行记录,该过程也称作回表。

  • 添加必要的索引优化 SQL 查询性能

  • 不要盲目添加索引,避免不必要的增删开销

  • 事务日志,用于回滚(UNDO Log)或崩溃后恢复(REDO Log)



总结

性能优化是个很大的话题

  • 首先要有判断是否达到优化目标的性能指标

  • 围绕性能指标选择技术方案时,需要综合权衡。不同的方案有不同的折中取舍,而这些取舍有时不是技术团队能决定的,技术选型和架构决策需要依赖业务规划甚至企业的战略规划,离开业务发展的支撑和驱动,技术走不远,甚至会迷路

  • 前沿技术是由前沿业务催生的

  • 新技术的出现又会驱动企业开展新的业务



因此架构师不仅仅要技术全面,还要有业务发展的前瞻性。



用户头像

三板斧

关注

程咬金的三板斧 2018.10.08 加入

1、原理 2、实践 3、总结

评论

发布
暂无评论
第八周学习性能优化 2 总结