数据结构算法及分布式文件实践

发布于: 2020 年 07 月 28 日



Author: Jessie

Date:  2020/7/28   V1.0



两条单向链表是否合并的查找算法



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

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

 



方法一:

 

采用暴力的方法,遍历两个链表,判断第一个链表的每个结点是否在第二个链表中,时间复杂度为O(m*n),耗时很大。

 

方法二:

 

如果两个链表合并,那么最后的节点的地址一定相同。时间复杂度为O(m+n)。

 

伪代码实现:

 

node findNode(node A, node B)


   node p1,p2;

   p1=A;

   p2=B;

 

   if(p1==null || p2==null) {

       return null;

   }
 

   //查找链表2结束节点

   int m=0;

   while(p1.next!=null){

        p1 = p1.next;

        m++;

    }

 

//查找链表2结束节点

  int n=0;

   while(p2.next!=null){

        p2 = p2.next;

        n++;

    }

 

 if(p1!=p2)

return null;

 

  //判断交叉点

  int diff = abs( m-n);

  if(m>n){

   p1=A;

   p2=B;

  } else{

p1=B;

p2= A;

  }

  

  for(int i=0;i<diff;i++){

    p1=p1.next;

  }

  while( p1!=p2){

p1= p1.next;

p2=p2.next;

  }

  return p1;

}




DataNode服务节点宕机,HDFS处理时序图



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



HDFS写文件具体流程如下:

1.客户端端首先通过DistributedFileSystem对象的create方法创建一个FSDataOutputStream(输出流)对象;

2.客户端通过DistributedFileSystem对象向NameNode发起一次RPC调用,在HDFS的Namespace中创建一个文件条目;

3.通过FSDataOutputStream对象,向DataNode写入数据,数据首先被写入FSDataOutputStream对象内部的Buffer中,然后数据被分割成一个个Packet数据包;

4.以Packet最小单位,基于Socket连接发送到按特定算法选择的HDFS集群中一组DataNode中的一个节点上,在这组DataNode组成的Pipeline(数据量管道)上依次传输Packet;

5.这组DataNode组成的Pipeline反方向上,发送ack,最终由Pipeline中第一个DataNode节点将Pipeline ack发送给客户端;

6.完成向文件写入数据,客户端在FSDataOutputStream对象上调用close方法,关闭流;

7.调用DistributedFileSystem对象的complete方法,通知NameNode文件写入成功。

 



判断失效:





发现DataNode宕机后,NameNode处理时序图,简化表示过程如下:





参考文献:

1 . 对于有环的链表查找是否有合并点,还可以参考如下链接:

 

https://blog.csdn.net/jiary5201314/article/details/50990349?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase

  1. 

https://www.cnblogs.com/testling/p/11581179.html



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

还未添加个人签名 2018.08.21 加入

码过代码、做过产品;擅长码字、演讲、认真做事之人。

评论

发布
暂无评论
数据结构算法及分布式文件实践