写点什么

性能优化(二)

用户头像
wing
关注
发布于: 2020 年 11 月 15 日

本周是跟随李智慧老师学习架构师训练营的第八周,现将本周主要学习内容总结如下:

文件控制块:文件系统将硬盘空间划分为一个一个块,一个文件占用多个块,通过一个文件控制块系统FCB记录每个文件占用的块。一个块默认大小是4K。

inode:记录文件大小、创建时间,所有者等信息,以及对应的文件数据块硬盘地址索引。inode是固定结构,能够记录的数据块索引也是固定的只能是15个。一个inode最多能存储的数据块是:12+256+256*256+256*256*256,故一个文件大小最大为70G。

RAID:独立硬盘冗余阵列。

RAID0:将一个文件分成多个部分存储在不同的硬盘上

RAID1:将一个文件存储在两个互为备份的硬盘上

RAID10:RAID0和RAID1的组合

RAID5:N块磁盘,将一个文件分成N-1份,一块磁盘存储校验信息(螺旋式记录校验信息),其余磁盘存储文件信息。通过异或的方式获取丢失信息。常用方式

RAID6:与RAID5相似,用两块磁盘备份记录校验信息



时间复杂度:粗略估计一个算法的执行效率

空间复杂度:程序运行占用的临时空间

常见的时间复杂度:

O(1):map,set

O(n):数组遍历,链表遍历

O(logn):二分查找

O(n*logn):快速排序,归并排序,堆排序

O(n^2):冒泡排序,插入排序,选择排序

O(n!)、O(2^n):非多项式,随数据量增大算法复杂度会急剧升高

常见数据结构:

数组

链表

hash

跳表

trie树

并查集

红黑树特点:

1.所有的节点要么是黑色要么是红色

2.叶子节点是黑色并且是空节点

3.根节点是黑色

4.红色节点不能相邻

5.从任一节点到它的叶子节点经过的黑色节点的数目相同

常用算法:

穷举

递归

贪心:改进版:迪杰斯特拉算法

动态规划

启发式搜索

剪枝

分治

遗传算法:不一定能得到最优解,效率高

HTTP响应的5中状态:

1XX消息:请求已被服务器接收,继续处理

2XX成功:请求已成功被服务器接收、理解、并接受

3XX重定向:需要后续操作才能完成这次操作

4xx请求错误:请求含有语法错误或无法被执行

5XX服务器错误:服务器处理某个请求时发生错误

HTTP版本:

1.0:1996年发布,每次建立一个新的TCP连接

1.1:长连接,但每个连接任意时间点只能处理一个请求

2.0:引入HTTP流概念,允许复用TCP连接,但请求是有顺序的,有可能出现队头阻塞现象

3.0:QUIC,基于UDP

BIO

NIO:多路复用,没有请求进来时,select会阻塞



有两个单向链表(链表长度分别为m,n),这两个单向链表有可能在某个元素合并,也

可能不合并,如下图所示的这样。现在给定两个链表的头指针,在不修改链表的情况下,

如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的x 元

素。

请用代码(或伪代码)描述算法,并给出时间复杂度。



时间复杂度:max(O(m),O(n))

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        while(headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while(headB != null) {
            if(set.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}



用户头像

wing

关注

还未添加个人签名 2018.05.13 加入

还未添加个人简介

评论

发布
暂无评论
性能优化(二)