Algorithm(leetcode 算法题)

K-Similar Strings

还是 Graph Tag 下难度为 hard 的一道题,初始思路就是暴力遍历可能的交换结果,每个状态作为一个元素入队列,基本操作概念是 BFS

这一版编码实现出来后果不其然超时了……但是 case 的通过率将近 90%,可以发现这题本身的限制并不严格

优化了一下思路,发现没必要对字符两两无脑交换后比较,因为变换最终目标是固定的,而且一次变换要能消除至少一处不相同,所以每个位置的变换可能性是可以提前计算出来的。此外还存在以下这种重复的可能:

graph LR
A --> s1("Status 1")
s1 --> s2("Status 2")
s2 --> B
A --> ss1("Status 2")
ss1 --> ss2("Status 1")
ss2 --> B

因为题目只计算最短变换次数而不是要求输出所有最短结果,因此上图的可能在入队列时可以排除。最后加了个 visited 的 set 用于记录重复的状态

值得一体的是一开始没想清楚没有加上 visited 导致虽然优化了思路,但不知为何 case 通过率反而降到了不到 20% 的惨剧……🤣

AC 的完整代码,beats 不到 55%,勉勉强强凑合吧:

import Queue
class Solution(object):
	def diffAndCount(self, a, b):
		count, length, diff = 0, len(a), []
		pToI, iToP = {}, {}
		for i in range(0, length):
			if a[i] != b[i]:
				diff.append(i)
				if a[i] in pToI:
					pToI[a[i]].append(i)
				else:
					pToI[a[i]] = [i]
		return diff, pToI
		
	def kSimilarity(self, A, B):
		if A == B : return 0
		diff, pToI = self.diffAndCount(A, B)
		queue, visited = Queue.Queue(), set()
		queue.put([diff, pToI, 0, [a for a in A]])
		while not queue.empty():
			hDiff, hPToI, hLev, hA = queue.get()
			if len(hPToI[B[hDiff[0]]]) == 0: continue
			else:
				for i in hPToI[B[hDiff[0]]]:
					newDiff, newPToI, newLev = [x for x in hDiff], {}, hLev + 1	
					newA = [a for a in hA]
					for k in hPToI: newPToI[k] = [x for x in hPToI[k]]
					if B[i] == hA[hDiff[0]]:
						newDiff.remove(i)
					else:
						newPToI[hA[hDiff[0]]].append(i)
					newDiff.remove(hDiff[0])
					if len(newDiff) == 0: return newLev
					newPToI[hA[i]].remove(i)
					newPToI[hA[hDiff[0]]].remove(hDiff[0])
					newA[hDiff[0]], newA[i] = newA[i], newA[hDiff[0]]
					joindA = ''.join(newA)
					if joindA not in visited:
						queue.put([newDiff, newPToI, newLev, newA])
						visited.add(joindA)
		return -1

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

The Go scheduler

Scalable Go Scheduler Design Doc

Go 语言升级版本时对调度器的重新规划与设计的综合文档,内容很全且废话不多,非常精简的介绍了 Go 当前存在的问题、schedular 的痛点等,针对这些缺陷提出了修复方案

全文不长但个人认为还挺有意义所以自己顺手无授权翻译了一份中文,博客目录内自取


Technique(技术技巧)

vim 的列操作

对 vim 一直挺苦手,操作不熟练,能在本地用 vscode、sublime 之类的专用文本编辑解决的问题都不会用 vim,而这回遇到了不得不在 vim 上进行文本操作的情况,特别记录一下

想要达成的目的:

  • 替换所有行的某一列为指定内容
  • 行末加上双引号

每一行的内容大概是这样的:

746900951138997314【此处一个tab】jhfg nnvd c,jiohfr	d

希望将数字后面的第一个 tab 替换为 '\x01'。一开始是用了 awk + sed,想依赖默认的字符串切分功能,但因为右边的字符串内也可能存在 tab 键所以默认的分割无法满足需求,后来又想依赖正则表达式(因为一开始的字符串可以确保是一定位数的数字,但在 vim 里编写正则也不熟……最终发觉不用那么麻烦,还是好好查了一下 vim 模式下列编辑的快捷键,完整操作:

  • CTRL + V 进入 visual mode
  • 光标移到要删除的列位置
  • SHIFT + G选中到末尾,此时应该是列位置左边的所有数字列都被选中了,右键减少选区到要删除的一列
  • d 键删除
  • 重复一遍操作选中刚才删除那列后的一列
  • SHIFT + I 进入输入模式
  • CTRL + V,CTRL + A 输入'\x01'
  • ESC 键退出

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

K8s and Virtual Kubelet

如标题所言,本文主要介绍 k8s 以及与作为 k8s 主要组成部分相关的虚拟 Kubelet

在访谈正式开始前有一段小对话引起了我的兴趣:受访者问主持人对 Kubernetes 有多少了解,主持人是这么回答的:

So we've done shows on Kubernetes, which means we've had smart people teach us about it, and we haven't actually used it IRL, or anything, so it's very much academic and somewhat transient knowledge that floats in and out between my ears; I don't know if that speaks for you, Adam, but very generic knowledge, no practical use of it, so a general rundown would be nice, too.

虽然他们参加过 Kubernetes 的 show,也有相当聪明的人向他们介绍过,但是他们自己并没有实践过,所以 Kubernetes 在他们脑内是相当"学术"的一个概念,对于他们的知识体系而言这句话概括的很好:

transient knowledge that floats in and out between my ears

对 Kubernetes 概念、架构、意义等的了解非常虚浮抽象,在耳朵旁进进出出,最后也没留下多少有深入意义的东西——这和我们平时碎片化学习知识的状态很像,公众号文章、短小的博客上的知识点,在我们脑海里进了又出,也就是说我们并没有真正学到这部分知识,到了要投入应用的关键时刻脑内还是会一片浆糊

就像我虽然去年就对 k8s 感兴趣,看过 k8s classroom 教程跟步骤操作过也了解过他的架构组成和意义,但若真到了跟别人交流 k8s 的场合,我也不见得能说得出什么有价值的观点和理解——这就是所谓的无意义学习吧

学习的方法真的是不得不多多注意啊,什么都没学到还产生了自己非常努力的错觉是件非常可怕的事

对 k8s 的介绍提到了其有潜力作为新的 PaaS 基础的一个重要特性:

there's other components like controllers and things like that that run within the system that are just constantly trying to reconcile the differences.

其内部有各种各样的组件负责协调集群状态,最简单比如几个容器实例挂了,内部组件会根据预先设定的标准值(如某镜像必须保证至少有 x 个在运行实例,一旦少于 x 个系统自动启动新的实例)对节点状态进行调整

在看对虚拟 kubelet 的介绍前我先自己从 kubernetest.io 复习了下 kubelet 的概念:可以认为是每个节点的"代理",负责确保 PodSpec 文件(通常为 YAML 或 JSON 格式)描述的 pod 群正常工作,是集群节点单元的管理者

而虚拟 kubelet ——字面含义,他具备 kubelet 的功能,但又不是真正的 kubelet。Erik 告诉我们从 Kubernetes 的概念上去理解 kubelet:我们认为他是 API 服务器的一个入口,是被注册到服务器的一个组件,系统基于这一事实进行运作,例如 API 服务器可以知道访问该 node 的某一 pod 的请求我们需要转发到这一 Kubelet 上、调度器可以将任务调度到这里等等。实际上就是通过它可以与 API 交互

那么既然这块像插件一样"独立"出来了,就意味着理论上我们甚至可以在虚拟 Kubelet 的加持下启动一个完整隔离的虚拟机——就像如今我们的云基础建设一样——或者以 pod 为单位,但以比容器更加轻量级的方式运行批量任务等

截止到访谈发布,ACI(Azure Container Instances)已经能通过虚拟 Kubelet 在不存在真实节点的前提下在 k8s 集群中启动了

Kubernetes 的这种运作方式 可能会成为将来 Serverless 建设的核心,有一个非常重要的点:作为云服务提供出去的资源,仅在计算运行的时候收费(you're only paying for the time that they're running),资源闲置时不收费。简而言之这应该是一种理论上完美的**基于计算量**计费的模式

Brian 提到 Kubernetes 它本身是一个 着眼于容器、以容器为驱动核心的工作流程,但是 Kubelet 却并不在乎它到底启动了些什么:启动的是 Docker 还是别的容器——甚至不是容器都不重要。对于一些运行完即结束、不需要维持状态的轻量级 job,真实存活的 node 其实也不是必要的,因此虚拟的 Kubelet 在这里能起到非常大的作用。而说到容器顺便也还提到了 Azure 和 Amazon:Azure 函数和 Amazon 的 Lambda 都允许在干净的环境内运行代码,但并不是容器环境

之后是比较零散的内容,例如我个人很喜欢的一个对开源和封闭的看法:

Competing for customers is kind of a losing game.

以及 Go 的升级等:Go 1.10 升级带来了对测试结果的缓存,而这实际上是编译器改变优化带来的优势:原本的 Go 有一个参数,而这个参数新版本不再支持,因为 Go 自身可以基于文件内容是否改变做出判断决定是否重新编译


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