Algorithm(leetcode 算法题)

Redundant Connection II

发现之前做的题大多数是偏向 DP 的,所以最近找题的时候刻意加上了 Graph 的筛选 tag,发现 Graph Tag 下面 hard 难度的题非常少(甚至还有几道上了锁)

这题不复杂——应该说本来可以很复杂但题目本身呈现的比较简单:多余的边只有一条,如果多余的边不止一条,思路应该就不一样了

一开始在观察分析后总结出多余边的两种独立形态:

  1. 成环
  2. 某一个节点入度为 2

一开始照着这个思路编码,test 通过率都超过 80% 了才在一个 case 里发现原来这两种情况存在交集:既成环又存在某一节点入度为 2,例如下图情况

graph LR
1 --> 4
4 --> 2
2 --> 1
3 --> 1

所以在原先编码的基础上直接简单粗暴的加上了判定同时出现的情况,没有过多优化思路,结果就是虽然 AC 了但是 beats 率惨不忍睹😂

beats

一首凉凉送给自己~~(这跟没 AC 究竟有什么区别)~~,完整代码如下:

class Solution(object):
	def findRedundantDirectedConnection(self, edges):
		inCount, outCount, maxPoint, doubleInCount  = {}, {}, len(edges), []
		newEgdes = [edge for edge in edges]
		for i in range(1, maxPoint + 1):
			inCount[i] = []
			outCount[i] = []
		for edge in edges:
			if len(inCount[edge[1]]) != 0:
				doubleInCount.append(edge)
				doubleInCount.append([inCount[edge[1]][0], edge[1]])
			inCount[edge[1]].append(edge[0])
			outCount[edge[0]].append(edge[1])
		while True:
			onlyOneEdgePoint = False
			for p in range(1, maxPoint+1):
				inP, outP = len(inCount[p]) if p in inCount else 0, len(outCount[p]) if p in outCount else 0
				if inP == 1 and outP == 0:
					newEgdes.remove([inCount[p][0], p])
					outCount[inCount[p][0]].remove(p)
					inCount[p] = []
					onlyOneEdgePoint = True
				elif inP == 0 and outP == 1:
					newEgdes.remove([p, outCount[p][0]])
					inCount[outCount[p][0]].remove(p)
					outCount[p] = []
					onlyOneEdgePoint = True
			if not onlyOneEdgePoint:
				break
		if len(doubleInCount) != 0 and len(newEgdes) != 0:
			return doubleInCount[0] if doubleInCount[0] in newEgdes else doubleInCount[1]
		elif len(newEgdes) == 0:
			return doubleInCount[0]
		else:
			return newEgdes[-1]

Review(阅读并点评至少一篇技术文章)

这周读的篇目多但每篇都不长,所以全部放在一起,跟上周看的那篇 Go 内存管理介绍是同一个作者

Effective error handling in Go.

文章内容不多,主要介绍了 Go 中处理 error 的几种方案,总结如下:

  • 更多时候建议使用 if err != nil {...} 这样的处理错误方式而不是 if err == nil {...}
  • 自定义错误类型,抛出用户关心的错误(例:给用户返回服务器繁忙以及空的响应数据,而不是直接将网络错误、数据库错误等 error 字符串直接抛出去)
  • 将错误保持为某种状态,不立即抛出,例如 go/loader 加载出错,后续可能会以同样的参数重试,因此不需要立刻抛出
  • 使用诸如 func handleError(err error){...} 一类的函数统一处理错误,避免重复无用代码

感觉不仅仅是 Go,别的语言在类似的错误处理也是类似的通用设计,但细节有所区别

The Go netpoller

本文是对 Go 如何处理网络 I/O 的基本介绍:在 Go 语言中所有的 I/O 都是阻塞的,Go 语言的生态被设计为鼓励人们使用 goroutine 和 channel 而不是常规的 callback 和 future。例如 http 服务器每接到一个连接都会新开一个 goroutine 去处理这个连接的所有请求。

channel 的使用方式我们可以看到是阻塞的,但 goroutine 又是异步的在执行函数,那么如何在不使用传统 callback 的的情况下实现——即如何将异步转换为阻塞,就是 netpoller 正在做的事情。在不同平台上 netpoller 的实现不同,例如在 Linux 上使用 epoll,在 BSD 和 Darwin 上使用 kqueue,而在 Windows 上则使用 IoCompletionPort

你每在 Go 中接受一个连接,相应的文件描述符都会被设置成非阻塞模式
会被阻塞的网络请求都在底层都会在底层新开一个 goroutine 去请求,而 Go 在对连接读取或写入数据都会不断尝试直到数据返回,在此期间是阻塞的;而 netpoller 在收到操作系统通知可以对文件描述符进行 I/O 操作后会检查其数据结构看是否有 goroutine 阻塞在上面,并通知他们继续重试 I/O 操作

Go scheduler: Ms, Ps & Gs

一篇对 Go 语言调度器基本结构的说明,对 M、P、G 三种实体的数据结构和功能都给了清晰易懂的说明,看完后能对 Go 的调度器有个基本的礼节,更加详细的架构和设计方案建议阅读 Go schedular 设计的论文原文


Technique(技术技巧)

数据库语句的优化

是最近在工作中遇到的一个坎,其实非常简单,但对于一直对数据库操作不敏感的我来说算是一个小进步吧

在一个异步队列的 job 里要查询一批 id 的数据,原本的语句大概是这样写的:

for item, _ := range items {
  client.Query("SELECT * FROM table WHERE id = " + item.id)
}

考虑到 go 的 runtime 会为被 block 的操作新开一个 goroutine 去执行,所以这几条查询语句很有可能是“分批”到达 mysql 去执行的,相当于要执行 len(items) 次 sql 语句,而且个人认为在 mysql 看来这些都是独立的请求,所以 mysql 很可能不会自动做聚合优化?(不确定,只是直觉,有待考证)所以将语句改成以下可以一条语句直接查询完毕的写法

SELECT * FROM table WHERE id IN (id1, id2, id3......)

微不足道的小技巧,数据库大佬们拍砖拍的轻一点谢谢😂


Share(分享有观点和思考的技术文章)

Dependencies and the future of Go

这回的访谈与 Go 语言、Vgo、错误处理以及 Go 2.0的更新有关

受访者 Russ 为是 Go 这门语言创始团队最早的成员之一,当年他们完全没想到这门语言会火起来,当年 Release 前 Russ 的想的是将来的流行语言能从 Go 这里“抄走”他们引以为豪的 concurrency 和 interface 等特性,他们就很满足了,这样多少也算他们的思考为流行的编程语言发展做出了贡献——事实是当年热火朝天的纳闷语言如今早已销声匿迹,Go 却发展的如火如荼,Russ 见证了参与 GopherCon 的人从最初的 700 来人——也许这就是全部的 Go 用户——发展到如今 Go 语言使用者超过了百万,这令他们感到非常震惊

话题回到原定的主题上,关于项目依赖管理的问题,Russ 认为重要的一点是当你的代码变得足够多,项目变得足够大时,你要能对其做渐进的改变(例如迁移,一次只迁移一小部分):例如版本升级等,你不能指望项目能够一次性完全从 v1 升级到 v2,这必然是一个循序渐进的过程

针对此 Russ 还提到了一些与 Go 版本管理相关的知识,在此不做赘述

GOPATH 是一个经常被吐槽的点,以及 Go 语言“一切都发生在 GOPATH 下”的这种设定也让其他语言的开发者们感到很不习惯,对此 Russ 认为新事物需要有一个接受的过程:例如,一开始会觉得很怪异,但适应了就还好(吐槽下,现在用 Go 开发了一个多月还没适应,项目依赖打包进来全靠 govendor 苟活)

进一步聊到 Go 的未来发展时主持人提到了 Go 目前尚且缺失的一个重大模块—— UI 模块,对此 Russ 表示 Go 语言的核心 lib 开发中暂时没有与 UI 相关的计划,它认为对于核心库来说 UI 并不是那么重要,而且 UI 本身是个极其庞大的计划,并不是短期能准备好的,并且在 Go 的发展方向上,他们团队认为 Go 应该是一个为大规模编程准备的语言:有大量的工程师参与开发、大量的部署与代码、巨大的分布式系统以及原生并发机制等,这些都是 Go 语言的强项所在

这个项目似乎会在结尾的时候推荐有趣的 Go 相关项目给大家,这里提取一个我比较喜欢的:

  • Kube-lego:一个在 k8s 集群中应用的 controller,可以自动化使用 Letsencrypt 进行 TLS 加密、nginx 的设置等,即我们常说的一键 https

Comment(来自别人的评价与相关讨论)