ARTS-WEEK7

2019-05-06
#ARTS #Leetcode

本周ARTS

本周ARTS打卡内容：

  1. Algorithm 来源 LeetCode23
  2. Review 分享 为何维基百科的链接预览功能花费了这么长时间
  3. Tip 分享 golang包管理go module
  4. Share 分享 go语言实现gRPC实战

Algorithm

LeetCode的23题，合并k个有序的链表：

https://leetcode.com/problems/merge-k-sorted-lists/

样例：

有序链表：

1
2
3
4
5
[
  1->4->5,
  1->3->4,
  2->6
]

输出：

1
1->1->2->3->4->4->5->6

解题思路：

前面我们解决了有序双链表排序问题，比较两个链表的元素，将较小的值拷贝到新的链表，直至两个链表都遍历完。这题也可以用同样的思路，比较k个链表的当前元素值，最小的值拷贝的新的链表，最小值所在的链表前进一位，如此循环，直至所有链表元素为空，即得到了我们想要的值。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
	var head = &ListNode{0, nil}
	var node *ListNode
	var value int
	node = head
	for !listnil(lists) {
		value, lists = minAndNext(lists)
		node.Next = &ListNode{value, nil}
		node = node.Next
	}
	return head.Next
}

// 判断所有链表为空
func listnil(lists []*ListNode) bool{
	for _, list := range lists{
		if list != nil {
			return false
		}
	}
	return true
}

// 找出最小值，最小值所在的链表前进一位
func minAndNext(lists []*ListNode) (int, []*ListNode){
	var min = 10000
	for _, list := range lists{
		if list != nil && list.Val < min {
			min = list.Val
		}
	}

	for k, list := range lists{
		if list != nil && list.Val == min {
			lists[k] = lists[k].Next
			break
		}
	}
	return min, lists
}

算法复杂度：

遍历了所有N个元素，每次选出最小元素时都需要遍历k次，所有算法的时间复杂度为O(Nk)。

Review

本周内容：Why it took a long time to build that tiny link preview on Wikipedia

https://blog.wikimedia.org/2018/04/20/why-it-took-a-long-time-to-build-that-tiny-link-preview-on-wikipedia/?utm_source=wanqu.co&utm_campaign=Wanqu+Daily&utm_medium=website

页面预览是一项简单的功能，当前很多的网站都支持，但是奇怪的是维基花了4年才实现这个功能，这就像一座冰山，看起来只有浮在水上的一点，看到水下时才知道冰山有多大。

  1. 需要选择缩略图
    维基有上百万的页面，都是以wikitext的方式存储的，对于每篇文章不会指定索引图像。在2012年时，我们的工程师Max Semenik创建了一个插件，为每篇文章创建最合适的缩略图。为了页面预览功能，我们升级了这个插件，只针对文章的第一节产生缩略图。

  2. 生成总结
    维基有上百万的页面，过去我们通过Max Semenik编写的插件来生成总结。但该插件主要是来处理text文件的，在页面预览中它就不适用了，根据HTML来生成总结更适用，比如化学文章中的化学公式就需要HTML。很多文章，以坐标信息和发音信息开头，很多这样的内容不属于我们的总结，另一些又不清楚是否属于。总结有很多输入，我们识别哪些不出现在预览中。感谢基础设施团队帮助我们构建这样的API。

  3. 和社区一起工作
    我们的编辑社区很关心我们的产品，我们全程和他们一起工作，处理各种边界问题。

  4. 设计
    我们做了很多工作，我们的设计师Nirzar在文章中描述过，我在这里就不在赘述。我们的每一步中都有设计参与，讨论特性的展示；缩略图和总结等等。

  5. 测试分析
    如何评论是一个巨大的改变。在维基，我们和注意隐私，我们或许是世界上唯一的没有跟踪用户行为的大型网站。

  6. 扩容API
    我们每分钟有50万的请求，我们过去的APIs是为机器人编写的，用来清除编辑内容，不是为读者设计的。感谢维基服务团队提供基础设施来处理大量缓存问题，确定新编辑内容的缩略图生成了。

Tip

golang包管理go module：

https://leitty.github.io/2019/05/06/%E5%8C%85%E7%AE%A1%E7%90%86Go-module/

Share

分析go语言实现gRPC，包括普通gRPC客户端和服务端，gRPC流服务的客户端服务端，gRPC的TLS证书认证，基于CA的TLS证书认证，gRPC的拦截器，gRPC和HTTP同时实现，gRPC Deadline，分布式链路追踪Zipkin的实现：

https://github.com/EDDYCJY/blog