第八周作业

用户头像
田振宇
关注
发布于: 2020 年 07 月 28 日



作业一:

以下两题,至少完成一道

1、有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

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



Set keySet = new HashSet();

while(true) {

if(m==null && n==null) {

return null;

}



if(m!=null && (m= m -> next) != null) {

if(ketSet.contains(m)) {

return m;

}

keySet.add(m);

}



if(n!=null && (n= n -> next) != null) {

if(ketSet.contains(n)) {

return n;

}

keySet.add(n);

}

}



时间复杂度是length(m+n),空间复杂度是length(m+n)



2、请画出 DataNode 服务器节点宕机的时候,HDFS 的处理过程时序图。



作业二:

根据当周学习情况,完成一篇学习总结



时间复杂度与空间复杂度

NP问题、P、NP-hard、NP完全问题



数组:内存连续、数据类型相同、随机快速读写、根据数组下标访问数据时间复杂度为O(1)

链表:可以使用零散的内存空间存储数据,查找复杂度是O(N),增删数据性能好

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

hash表:hash表key冲突,使用链表存储数据



栈:后进先出

队列:先进先出

用队列搜索好友关系中最有钱的人、用队列搜索最短路径



树:二叉排序树、不平衡的二叉(排序)树、平衡二叉(排序)树、红黑(排序)树

红黑树VS平衡二叉树:大量增删情况下,红黑树性能更高,查找效率稍微差一些

跳表



常用算法:穷举算法、递归算法、贪心算法、迪杰斯特拉算法(改进贪心算法)、动态规划、遗传算法



OSI七层模型:物理层、数据链路层、网络层、传输层、会话层、表示层、应用层

TCP/IP四层模型:网络访问层、网络互联层、传输层、应用层



网络数据包格式:链路层协议头(mac地址) -> IP协议头(IP) -> TCP协议头(端口) -> HTTP协议头(方法、path)



TCP协议:面向连接的、可靠的、基于字节流的传输层协议

使用序号,对收到的TCP报文进行排序和检测重复的数据

无错传输:使用校验和检测报文段的错误

使用确认和计时器来检测和纠正丢包或者延时

流量控制,避免主机分组发送过快而使接收方来不及完全收下

拥塞控制,发送方根据网络承载情况控制分组的发送量,以获得高性能同时避免拥塞崩溃

丢失包的重传



TCP3次握手:

1、App先发送SYN=1,Seq=X的报文,表示请求建立连接,X是一个随机数;

2、服务器收到这个报文后,应答SYN=1,ACK=X+1,Seq=Y的报文,表示同意建立连接;

3、App收到这个报文后,检查ACK的值为自己发送的Seq值+1,确认建立连接,并发送ACK=Y+1的报文给服务器;服务器收到这个报文后检查ACK值为自己发送Seq值+1,确认建立连接。至此,App和服务器建立起TCP连接,就可以进行数据传输了



TCP关闭连接4次挥手:

1、客户端向服务端发送一个FIN,请求关闭数据传输。

2、当服务器接收到客户端的FIN时,向客户端发送一个ACK,其中ACK的值等于FIN+Seq。

3、然后服务器向客户端发送一个FIN,告诉客户端应用程序关闭。

4、当客户端收到服务端的FIN时,回复一个ACK给服务器端。其中ACK的值等于FIN+Seq。



HTPP的七种方法和五种状态



HTTP协议版本:

HTTP/1.0,客户端请求到资源后会关闭连接,频繁三次握手、四次挥手很耗性能

HTTP/1.1,默认启用长连接模式,客户端可以使用一个长连接顺序发送多个请求。引入了管道机制,客户端可以不用等上一个请求的响应结果就可以发送下一个请求,但是服务端也是按照客户端发送顺序进行响应的,可以理解为半双工模式

HTTP/2.0,依然遵循请求响应模式,但客户端发送多个请求和服务端给出多个响应的顺序不受限制,这样既避免了队头阻塞,又能更快获取响应



客户端与服务端通过socket进行通信,一个连接一个socket,一个socket可以采用一个线程或者线程池进行业务处理



BIO: 进行I/O操作时,用户线程会一致阻塞,知道读操作或写操作完成

NIO(非阻塞IO):I/O操作立即返回,发起线程不会阻塞等待

系统IO复用方式:select、poll、epoll

epoll性能最好,poll其次



数据库preppareStatement预编译,提前生产查询计划,性能更好,还能防止sql注入

数据库连接池:初始化的时候建立一些数据库连接放在连接池里,处理sql的时候就不需要花时间建立连接了

数据库语法分析器、语义分析与优化器、执行计划

B-树与B+树

聚簇索引

添加索引可以优化查询性能,但是也不要盲目添加索引,添加索引的alter会消耗较长的时间,阻塞DML

数据库事务:原子性、隔离性、持久性、一致性



用户头像

田振宇

关注

还未添加个人签名 2018.05.10 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
作业请添加“极客大学架构师训练营”标签,便于分类
2020 年 07 月 29 日 17:51
回复
没有更多了
第八周作业