ARTS 第23周

ARTS 第23周分享

[TOC]

Algorithm

349. Intersection of Two Arrays

[easy]

[题目描述]

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

[解题思路]

• 先排序，再遍历求交集

[参考代码]

func intersection(nums1 []int, nums2 []int) []int {
    // 先将两个数组先排序
    // 遍历小的数组，将小的数组中的元素在大的数组中查询，如果存在，则记录入一个新的数组
    // 记录每次在大的数组中找到元素的位置，减少下次在大数组中遍历的次数
    res := make([]int, 0)

    if len(nums2) == 0 || len(nums1) == 0 {
        return res
    }

    sort.Slice(nums1, func(i, j int) bool {
        return nums1[i] < nums1[j]
    })
    sort.Slice(nums2, func(i, j int) bool {
        return nums2[i] < nums2[j]
    })

    if len(nums1) < len(nums2) {
        nums2, nums1 = nums1, nums2
    }

    tmp := nums2[0] + 1 // 将tmp的值初始化为数组第一个元素的值+1（永远和第一个元素不相等）， 用于判断如果数组中出现相同的元素时，直接跳过
    start := 0
    for i := 0; i < len(nums2); i++ {
        if tmp == nums2[i] {
            continue
        }
        tmp = nums2[i] // 当前需要判断的元素

        for j := start; j < len(nums1); j++ {

            if tmp == nums1[j] { // 有交集
                res = append(res, nums1[j])
                start = j
                break
            }
        }
    }
    return res
}

Review

Learning to Use Go Reflection — Part 2: https://medium.com/capital-one-tech/learning-to-use-go-reflection-part-2-c91657395066

反射的实际应用

Tips

把本地分支mybranch1与远程仓库origin里的分支mybranch1建立关联：

1. git push -u origin mybranch1
2. git branch --set-upstream-to=origin/mybranch1 mybranch1

这两种方式都可以达到目的。但是1方法更通用，因为你的远程库有可能并没有mybranch1分支，这种情况下你用2方法就不可行，连目标分支都不存在，怎么进行关联呢？

所以可以总结一下：

​ git push -u origin mybranch1 相当于 git push origin mybranch1 + git branch --set-upstream-to=origin/mybranch1 mybranch1

HTTPS 基本过程：

• 客户端发送一个 ClientHello 消息到服务器端，消息中同时包含了它的 Transport Layer Security (TLS) 版本，可用的加密算法和压缩算法。

• 服务器端向客户端返回一个 ServerHello 消息，消息中包含了服务器端的 TLS 版本，服务器所选择的加密和压缩算法，以及数字证书认证机构（Certificate Authority，缩写 CA）签发的服务器公开证书，证书中包含了公钥。

  客户端会使用这个公钥加密接下来的握手过程，直到协商生成一个新的对称密钥。证书中还包含了该证书所应用的域名范围（Common Name，简称 CN），用于客户端验证身份。

• 客户端根据自己的信任 CA 列表，验证服务器端的证书是否可信。如果认为可信（具体的验证过程在下一节讲解），客户端会生成一串伪随机数，使用服务器的公钥加密它。这串随机数会被用于生成新的对称密钥

• 服务器端使用自己的私钥解密上面提到的随机数，然后使用这串随机数生成自己的对称主密钥

• 客户端发送一个 Finished 消息给服务器端，使用对称密钥加密这次通讯的一个散列值

• 服务器端生成自己的 hash 值，然后解密客户端发送来的信息，检查这两个值是否对应。如果对应，就向客户端发送一个 Finished 消息，也使用协商好的对称密钥加密

• 从现在开始，接下来整个 TLS 会话都使用对称秘钥进行加密，传输应用层（HTTP）内容

TLS 证书机制

• 客户端根据自己的信任 CA 列表验证服务器的身份。现代浏览器中，证书验证的过程依赖于证书信任链。
• 所谓证书信任链，即一个证书要依靠上一级证书来证明自己是可信的，最顶层的证书被称为根证书，拥有根证书的机构被称为根 CA。 从上到下即 Root CA -> 二级 CA -> 网站。
• 证书当中包括 CN(Common Name)，浏览器在验证证书的同时，也会验证 CN 的正确性。即不光需要验证“这是一个合法的证书”，还需要验证“这是一个用于 Github.com 的证书”。（即验证合法，也验证使用人）
• 根证书一般是操作系统自带的。不管是桌面系统 Windows，macOS 还是移动端系统 Android, iOS 都会内置一系列根证书。随着操作系统本身的升级，根证书也会随着升级进行更新。

share

RESTful：

1. REST描述的是在网络中client和server的一种交互形式；REST本身不实用，实用的是如何设计 RESTful API（REST风格的网络接口）；

2. URL中只使用名词来指定资源，原则上不使用动词。“资源”是REST架构或者说整个网络处理的核心。

3. 用HTTP协议里的动词来实现资源的添加，修改，删除等操作。即通过HTTP动词来实现资源的状态扭转

4. Server和Client之间传递某资源的一个表现形式，比如用JSON，XML传输文本，或者用JPG，WebP传输图片等。当然还可以压缩HTTP传输时的数据（on-wire data compression）。

5. 用 HTTP Status Code传递Server的状态信息。比如最常用的 200 表示成功，500 表示Server内部错误等。

RPC：

• RPC就是要像调用本地的函数一样去调远程函数。

  在远程调用时，我们需要执行的函数体是在远程的机器上的，也就是说，Multiply是在另一个进程中执行的。

• Call ID映射。我们怎么告诉远程机器我们要调用Multiply，而不是Add或者FooBar呢？

  所以，在RPC中，所有的函数都必须有自己的一个ID。这个ID在所有进程中都是唯一确定的。客户端在做远程过程调用时，必须附上这个ID。然后我们还需要在客户端和服务端分别维护一个 {函数 <--> Call ID} 的对应表。两者的表不一定需要完全相同，但相同的函数对应的Call ID必须相同。当客户端需要进行远程调用时，它就查一下这个表，找出相应的Call ID，然后把它传给服务端，服务端也通过查表，来确定客户端需要调用的函数，然后执行相应函数的代码。

• 序列化和反序列化。客户端怎么把参数值传给远程的函数呢？

  在远程过程调用时，客户端跟服务端是不同的进程，不能通过内存来传递参数。甚至有时候客户端和服务端使用的都不是同一种语言（比如服务端用C++，客户端用Java或者Python）。这时候就需要客户端把参数先转成一个字节流，传给服务端后，再把字节流转成自己能读取的格式。这个过程叫序列化和反序列化。同理，从服务端返回的值也需要序列化反序列化的过程。

• 网络传输。远程调用往往用在网络上，客户端和服务端是通过网络连接的。所有的数据都需要通过网络传输，因此就需要有一个网络传输层。网络传输层需要把Call ID和序列化后的参数字节流传给服务端，然后再把序列化后的调用结果传回客户端。

  因此，它所使用的协议其实是不限的，能完成传输就行。尽管大部分RPC框架都使用TCP协议，但其实UDP也可以，而gRPC干脆就用了HTTP2。Java的Netty也属于这层的东西。

// Client端
// int l_times_r = Call(ServerAddr, Multiply, lvalue, rvalue)

1. 将这个调用映射为Call ID。这里假设用最简单的字符串当Call ID的方法
2. 将Call ID，lvalue和rvalue序列化。可以直接将它们的值以二进制形式打包
3. 把2中得到的数据包发送给ServerAddr，这需要使用网络传输层
4. 等待服务器返回结果
5. 如果服务器调用成功，那么就将结果反序列化，并赋给l_times_r

// Server端

1. 在本地维护一个Call ID到函数指针的映射call_id_map，可以用std::map<std::string, std::function<>>
2. 等待请求
3. 得到一个请求后，将其数据包反序列化，得到Call ID
4. 通过在call_id_map中查找，得到相应的函数指针
5. 将lvalue和rvalue反序列化后，在本地调用Multiply函数，得到结果
6. 将结果序列化后通过网络返回给Client

其中：

• Call ID映射可以直接使用函数字符串，也可以使用整数ID。映射表一般就是一个哈希表。
• 序列化反序列化可以自己写，也可以使用Protobuf或者FlatBuffers之类的。
• 网络传输库可以自己写socket，或者用asio，ZeroMQ，Netty之类。

本周阅读

第一周：2, 3, 6, 7
什么是 RPC 框架？https://www.zhihu.com/question/25536695/answer/36197244
Go module机制下升级major版本号的实践： https://tonybai.com/2019/06/03/the-practice-of-upgrading-major-version-under-go-module/

GPM 到底是什么？（一）https://mp.weixin.qq.com/s/JOjUWp15JbEu54VJHY8i_A

Go语言回顾：从Go 1.0到Go 1.13: https://tonybai.com/2019/09/

Learning to Use Go Reflection — Part 2: https://medium.com/capital-one-tech/learning-to-use-go-reflection-part-2-c91657395066