vericmore

vericmore 查看完整档案

上海编辑中国石油大学(华东)  |  计算机 编辑头条  |  后端开发 编辑 blog.itiwin.cn 编辑
编辑

web开发 php python golang js

个人动态

vericmore 关注了用户 · 10月31日

tyloafer @tyloafer

关注 64

vericmore 收藏了文章 · 10月10日

[LeetCode 142/287]PHP 快慢指针的进阶题

原文链接:何晓东 博客

环形链表 II

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

说明:不允许修改给定的链表。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...

解题思路 1

遍历链表,同时将每次的结果放到 map 中,首次遇到重复元素,则直接返回这个元素就行,代码和上一篇文章的类似。

解题思路 2

快慢指针求解:我们定义两个指针,一快一满。慢指针每次只移动一步,而快指针每次移动两步。初始时,慢指针在位置 head,而快指针在位置 head.next。这样一来,如果在移动的过程中,快指针反过来追上慢指针,就说明该链表为环形链表。否则快指针将到达链表尾部,该链表不为环形链表。

确定有环形之后,就是推理找到入环点:
我们使用两个指针,fastslow。它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置,而 fast 指针向后移动两个位置。如果链表中存在环,则 fast 指针最终将再次与 slow 指针在环中相遇。

如下图所示,设链表中环外部分的长度为 aa。slow 指针进入环后,又走了 bb 的距离与 fast 相遇。此时,fast 指针已经走完了环的 nn 圈,因此它走过的总距离为 a + n(b + c) + b = a + (n + 1)b + nc

示例图

根据题意,任意时刻,fast 指针走过的距离都为 slow 指针的 22 倍。因此,我们有

a + (n + 1)b + nc = 2(a+b) ⟹ a = c + (n − 1)(b + c)

有了 a = c + (n - 1)(b + c) 的等量关系,我们会发现:从相遇点到入环点的距离加上 n-1 圈的环长,恰好等于从链表头部到入环点的距离。

因此,当发现 slowfast 相遇时,我们再额外使用一个指针 ptr。起始,它指向链表头部;随后,它和 slow 每次向后移动一个位置。最终,它们会在入环点相遇。

作者:LeetCode-Solution
链接:https://leetcode-cn.com/probl...
来源:力扣(LeetCode)

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */

class Solution {
    /**
     * @param ListNode $head
     * @return ListNode
     */
    function detectCycle($head) {
        if($head == null || $head->next == null) return null;
        $fast = $head;
        $slow = $head;

        // 在相遇点跳出循环
        
        while ($fast != null && $fast->next != null) {
            $fast = $fast->next->next;
            $slow = $slow->next;
            if ($fast === $slow) {
                break;
            }
        }
        
        // 声明 ptr 指针,步长为 1 的向前走

        $ptr = $head;
        while ($ptr !== $slow) {
            $ptr = $ptr->next;
            $slow = $slow->next;
        }
        // ptr 即为入口

        return $ptr;
    }
}

类似的另外一题是:

寻找重复数

给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2

示例 2:

输入: [3,1,3,4,2]
输出: 3

说明:

不能更改原数组(假设数组是只读的)。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字,但它可能不止重复出现一次。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...

解题思路

和上面的快慢指针一样的,只是借助索引将数组想象成链表就可以。

代码
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findDuplicate($nums) {
        $slow = 0;
        $fast = 0;
        $slow = $nums[$slow];
        $fast = $nums[$nums[$fast]];
        while($slow != $fast){
            $slow = $nums[$slow];
            $fast = $nums[$nums[$fast]];
        }
        
        $pre1 = 0;
        $pre2 = $slow;
        while($pre1 != $pre2){
            $pre1 = $nums[$pre1];
            $pre2 = $nums[$pre2];
        }
        return $pre1;
    }
}

参考链接:

  1. 环形链表 Ⅱ 官方题解

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券

查看原文

vericmore 收藏了文章 · 10月9日

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

前言

虽然在大学的时候大家都学过网络协议 ,但是肯定感觉网络协议的知识点非常多 ,非常复杂。学的时候就浑浑噩噩,真正到了实践中更是糊里糊涂,一旦工作中遇到了网络问题,除了会简单地 ping 几下 ,基本没有什么解决问题的思路。 然而当拿起书来学习,或者看一些官方文档的时候,各种生僻的专业词汇马上扑面而来,每了解其中的一个词汇 ,都要看多 篇文章,读多本书,导致一篇即使很短的有关网络技术的文章也要几个星期才能看完。

这严重打击着大家的自信心,并且很容易让人在技术的海洋中迷失自我,从而产生“从人门到放弃”的冲动!

网络协议和变化万千的前沿技术不同,它的变化比较小,一旦掌握到一定程度,就会一直受益 技术变 很快,这 几年OpenStack、docker、Mesos、kubernetes、微服务、serverless、AIops等技术层出不穷,让大多数技术人员应接不暇,但是掌握了基础知识 后,反而发现很多技术看起来“轰轰烈烈”, 脱下外衣,其实本质还是操作系计算机网络、算法与数据结构、编译原理 、计算机组成与系统结构 。

如果基础打好了,最大的收益就是,在最新的技术出来以后,只要经过短时间的学习,就很容易上手,就能在新技术的滚滚浪潮中保持快速学习的能力。

既然网络协议既是基础,又绕不过去,还这么难,但是趟过去之后又不怎么变,收益越来越大,那为什么不写一文档,给大家一点可借鉴的经验,帮助大家尽快掌握网络协议呢?

那么,今天咱们就从目录、主要包括的内容和总结三部分给大家进行网络协议的拓展学习,希望大家能够喜欢!!

目录

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

主要内容

主要把本文内容分为九章来给大家介绍:

第1章通信协议概述.

1.1为什么要学习网络协议

1.2网络分层的真实含义,总结一下本节的内容,理解网络协议的工作模式,有以下两个小窍门。

  • 始终想象自己是一个处理网络包的程序:如何拿到网络包,如何根据规则进行处理,如何发出去。
  • 始终牢记一个原则:只要是在网络上跑的包,都是完整的。可以有下层没上层,绝对不可能有上层没下层。

1.3 ifconfig:熟悉又陌生的命令行,通过本节的学习希望你能记住以下的知识点,后面都能用得上:

  • I地址有定位功能,MAC地址类似身份证号,无定位功能。
  • CIDR可以用来判断是不是本地地址。
  • IP地址分公网IP地址和私网IP地址。后面的章节中会谈到“出国门”,就与此有关。

1.4 DHCP与PXE:IP地址是怎么来的,又是怎么没的,本节内容总结如下:

  • DHCP主要租给客户端IP地址,这个过程和租房很像,要商谈、签约、续租,广播还不能“抢单”。
  • DHCP会给客户端推荐“装修队”PXE来安装操作系统,这在云计算领域大有用处。

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

第2章从二层到三层.

2.1从物理层到MAC层:如何在宿舍里自己组网玩联机游戏,本节有3个重点需要记住:

  • MAC层是用来解决多路访问的“堵车”问题的。
  • ARP是通过“吼”的方式来寻找目标MAC地址的,“吼”完之后会记住一段时间,这个叫作缓存。
  • 交换机是有MAC地址学习能力的,学会了它就能知道谁在哪里,不用广播了。

2.2交换机与VLAN:办公室太复杂,我要回学校,本节总结如下:

  • ·当交换机的数目越来越多时,会遭遇环路问题,让广播包迷路。这时就需要使用STP通过“比武论剑”的方式,将有环路的图变成没有环路的树,从而解决环路问题。
  • ·交换机数目过多会导致隔离问题。可以通过VLAN形成虚拟局域网,从而解决广播问题和安全问题。

2.3ICMP与ping:投石问路的侦察兵,本节内容总结如下:

  • ·ICMP 相当于网络世界的侦察兵。本节讲解了两种类型的ICMP报文,一种是主动探查的查询报文,一种异常报告的差错报文。
  • ping使用查询报文,Traceroute使用差错报文。

2.4世界这么大,我想出网关:欧洲十国游与玄奘西行,本节总结如下:

  • ·如果离开局域网,就需要经过网关。
  • ·路由器是一个三层设备,里面有如何寻找下一跳的规则。
  • ·经过路由器之后MAC头要变,如果I地址不变,相当于不换护照的“欧洲十国游”,如果IP地址改变,相当于换护照的“玄奘西行”。

2.5路由协议:“西出网关无故人""敢问路在何方”,本节总结如下:

  • 路由分静态路由和动态路由,静态路由可以配置复杂的策略路由,控制转发策略。
  • 动态路由有两种主流协议,距离矢量路由协议和链路状态路由协议。分别对应BGP和OSPF 这两个实现。

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

第3章重要的传输层.

3.1 UDP:虽然简单但是可以定制化,本节总结如下:

  • 如果将TCP比作成熟的社会人,UDP则是头脑简单的小朋友。TCP复杂,UDP简单。TCP维护连接,UDP谁都相信。TCP知进退,UDP愣头青一个,勇往直前。
  • ·UDP虽然简单,但它有简单的用法。它可以用在环境简单、需要多播、应用层自己控制传输的地方,例如DHCP、VXLAN、QUIC等。

3.2 TCP(上):虽然复杂,使用起来却轻松,本节总结如下:

  • · TCP头很复杂,但是主要关注五个方面:顺序问题、丢包问题、连接维护、流量控制,以及拥塞控制。
  • 连接的建立要经过三次握手,断开要经过四次挥手。

3.3 TCP (下):西行必定多妖孽,恒心智慧消磨难,总结如下:

  • 顺序问题、丢包问题、流量控制都是通过滑动窗口来解决的,滑动窗口其实就相当于领导和下属的工作备忘录,布置过的工作要有编号,干完了有反馈,活儿不能派太多,也不能太少。
  • 拥塞控制是通过拥塞窗口来解决的,相当于往管道里面倒水,快了容易溢出,慢了浪费带宽,要摸着石头过河,找到最优值。

3.4 socket: Talk is cheap, show me the code ,本节总结如下:

  • 你需要记住在基于TCP和UDP的socket程序的函数调用过程中,客户端和服务端都需要调用哪些函数。
  • 写一个能够支撑大量连接的高并发的服务端不容易,需要多进程、多线程,而 epoll能解决C10K问题。

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

第4章常用的应用层.

4.1 HTTP:看个新闻原来这么麻烦,本节总结如下:

  • HTTP很常用,也很复杂,重点记住GET、POST、PUT、DELETE这几个方法,以及重要的首部字段。
  • HTTP2.0通过头压缩、分帧、二进制编码、多路复用等技术提升性能。
  • QUIC协议通过基于UDP自定义的连接、重传、多路复用、流量控制等机制进一步提升性能。

4.2 HTTPS:点外卖的过程原来这么复杂,本节总结如下:

  • 加密分对称加密和非对称加密。对称加密效率高,但是解决不了密钥传输问题;非对称加密可以解决这个问题,但是效率低。
  • 非对称加密需要通过证书和权威机构来验证公钥的合法性。
  • HTTPS是综合了对称加密和非对称加密的HTTP。既保证传输安全,也保证传输效率。

4.3流媒体协议:如何在直播里看到帅哥美女,本节总结如下:

  • 编码两大流派达成了一致,都是通过关于时间、空间的各种算法来压缩数据的。
  • 压缩好的数据,为了方便传输会组成一系列NALU,按照帧和片依次排列。
  • 排列好的NALU在网络传输时,要按照RTMP包的格式进行包装,RTMP包会拆分成块进行传输。
  • 推送到流媒体服务器的视频流经过转码和分发,可以被客户端通过RTMP拉取,然后组合为NALU,解码成视频格式进行播放。

4.4 P2P协议:下载电影,分布式协议速度快,本节总结如下:

  • 下载一个文件可以使用HTTP或FTP,这两种协议都使用集中下载的方式,而P2P则换了一种思路,采取去中心化下载的方式。
  • P2P也有两种下载方式,一种是依赖于tracker服务器,即元数据集中,文件数据分散;另一种基于分布式哈希算法,元数据和文件数据全部分散。

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

第5章陌生的数据中心.

5.1 DNS:网络世界的地址簿,本节总结如下:

  • DNS是网络世界的地址簿,可以通过域名查询地址,由于DNS服务器是按照树状结构组织的,因而域名查找使用的是递归的方法,并通过缓存的方式增强性能。
  • 域名和IP地址相互映射的过程给了应用基于域名做负载均衡的机会,可以实现简单的负载均衡,也可以根据地址和运营商实现全局负载均衡。

5.2 HTTPDNS:网络世界的地址簿也会指错路,本节需要记住以下两个重点:

  • ·传统的DNS服务器有很多问题,例如解析慢、更新不及时。因为缓存、转发NAT问题导致客户端误会自己所在的位置和所属的运营商,从而影响流量的调度。
  • ·HTTPDNS服务器通过客户端SDK,服务端通过HTTP直接调用解析DNS服务器的方式,绕过了传统DNS服务器的缺点,实现了智能调度。

5.3 CDN:你去小卖部取过快递吗,本节需记住以下两个重点:

  • CDN和电商系统的分布式仓储系统-样,分为中心节点、区域节点、边缘节点,将数据缓存在离用户最近的位置。
  • CDN最擅长的是缓存静态数据,除此之外还可以缓存流媒体数据,这时要注意使用防盗链。CDN也支持动态数据缓存,可用模式有两种:一种是边缘计算的生鲜超市模式,另一种 是链路优化的冷链运输模式。

5.4数据中心:我是开发商,自己拿地盖别墅,本节需要记住以下3个重点:

  • 数据中心分为三层。服务器连接到接入层,然后是汇聚层,接着是核心层,最外面是边界路由器和安全设备。
  • 数据中心的所有链路都要高可用。服务器可以绑定网卡,交换机可以堆叠,三层设备可以通过等价路由,二层设备可以通过TRILL协议实现高可用。
  • 随着云和大数据的发展,东西流量相较于南北流量更加重要,因而演进出叶脊网络结构。

5.5 VPN:朝中有人好做官,本节总结如下:

  • VPN可以将一个机构的多个数据中心通过隧道连接起来,让机构感觉在一个数据中心里面一样,如同自驾游通过琼州海峡。
  • 完全基于软件的IPsec VPN可以保证私密性、完整性、真实性,简单便宜,但是性能稍微差一些。
  • MPLS-VPN综合了I转发模式和ATM标签转发模式的优势,性能较好,但是需要从运营商处购买。

5.6移动网络:去巴塞罗那,手机也上不了“脸书”,本节总结如下:

  • 移动网络的发展历程从2G到3G,再到4G,功能逐渐从以打电话为主转变为以上网为主。
  • 请记住4G网络的结构,有eNodeB、MME、SGW、PGW等,分控制面协议和数据面协议,你可以对照这个结构,试着说出手机上网的流程。
  • 即便你在国外运营商的范围内上网,也要由国内运营商控制,因而也上不了“脸书”。

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

第6章云计算中的网络.

6.1云中网络:自己拿地成本高,购买公寓更灵活,本节总结如下:

  • 云计算的关键技术是虚拟化,这里我们重点关注的是虚拟网卡通过打开TUN/TAP字符设备的方式,将虚拟机内外连接起来。
  • 云中的网络重点关注四个方面:共享、隔离、互通、灵活。其中共享和互通有两种常用的方式,分别是桥接和NAT,隔离可以通过VLAN的方式来进行。

6.2软件定义网络:共享基础设施的小区物业管理办法,本节总结如下:

  • 用SDN 控制整个云里面的网络,就像小区保安从总控室管理整个物业是一样的,将控制面和数据面进行了分离。
  • Open vSwitch是一种开源的虚拟交换机的实现,它能对经过自己的网络包做任意修改,从而使得云对网络的控制十分灵活。
  • 将Open vSwitch引入云之后,可以使配置简单而灵活,并且可以解耦物理网络和虚拟网络。

6.3云中网络之安全:虽然不是土豪,也需要基本保障,本节总结如下:

  • 云中的安全策略的常用方式是使用iptables的规则,请记住它的5个链:PREROUTING、INPUT、FORWARD、OUTPUT、POSTROUTING。
  • iptables 的表分为4种: raw、mangle、nat、filter。其中安全策略主要在filter表中实现,而虚拟网络和物理网络地址的转换主要在nat表中实现。

6.4云中网络之QoS:室友疯狂下电影,我该怎么办,本节总结如下:

  • 云中的流量控制主要是通过队列进行的,排队规则分为两大类:无类别排队规则和基于类别的排队规则。
  • 在云中网络Open vSwitch中,主要使用HTB将总的带宽在一棵树上按照配置的比例进行分配,并且在一个分支不使用流量时,借给另外的分支,从而增强带宽利用率。

6.5云中网络之隔离GRE、VXLAN:虽然住一个小区,也要保护隐私,本节总结如下:

  • 要对不同用户的网络进行隔离,解决VLAN数目有限的问题,需要通过Overlay的方式,常使用的是GRE和VXLAN。
  • GRE是一种点对点的隧道模式,VXLAN是支撑组播的隧道模式,它们都要在某个隧道端口进行封装和解封装,实现跨物理机的互通。
  • Open vSwitch可以作为隧道端口,通过设置流表规则在虚拟机网络和物理机网络之间进行转换。

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

第7章容器技术中的网络.

7.1容器网络:来去自由的日子,不买公寓去合租,本节总结如下:

  • 容器是一种比虚拟机更加轻量级的隔离方式,主要通过namespace和 cgroup技术进行资源的隔离,namespace负责“看起来”隔离,cgroup负责“用起来”隔离。
  • 容器网络连接到物理网络的方式和虚拟机很像,通过桥接的方式可以实现一台物理机上容器的相互访问,如果要访问外网,最简单的方式还是通过NAT。

7.2容器网络之Flannel:每人一亩三分地.,本节总结如下:

  • 基于NAT的容器网络模型在微服务架构下有两个问题,一个是IP地址重叠,另一个是端口冲突,需要通过Overlay 网络保持跨节点的连通性。
  • Flannel是跨节点容器网络方案之一,它提供的Overlay方案主要有两种方式,一种是UDP在用户态封装,另一种是VXLAN在内核态封装,而VXLAN的性能更好一些。

7.3容器网络之Calico:为了高效说出善意的谎言,本节总结如下:

  • Calico推荐使用物理机作为路由器,这种模式没有虚拟化开销,性能比较高。
  • Calico的主要组件包括路由、iptables 的配置组件Felix、路由广播组件BGP Speaker,以及大规模场景下的BGP路由反射器。
  • 为解决跨网段的问题,Calico还有一种IPIP模式,即在两台机器之间打一个隧道,两台机器分别位于隧道两端,这样本来不是邻居的两台机器,因为隧道变成了相邻的机器。

7.4 RPC概述:远在天边,近在眼前,本节总结如下:

  • 远程调用看起来用socket编程就可以了,其实是很复杂的,要解决协议约定问题、传输协议问题和服务发现问题。
  • Bruce Jay Nelson的论文、早期ONC RPC框架,以及NFS的实现,给出了解决这三大问题的示范性实现,即协议约定要公用协议描述文件并通过这个文件生成Stub程序,RPC的传输一般需要一个状态机,同时需要另外一个进程专门做服务发现。

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

第8章微服务相关协议.

8.1基于XML的SOAP:不要说NBA,请说美国职业篮球联赛,本节总结如下:

  • 原来的二进制RPC有很多缺点:格式要求严格、修改过于复杂、不面向对象。于是产生了基于文本的调用方式——基于XML的SOAP。
  • SOAP的三大要素:协议约定用WSDL、传输协议用HTTP、服务发现用UDDL。

8.2基于JSON的RESTful接口协议:我不关心过程,请给我结果,本节总结如下。

  • SOAP过于复杂,而且设计是面向动作的,因而往往因为架构问题导致并发量上不去。
  • RESTful不仅仅是一个API,还是一种架构模式,主要面向资源提供无状态服务,有利于横向扩展应对高并发。

8.3二进制类RPC协议:还是叫NBA吧,总说全称多费劲,本节总结如下:

  • RESTful API对于接入层和Controller层之外的调用,已基本形成事实标准,但随着内部
  • 服务之间的调用越来越多,性能也越来越重要,于是Dubbo的RPC框架有了用武之地。
  • Dubbo通过注册中心解决服务发现问题,通过Hessian2序列化解决协议约定的问题,通过Netty解决网络传输的问题。

在更加复杂的微服务场景下,Spring Cloud的RESTful方式在内部调用时也会被考虑,重要的是JAR包的依赖和管理问题。

8.4跨语言类RPC协议:交流之前,双方先交换一下专业术语表,本节总结如下:

  • gRPC是一种二进制、性能好、跨语言、更灵活,同时可以进行服务治理的多快好省的
  • gRPC框架,唯一的不足就是要写协议文件。
  • gRPC 在序列化时使用Protocol Buffers,网络传输时使用HTTP 2.0,服务治理时可以使用基于Envoy的Service Mesh。

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

第9章网络协议知识串讲.

9.1 知识串讲:用"双*"的故事串起网络协议的碎片知识(上),

9.2 知识串讲:用"双*"的故事串起网络协议的碎片知识(中),

9.3 知识串讲:用"双*“的故事串起网络协议的碎片知识(下),

9.4 搭建—个网络实验环境:授人以鱼不如授人以渔,

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

这份【趣谈网络协议】文档共有435页,需要完整版的朋友,可以转发此文关注小编,关注小编公众号【Java烂猪皮】私信【666】来获取!!

当然,单单有文档看是远远不够的,还有视频和相匹配的课件进行学习提升,努力把计算机网络这一块儿给搞明白,相信一定会有不凡的人生!!

TCP/IP/网络IO学习视频

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

TCP/IP网络协议

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

网络IO

还有课件分享

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

IO课件

华为18级工程师三年心血终成趣谈网络协议文档(附大牛讲解)

TCP/IP课件

TCP/IP/IO网络通信视频和课件获取,转发关注小编,关注公众号【Java烂猪皮】私信【666】获取!

好了,今天就分享到这里了,希望大家能够好好学习,把计算机网络这一块儿给提升上来,也希望本文能够得到大家的喜欢!!
image

查看原文

vericmore 收藏了文章 · 10月9日

PHP 和 Go 实现环路链表检测

原文链接:何晓东 博客

环路链表检测

给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。
有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...

解题思路 1

遍历链表,同时将每次的结果放到 map 中,如果有元素重复出现,则是有环形链表

代码
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    visited := make(map[*ListNode]struct{}, 1)
    work := head

    for work != nil {
        _, ok := visited[work]
        if ok {
            return work
        } else {
            visited[work] = struct{}{}
        }
        work = work.Next
    }

    return nil
}
解题思路 2

快慢指针求解:我们定义两个指针,一快一满。慢指针每次只移动一步,而快指针每次移动两步。初始时,慢指针在位置 head,而快指针在位置 head.next。这样一来,如果在移动的过程中,快指针反过来追上慢指针,就说明该链表为环形链表。否则快指针将到达链表尾部,该链表不为环形链表。

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */

class Solution {
    /**
     * @param ListNode $head
     * @return Boolean
     */
    function hasCycle($head) {
        $fast = $head;
        $slow = $head;

        while ($fast != null && $fast->next != null) {
            $fast = $fast->next->next;
            $slow = $slow->next;
            if ($fast === $slow) {
                return true;
            }
        }
        return false;
    }
}

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券

查看原文

vericmore 收藏了文章 · 3月8日

头条面经-PHP/Golang

一面(约1h)

  1. 在面对未知的流量暴增,可以预先怎么处理
  2. 如何限流,限流算法,对于ddos攻击怎么处理
  3. PHP数组的底层实现
  4. 分布式事务
  5. RPC相对于传统的API调用的优点
  6. 服务调度中心的感知与动态上下线
  7. MySQL的索引,为什么是B+而不是平衡二叉树
  8. 索引查找在Linux的磁盘上是怎么操作的
  9. 聚簇索引相对于B+索引的优点
  10. 如何分析SQL执行慢的原因
  11. Redis连接时的connect与pconnect的区别
  12. Redis有哪些结构时间复杂度较高
  13. Redis hash的实现
  14. 算法题: 在1个10G大小的文件中,存储的都是int型的数据,如何在内存使用小于8M的情况下进行排序
  15. 设计题: 以微博为例,有1个亿的用户,同时用户之间有关注和粉丝,用户的关注和取关操作比较频繁,如何设计架构和API接口

二面(约1.5h)

二面主要以自己的项目为切入点,进一步考察你对项目中知识点的把握程度,我这里是以一个 自己撸的小项目 进程管理工具 为项目背景

  1. 守护进程是什么,怎么实现
  2. PHP是否适合做守护进程,为什么(内存管理这一块)
  3. PHP的垃圾回收机制
  4. 进程间通信方式
  5. 共享内存是怎么实现的
  6. 怎么查看Linux服务器的负载,及判断哪些操作引起的负载过高
  7. MySQL的IO过高怎么优化,分库分表及分区
  8. MySQL的索引结构,myisam的索引结构, innodb的索引结构,innodb为什么必须要有主键索引
  9. 添加索引,为什么可以减少io操作(磁盘页)
  10. nginx的负载均衡算法
  11. 算法题: 忘了
  12. 算法题:查找一个字符串中最长的无重复字串

上面是我基本还记得的一些题目,考察的力度相对比较深,所以,请选择一个自己比较熟悉的项目,因为面试官是会剖析到底层的

三面(约0.6h)

三面与二面的内容差不多,没有更深的问题,但是,需要注重细节,同时三面面试官有时间会放烟雾弹,坚定自己的立场就好

  1. 面试题: 在一个横向和纵向都是递增的有界二维坐标轴中,如何快速判断某个数是否存在于这个二维坐标中
  2. 面试题:设计一个定时任务管理器(从我同事那打听到的,我只有上面一个算法题)

总结

头条面试,算法是必考项,但是面试官都是让我给出思路,也没写多少行代码

涉猎范围一般,基本就是Redis MySQL ,Nginx比较少,可能配置简单吧

深度较深,很少人会去关注PHP的垃圾回收,何为垃圾,线程安全,array的HashTable实现这些内容, Redis Hash表等

分界线

需要内推的可以私我哈

查看原文

vericmore 关注了专栏 · 2019-09-24

Nginx源码分析

研读nginx源码

关注 791

vericmore 收藏了文章 · 2019-07-24

hyperf如何接入swoole enterprise

1.为什么要接入swoole enterprise

针对线上机器的监控、接口的调用情况、线上接口异常告警、线上耗时分析、线上调试等等,这应该是每个线上项目,都必须直面且要认真思考的问题。
本来想自己写的,但考虑到时间成本和系统复杂程度,一直在犹豫。这时正好看到swoole enterprise,发现swoole enterprise是一个非常好的解决方案。

呵呵··· 是不是有人以为我是这个项目的托?!其实我用的是 试用版 永久免费版(给力哦!!!),非付费用户。
给大家上几张图,目前线上已经稳定运行。

clipboard.png

clipboard.png

不截图了,打马赛克太麻烦了~~

2.那如何接入呢?

  • 这边必须说个小插曲哈:之前我在服务器安装swoole_plus.so拓展,怎么都不成功。最后通过联系swoole官网客服,并通过远程才解决。发现是自己的php版本错了(源码安装的都可以留意下),好尴尬~ 这里必须给客服点赞哈~~上图

clipboard.png

补充说下:我是服务器直接安装,没有使用docker环境。你可以先看下官网安装教程点击查看

a.服务器基础部署:php(nts版,不支持zts)【不知道到nts与zts的区别?这个不重要。知道如何安装即可。】、swoole4.4以上

clipboard.png

b.进入swoole enterprise申请试用,下载客户端包到服务器。

clipboard.png

clipboard.png

c.解压安装包后,运行deploy_env.sh,会安装基础组件和复制sdk至/opt/swoole下。

clipboard.png

d.复制对应php版本的swoole_plus7*.so至php的extensions文件下。不知道这个目录在哪里?没关系,看下面指令:

php -i|grep extension

clipboard.png

e.配置php.ini

extension=swoole_plus.so
apm.enable=1           #打开总开关
apm.sampling_rate=100  #采样率 例如:100%
# 手动埋点时再添加
apm.enable_memcheck=1  #开启内存泄漏检测 默认0 关闭

clipboard.png

f.回到自己的hyperf程序,安装hyperf/swoole-enterprise拓展,并添加全局中间件HttpServerMiddleware

i.最后重启服务,即可通过后台查看相关数据了。

ps.我感觉这个后台有几点确实很有用,第一点,可以看到每个接口的调用成功、失败情况和时长。我就通过这个后台,发现一个redis的auth问题。第二点,可以查看整个应用的调用链并能分析性能。第三点,可以直接分析线上接口性能。还有。。。 这是一个宝藏后台,可挖掘的还有很多哦~~

clipboard.png

clipboard.png

查看原文

vericmore 收藏了文章 · 2019-06-03

当我们在谈论高并发的时候究竟在谈什么?

什么是高并发?

高并发是互联网分布式系统架构的性能指标之一,它通常是指单位时间内系统能够同时处理的请求数,
简单点说,就是QPS(Queries per second)。

那么我们在谈论高并发的时候,究竟在谈些什么东西呢?

高并发究竟是什么?

这里先给出结论:
高并发的基本表现为单位时间内系统能够同时处理的请求数,
高并发的核心是对CPU资源的有效压榨

举个例子,如果我们开发了一个叫做MD5穷举的应用,每个请求都会携带一个md5加密字符串,最终系统穷举出所有的结果,并返回原始字符串。这个时候我们的应用场景或者说应用业务是属于CPU密集型而不是IO密集型。这个时候CPU一直在做有效计算,甚至可以把CPU利用率跑满,这时我们谈论高并发并没有任何意义。(当然,我们可以通过加机器也就是加CPU来提高并发能力,这个是一个正常猿都知道废话方案,谈论加机器没有什么意义,没有任何高并发是加机器解决不了,如果有,那说明你加的机器还不够多!🐶)

对于大多数互联网应用来说,CPU不是也不应该是系统的瓶颈,系统的大部分时间的状况都是CPU在等I/O (硬盘/内存/网络) 的读/写操作完成。

这个时候就可能有人会说,我看系统监控的时候,内存和网络都很正常,但是CPU利用率却跑满了这是为什么?

这是一个好问题,后文我会给出实际的例子,再次强调上文说的 '有效压榨' 这4个字,这4个字会围绕本文的全部内容!

控制变量法

万事万物都是互相联系的,当我们在谈论高并发的时候,系统的每个环节应该都是需要与之相匹配的。我们先来回顾一下一个经典C/S的HTTP请求流程。

clipboard.png

如图中的序号所示:
1 我们会经过DNS服务器的解析,请求到达负载均衡集群
2 负载均衡服务器会根据配置的规则,想请求分摊到服务层。服务层也是我们的业务核心层,这里可能也会有一些PRC、MQ的一些调用等等
3 再经过缓存层
4 最后持久化数据
5 返回数据给客户端

要达到高并发,我们需要 负载均衡、服务层、缓存层、持久层 都是高可用、高性能的,甚至在第5步,我们也可以通过 压缩静态文件、HTTP2推送静态文件、CDN来做优化,这里的每一层我们都可以写几本书来谈优化。

本文主要讨论服务层这一块,即图红线圈出来的那部分。不再考虑讲述数据库、缓存相关的影响。
高中的知识告诉我们,这个叫 控制变量法

再谈并发

  • 网络编程模型的演变历史

clipboard.png

并发问题一直是服务端编程中的重点和难点问题,为了优系统的并发量,从最初的Fork进程开始,到进程池/线程池,再到epoll事件驱动(Nginx、node.js反人类回调),再到协程。
从上中可以很明显的看出,整个演变的过程,就是对CPU有效性能压榨的过程。
什么?不明显?

  • 那我们再谈谈上下文切换

在谈论上下文切换之前,我们再明确两个名词的概念。
并行:两个事件同一时刻完成。
并发:两个事件在同一时间段内交替发生,从宏观上看,两个事件都发生了

线程是操作系统调度的最小单位,进程是资源分配的最小单位。由于CPU是串行的,因此对于单核CPU来说,同一时刻一定是只有一个线程在占用CPU资源的。因此,Linux作为一个多任务(进程)系统,会频繁的发生进程/线程切换。

在每个任务运行前,CPU都需要知道从哪里加载,从哪里运行,这些信息保存在CPU寄存器和操作系统的程序计数器里面,这两样东西就叫做 CPU上下文
进程是由内核来管理和调度的,进程的切换只能发生在内核态,因此 虚拟内存、栈、全局变量等用户空间的资源,以及内核堆栈、寄存器等内核空间的状态,就叫做 进程上下文
前面说过,线程是操作系统调度的最小单位。同时线程会共享父进程的虚拟内存和全局变量等资源,因此 父进程的资源加上线上自己的私有数据就叫做线程的上下文

对于线程的上下文切换来说,如果是同一进程的线程,因为有资源共享,所以会比多进程间的切换消耗更少的资源。

现在就更容易解释了,进程和线程的切换,会产生CPU上下文切换和进程/线程上下文的切换。而这些上下文切换,都是会消耗额外的CPU的资源的。

  • 进一步谈谈协程的上下文切换

那么协程就不需要上下文切换了吗?需要,但是不会产生CPU上下文切换进程/线程上下文的切换,因为这些切换都是在同一个线程中,即用户态中的切换,你甚至可以简单的理解为协程上下文之间的切换,就是移动了一下你程序里面的指针,CPU资源依旧属于当前线程。
需要深刻理解的,可以再深入看看Go的GMP模型
最终的效果就是协程进一步压榨了CPU的有效利用率

回到开始的那个问题

这个时候就可能有人会说,我看系统监控的时候,内存和网络都很正常,但是CPU利用率却跑满了这是为什么?

注意本篇文章在谈到CPU利用率的时候,一定会加上有效两字作为定语,CPU利用率跑满,很多时候其实是做了很多低效的计算。
以"世界上最好的语言"为例,典型PHP-FPM的CGI模式,每一个HTTP请求:
都会读取框架的数百个php文件,
都会重新建立/释放一遍MYSQL/REIDS/MQ连接,
都会重新动态解释编译执行PHP文件,
都会在不同的php-fpm进程直接不停的切换切换再切换。

php的这种CGI运行模式,根本上就决定了它在高并发上的灾难性表现

找到问题,往往比解决问题更难。当我们理解了当我们在谈论高并发究竟在谈什么 之后,我们会发现高并发和高性能并不是编程语言限制了你,限制你的只是你的思想。

找到问题,解决问题!当我们能有效压榨CPU性能之后,能达到什么样的效果?

下面我们看看 php+swoole的HTTP服务 与 Java高性能的异步框架netty的HTTP服务之间的性能差异对比。

性能对比前的准备

Swoole是一个为PHP用C和C++编写的基于事件的高性能异步&协程并行网络通信引擎
Netty是由JBOSS提供的一个java开源框架。 Netty提供异步的、事件驱动的网络应用程序框架和工具,用以快速开发高性能、高可靠性的网络服务器和客户端程序。
  • 单机能够达到的最大HTTP连接数是多少?

回忆一下计算机网络的相关知识,HTTP协议是应用层协议,在传输层,每个TCP连接建立之前都会进行三次握手。
每个TCP连接由 本地ip,本地端口,远端ip,远端端口,四个属性标识。
TCP协议报文头如下(图片来自维基百科):

clipboard.png

本地端口由16位组成,因此本地端口的最多数量为 2^16 = 65535个。
远端端口由16位组成,因此远端端口的最多数量为 2^16 = 65535个。
同时,在linux底层的网络编程模型中,每个TCP连接,操作系统都会维护一个File descriptor(fd)文件来与之对应,而fd的数量限制,可以由ulimit -n 命令查看和修改,测试之前我们可以执行命令: ulimit -n 65536修改这个限制为65535。

因此,在不考虑硬件资源限制的情况下,
本地的最大HTTP连接数为: 本地最大端口数65535 * 本地ip数1 = 65535 个。
远端的最大HTTP连接数为:远端最大端口数65535 * 远端(客户端)ip数+∞ = 无限制~~ 。
PS: 实际上操作系统会有一些保留端口占用,因此本地的连接数实际也是达不到理论值的。

性能对比

  • 测试资源

各一台docker容器,1G内存+2核CPU,如图所示:

clipboard.png

docker-compose编排如下:

# java8
version: "2.2"
services:
  java8:
    container_name: "java8"
    hostname: "java8"
    image: "java:8"
    volumes:
      - /home/cg/MyApp:/MyApp
    ports:
      - "5555:8080"
    environment:
      - TZ=Asia/Shanghai
    working_dir: /MyApp
    cpus: 2
    cpuset: 0,1

    mem_limit: 1024m
    memswap_limit: 1024m
    mem_reservation: 1024m
    tty: true
    
# php7-sw
version: "2.2"
services:
  php7-sw:
    container_name: "php7-sw"
    hostname: "php7-sw"
    image: "mileschou/swoole:7.1"
    volumes:
      - /home/cg/MyApp:/MyApp
    ports:
      - "5551:8080"
    environment:
      - TZ=Asia/Shanghai
    working_dir: /MyApp
    cpus: 2
    cpuset: 0,1

    mem_limit: 1024m
    memswap_limit: 1024m
    mem_reservation: 1024m
    tty: true    
  • php代码
<?php

use Swoole\Server;
use Swoole\Http\Response;

$http = new swoole_http_server("0.0.0.0", 8080);
$http->set([
    'worker_num' => 2
]);
$http->on("request", function ($request, Response $response) {
    //go(function () use ($response) {
        // Swoole\Coroutine::sleep(0.01);
        $response->end('Hello World');
    //});
});

$http->on("start", function (Server $server) {
    go(function () use ($server) {
        echo "server listen on 0.0.0.0:8080 \n";
    });
});
$http->start();
  • Java关键代码

源代码来自, https://github.com/netty/netty

    public static void main(String[] args) throws Exception {
        // Configure SSL.
        final SslContext sslCtx;
        if (SSL) {
            SelfSignedCertificate ssc = new SelfSignedCertificate();
            sslCtx = SslContextBuilder.forServer(ssc.certificate(), ssc.privateKey()).build();
        } else {
            sslCtx = null;
        }

        // Configure the server.
        EventLoopGroup bossGroup = new NioEventLoopGroup(2);
        EventLoopGroup workerGroup = new NioEventLoopGroup();
        try {
            ServerBootstrap b = new ServerBootstrap();
            b.option(ChannelOption.SO_BACKLOG, 1024);
            b.group(bossGroup, workerGroup)
             .channel(NioServerSocketChannel.class)
             .handler(new LoggingHandler(LogLevel.INFO))
             .childHandler(new HttpHelloWorldServerInitializer(sslCtx));

            Channel ch = b.bind(PORT).sync().channel();

            System.err.println("Open your web browser and navigate to " +
                    (SSL? "https" : "http") + "://127.0.0.1:" + PORT + '/');

            ch.closeFuture().sync();
        } finally {
            bossGroup.shutdownGracefully();
            workerGroup.shutdownGracefully();
        }
    }

因为我只给了两个核心的CPU资源,所以两个服务均只开启连个work进程即可。
5551端口表示PHP服务。
5555端口表示Java服务。

  • 压测工具结果对比:ApacheBench (ab)

ab命令: docker run --rm jordi/ab -k -c 1000 -n 1000000 http://10.234.3.32:5555/
在并发1000进行100万次Http请求的基准测试中,

Java + netty 压测结果:

clipboard.png

clipboard.png

PHP + swoole 压测结果:

clipboard.png

clipboard.png

服务QPS响应时间ms(max,min)内存(MB)
Java + netty84042.11(11,25)600+
php + swoole87222.98(9,25)30+

ps: 上图选择的是三次压测下的最佳结果。

总的来说,性能差异并不大,PHP+swoole的服务甚至比Java+netty的服务还要稍微好一点,特别是在内存占用方面,java用了600MB,php只用了30MB。
这能说明什么呢?
没有IO阻塞操作,不会发生协程切换。
这个仅仅只能说明 多线程+epoll的模式下,有效的压榨CPU性能,你甚至用PHP都能写出高并发和高性能的服务。

性能对比——见证奇迹的时刻

上面代码其实并没有展现出协程的优秀性能,因为整个请求没有阻塞操作,但往往我们的应用会伴随着例如 文档读取、DB连接/查询 等各种阻塞操作,下面我们看看加上阻塞操作后,压测结果如何。
Java和PHP代码中,我都分别加上 sleep(0.01) //秒的代码,模拟0.01秒的系统调用阻塞。
代码就不再重复贴上来了。

带IO阻塞操作的 Java + netty 压测结果:

clipboard.png

大概10分钟才能跑完所有压测。。。

带IO阻塞操作的 PHP + swoole 压测结果:

clipboard.png

服务QPS响应时间ms(max,min)内存(MB)
Java + netty1562.69(52,160)100+
php + swoole9745.20(9,25)30+

从结果中可以看出,基于协程的php+ swoole服务比 Java + netty服务的QPS高了6倍。

当然,这两个测试代码都是官方demo中的源代码,肯定还有很多可以优化的配置,优化之后,结果肯定也会好很多。

可以再思考下,为什么官方默认线程/进程数量不设置的更多一点呢?
进程/线程数量可不是越多越好哦,前面我们已经讨论过了,在进程/线程切换的时候,会产生额外的CPU资源花销,特别是在用户态和内核态之间切换的时候!

对于这些压测结果来说,我并不是针对Java,我是指 只要明白了高并发的核心是什么,找到这个目标,无论用什么编程语言,只要针对CPU利用率做有效的优化(连接池、守护进程、多线程、协程、select轮询、epoll事件驱动),你也能搭建出一个高并发和高性能的系统。

所以,你现在明白了,当我们在谈论高性能的时候,究竟在谈什么了吗?

思路永远比结果重要!

本文欢迎转载,转载请注明作者和出处即可,谢谢!

查看原文

vericmore 关注了用户 · 2019-04-29

LNMPR源码研究 @php7internal

一群热爱代码的人 研究Nginx PHP Redis Memcache Beanstalk 等源码 以及一群热爱前端的人
希望交流的朋友请加微信 289007301 注明:思否 拉到交流群

《PHP7底层设计与源码分析》勘误https://segmentfault.com/a/11...

《Redis5命令设计与源码分析》https://item.jd.com/12566383....

景罗 陈雷 李乐 黄桃 施洪宝 季伟滨 闫昌 李志 王坤 肖涛 谭淼 张仕华 方波 周生政 熊浩含 张晶晶(女) 李长林 朱栋 张晶晶(男) 陈朝飞 巨振声 杨晓伟 闫小坤 韩鹏 夏达 周睿 李仲伟 张根红 景罗 欧阳 孙伟 李德 twosee

关注 4310

认证与成就

  • 获得 21 次点赞
  • 获得 3 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 3 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2016-10-18
个人主页被 263 人浏览