Algorithm(leetcode 算法题)

Similar String Groups

Graph 标签下难度为 hard 的又一道题……想了没多久就有了思路:能一步变换到位的两个点之间连通,每个节点与其他某一节点之间至少有一条边相连构成一个子图,求子图数量最少为多少。用暴力遍历的话,O(n2) 无论如何都能编码实现一个方案,最大可能性是超时,为了减少遍历判断次数可以加个 visited 的 map 记录已访问过的可能

从思考如何合并两个子图的中间状态开始,一直到点对点直接判断连接子图为止,各种思路都过了一下,想了很久也没有除了暴力遍历以外的点与子图连接思路,所以最终还是看了讨论区的一两个答案

然后非常惊喜的发现各位大佬们也没有别的思路!基本还是暴力遍历!开心!

……咳咳

看了评论区的两种方法,基本上也还是以点找点通过 for i 套 for j 的二重循环方式构建子图并逐步记录访问分组结果,跟我思路的区别在于他们是直接从数组中 remove/delete 掉,我是打算用 visited 记录

最后也没多折腾,找了一个据说 beats 了 100% 的 C++ 版用 python 实现了,这个思路比较创新的一点在于根据长度的不同采用了两种解法:小于 20 对每个不属于子图的字符串暴力遍历可能变形的方案并判断原数组中是否有该点,反之则用并查集寻找图的"起点"作为子图标志。写完提交没想到提交居然报了……Internal Error????

恕我孤陋寡闻没见过这种类型错误……要是代码数组越界之类不应该是 runtime error 么……

下面是完整的思路,不理解的朋友也可以不用看讨论区了因为该思路的原作者也没有任何解释只有代码

from Queue import Queue
class Solution(object):
	def replaceAvailable(self, A, B):
		count, length = 0, len(A)
		for i in range(length):
			if A[i] != B[i]:
				count += 1
				if count > 2:
					return False
		return True
		
	def recursiveFind(self, s, parent):
		if parent[s] != s:
			parent[s] = self.recursiveFind(parent[s], parent)
		return parent[s]
		
	def caculate1(self, A):
		arrA, count, length= [s for s in A], 0, len(A[0])
		while len(arrA) != 0:
			head = arrA[0]
			q = Queue()
			q.put(head)
			while arrA.count(head):
				arrA.remove(head)
			while not q.empty():
				head = q.get()
				for i in range(0, length-1):
					for j in range(i+1, length):
						if head[i] != head[j]:
							similar = head[0:i] + head[j] + head[i+1:j] + head[i] + head[j+1:length]
							if arrA.count(similar):
								while arrA.count(similar):
									arrA.remove(similar)
								q.put(similar)
			count += 1
		return count
		
	def caculate2(self, A, length):
		parent = {}
		for str in A:
			parent[str] = str
		for i in range(0, length-1):
			for j in range(i+1, length):
				if self.replaceAvailable(A[i], A[j]):
					parent[A[j]] = self.recursiveFind(A[i], parent)
		
	def numSimilarGroups(self, A):
		length = len(A)
		if length < 20: 
			return self.caculate1(A)
		else:
			return self.caculate2(A, length)

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

Testing distributed systems in Go

如标题,主要以 etcd 为例简单介绍了给分布式系统进行测试的方式。根据常见理论我们往往认为对分布式系统进行测试是一件“很困难”的事——这是一个非常具有欺骗性的结论

文章指出了分布式系统所需要常见的常见的测试类型并提供了相应的测试方法与配套工具:

  • etcd 的行为的验证: functional-tester
  • 网络分裂/分区:iptables
  • 网络缓慢:tc 命令模拟
  • 崩溃测试(电力丢失、io 错误、部分写入等):gofail

Technique(技术技巧)

多日志文件同时监控

依然是一个很小很微不足道的技巧,当进程的日志输出到命名相似的不止一个文件(例:schedular-err.log、schedular-info.log)而我们又不想开多个窗口同时看多个滚动流时可以这样:

tail -f schedular-*

混合多份日志到一个输出流滚动打出来

其实这也算是个基础的命令行技巧了 (毕竟是 rm -rf /* 用的很熟练的人),但之前也确实一直没想到,所以还是记录分享下吧


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

All About The Go Compiler

本周一篇与 Go 编译器相关的 changelog,由于对编译器没多少了解,很多技术实现的细节讨论其实没看懂,尽力理解了比较 general 的一些部分……Orz

用受访者 David 的语言概括:编译器的基本工作是将你的输入转化为基于树结构的一种表达方式,即我们常说的语义树。Go 的编译器会扫描我们输入的字符转化为 AST,进行语义分析,再将 AST 转化为 SSA(Static Single Assignment,要求每个变量只被分配一次,任何一个变量在使用前被定义,具体见百科),进行部分优化,然后连接到 Go 汇编程序,最后输出机器代码,而在这一整套环节中 David 负责的部分是将 SSA 适配到底层不同的指令集

如今主流的语言基本配备有自己的一套编译器生态,David 认为在这其中 Go 的编译器并不算坏。对此采访的大家提出了编译器可以更好、更进一步优化的观点,对于这个惯例问题他的一个核心反问是:

对什么而言更好?对谁来说更好?

他们团队目前有对编译时间、性能的相关优化等等,但对一方面的优化总会对另一方面造成影响,这里总是有一个相对的代价需要去权衡,而实际上不仅限于编译器,无论是编程语言模式的设计还是系统的规划等,都存在这样的 trade-off,永远没有对任一方面都是最优的设计

针对编译器场下有社区的成员提到 Go 语言并没有一个被正式认定的编译器:一个被认证的编译器要求你有输入语言及其预期行为的精确规范,要求你有硬件行为的精确规范,这存在一定的难度(这段我几次阅读下来都没能很好的理解,大概还是受限于对编译器浅薄的理解吧)

在他被问到 Go 最终会不会像 GCC 一样变成有各种 flag 控制的编译器,David 认为最终还是会的,这是个时间的问题,但希望能尽可能延后它的到来,因为编译标志的存在会使一切变得复杂:每个标志都需要测试和记录,在编译对象有大量的 package 相互依赖且各自用了不同的编译条件时,出了选项相关的 bug 该如何汇报?汇报要包含你的每个 package 的每个编译标志吗?……每一个实现要求都会使架构复杂程度几何倍数上升。但随着 Go 的发展,当某些特性变得足够重要、不可缺少时,这终究还是会发生的

接下来的部分基本完全偏题,大家开始讨论 Go 团队的成员喜欢吃什么类型的派了(老实说一开始还以为 Pie 是某类技术或特征的隐喻……没想到是真的在一本正经讨论喜欢吃什么口味的派了23333)


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