Algorithm(leetcode 算法题)

Distinct Subsequences

本周题目依旧是喜闻乐见简单到变形的 dp 类,说实话在找题的时候都是从难度为 Hard 的题里随机抽 AC 率比较低的题来做的,似乎抽中 dp 的概率蛮大的……?也就是说一般而言大家会觉得 dp 比较难吗😂

虽然说是很简单的题目,但其实一开始思路还是岔了,隐约觉得是 dp 可以解决的类型,但一时又没想清楚关键的 dp 式子,反而绕弯到图的路径上了:最初的思路是用序号标记 s 中每一个存在于 t 的字符,按照其位于 s 中的顺序得到类似于 123(459)23(156)4(689)78956878 这样的字符串(括号内代表同一个字符重复出现在 t 中的位置),将字符串转换为有向图,节点路径按照严格的顺序增长连接,最后求出所有起点到达所有终点的路径总数即为结果,而求路径总数用递归或栈都可以轻松解决。最后事实这个思路是有问题的,因为存在多个位置可能的一个节点能连接的节点不同(例如节点位置标号为 3 可以连接 4,但若该节点同时具有标号 5 的可能,则无法连接 4)

所以还是兜回了 dp 上,花了点时间想清楚 dp[i][j] 的含义及表达式,问题就迎刃而解啦!最后落到真实编码实现上不过 20 来分钟,果然弄清思路、想清楚解法才是最重要的,编码只是思路的具现化罢了

完整 AC 代码,beats 了 75% 左右,还行吧,毕竟是通用型解法了

class Solution(object):
	def numDistinct(self, s, t):
		lens, lent = len(s), len(t)
		if lens == 0 or lent == 0:
			return 0
		dp = [[0 for i in range(lens)] for j in range(lent)]
		if s[0] == t[0]: dp[0][0] = 1
		else: dp[0][0] = 0
		for j in range(1, lens):
			if t[0] == s[j]: dp[0][j] = dp[0][j-1] + 1
			else: dp[0][j] = dp[0][j-1]
		for i in range(1, lent):
			for j in range(1, lens):
				if t[i] == s[j]: dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
				else: dp[i][j] = dp[i][j-1]
		return dp[lent-1][lens-1]

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

Go Memory Management

这篇算是近期读的最有价值的一篇 Review 了吧,果然耗子叔推荐必属精品

如标题所言讲的是 Go 的内存管理,开篇花了不少篇幅先简单的介绍了内存相关的基础知识和概念等,非常适合像我这样对内存相关理解没什么深入理解读者:

  • Virtual Memory Size(VSZ):进程能够访问的所有内存,包括已被置换出存储器的、分配了还未使用的以及共享内存等等
  • Resident Set Size(RSS):进程在页中真实能访问的内存(不包含已被换出的内存页)
  • Memory Management Unit (MMU):内存管理单元,维持虚拟地址到真实物理地址的映射
  • Page Table Entry (PTE)
  • Translation Lookaside Buffer (TLB):MMU 的物理缓存
  • 可执行文件格式
    • Linux 平台:Executable and Linkable Format (ELF)
    • Windows 平台:Portable Executable

Go 底层并不使用 malloc 来获取内存,而是直接向操作系统请求(通过 mmap),因此它必须实验自己的内存分配与释放机制:Go 的内存分配器基于 TCMalloc:Thread-Caching Malloc:比 glibc 2.3 的 malloc 要快,且减少了竞争状态

Go 视需要分配空间大小分为大对象和小 Object,大小两种对象有不同的分配规则:大对象直接从中心堆通过页级别的分配器获取空间,而小的对象则会被划分为约 170 种大小的 class,先从线程本地缓存中获取空间

小对象分配空间规则大致如下:

graph TD
a("大小映射到 class 类型") -->b("查找当前线程 free list")
b --> |free list 为空|c("从中心堆获取一些该 class 大小的 object")
c --> |"中心堆 free list 为空"|f("中心页分配器分配空间")
f --> g("空间分配为一系列 class 大小的 object")
g --> h("将对象放入中心 free list")
h -->e
c --> |"中心堆 free list 不为空"|e("将这些对象移到线程本地缓存的 free list")
b --> |free list 不为空|d("取出 list 中第一个 object 分配空间")
e --> d

(部分英文表达不准确,图示仅供辅助学习,建议仔细阅读原文)

大对象分配空间规则大致如下:

graph TD
a("大对象大小被近似到 page 大小(4k)") --> b("计算需要的 page 数量")
b --> c("查找中心堆的第 k 个 free list")
c --> |"free list 不为空"|d("查找下一个 free list")
d --> |"查到数组末尾"|f("系统分配")
d --> |"存在满足大小的 free list"|g("取出相应大小 page 空间分配")

微小对象的分配为享元模式,详见原文,这里不做叙述

Span 的基本概念如下:

  • Span:8K(或者更大)连续的内存区域
    • idle:没有 object,可以被释放回操作系统,或在堆分配空间时被复用
    • in use:至少有一个堆 object,空间更大
    • stack:用于 goroutine 的栈空间,可以存在于栈也可以存在于堆中,但不能同时在两者中存在

全文的讲解非常清晰,从一个小的 Go 示例开始,引入内存管理必要的相关知识介绍,然后在此基础上开始介绍 Go 内存分配的基本规则,讲述过程中对规则的类型、步骤以及适用场合等的描述也都明白易懂,强烈推荐正在使用或对 Go 感兴趣的小伙伴们细细品读


Technique(技术技巧)

这回的小技巧是这两天工作时偶然遇到的,将 mysql 数据表导出后再直接导入时报的一个错和解决方式

sql文件的导入导出的锁

默认情况下用 mysqldump 导出来的 sql 表会有这么两行用于读取的时候锁表

LOCK TABLE........
...
UNLOCK TABLE

而如果你要导入 sql 的数据库没有锁表权限,就会报类似的错误(打开 sql 文件到对应行可以发现是锁表语句):

error

最简单的解决办法就是在导入 sql 之前手动删掉 LOCK 和 UNLOCK 的两行语句

另一种解决方式是在 dump 出来时加上 --lock-tables=false 选项


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

Go is for everyone

虽然文不对题,但却是我自打 Zed Shaw 那篇以来看过的最好的 changelog 访谈。受访者是 GopherCon 第一位官方奖学金获得者,一位优雅的女性工程师:CARMEN ANDOH

讨论话题从 CARMEN 加入 Go 社区开始,前半部分更多的是与生活哲学有关,CARMEN 算是一位半路出家的工程师,在职业生涯的前 12-13 年她更多是作为一位母亲、作为一位支持她丈夫追求学业事业的妻子,因为在她刚开始工作时她并不知道自己想要做什么,所以只是找了份看起来还行的工作,生活的重心更多放在家庭而不是事业上

对于一贯经典的“作为女性为家庭牺牲,追随丈夫的脚步会不会后悔”一类的问题 CARMEN 的看法平静而稳重:在大学时她不知道自己想做什么,但她的丈夫有明确的理想和追求,所以跟随她丈夫的脚步并不是什么非常巨大的牺牲,因为如果要登一座险恶的高峰,总得有人是留在营地照看食物和水的人(one of you has to always try to do what you can to tend to the base camp )。而现在她找到她想做的事了,攻守交换,轮到她来“攀登山峰”而她丈夫“留守营地”了,而她丈夫也非常自然的接受了这一点(如下图,It's gonna be my turn)。她认为这是非常自然而然的事,只要两个人中不是某一方永远留守营地就没问题

It's gonna be my turn

从她的想法也可以看出这是一位非常豁达的女性,因为若按某些(尤其国内)想当然的思路来看,33 岁才开始学习编程成为工程师的她恐怕是“把自己的美好青春年华都奉献给家庭,没有事业没有追求”的典型代表了吧(此处应有滑稽的笑声)

科技发展的时代大家都非常的心急,仿佛亿万富翁随处可见,并且都是二三十岁出头的,但这其实是互联网时代的错觉,许多行业顶尖的专家、科学家等其实更多还是五六十岁、在自己的行业里打磨坚持了几十年的人。而在这里 CARMEN 也非常清晰点出了这里常见思维的误区:我们总是急于在自己二三十岁出头年轻立马就能成功,却忘了从平均年龄来看我们一般都要工作四十五年(这里她参考的退休年龄是 75)左右,这应当是细水长流的事情,那你又何必如此急躁呢?纵使花掉十年去找你真正想全心投入的事,你也还有几十年的时间可以努力呢

人生问题接下来的讨论话题与 Go 社区建设相关,此处不做赘述

进入技术话题范围后 CARMEN 分享了自己的工作内容:在 TravisCI 的基础设施构建团队负责 Mac 运行环境的调控开发。值得一提的是,虚拟环境的选择上使用的是 vSphere 的 VMware(在 Mac 硬件系统上运行 vSphere)而非 Docker,不用 Docker 是因为在 OS X 或 macOS 上必须通过 mac 特定证书的服务器(licensed-on-Mac Server)来运行相关程序,而这些无法在 Linux 服务器上运行——这意味着现有的庞大的容器生态系统都无法使用

日常工作对她来说具有挑战的部分是他们必须在 vSphere 提供的 API 和 Go 的微服务之间不断的进行协调,也许在不久的将来会考虑使用 KVM

如今 Travis 的代码基本基于 Go 语言:单个服务、后端 API 以及 GCE 和其他云上运行的 Docker 等都是用的也都是 Go 语言

谈到在计算机基础领域的学习,CARMEN 分享了一个她很感兴趣的领域:视觉抽象(专有名词叫,Kopfkino,英文对应的含义是 mind cinema)

她在一次相关会议上问 Golang 垃圾收集器的主要开发者之一的 Rick Hudson 当想到垃圾收集器时脑海里的 Kopfkino 是什么,Rick Hudson 毫不犹豫的回答是棋盘,因为在他看来垃圾收集器就像棋盘一样:一块又一块的碎片在网格上移动有所限制,而不同阶段的不同操作使得碎片(棋子)沿着堆(此处可将堆等价为棋盘的一列)上上下下移动,堆之间互相影响

在某一次演讲准备的过程中 Alan Donovan 为她介绍了 Golang 的内存本地化的 Kopfkino:就像瑞士山一样,山底有村庄,山上有顶峰。当你要调用不同部分的内存时,相当于不得不从山顶走到山底,而有了内存本地化的操作(个人理解相当于在山路上适当的地方建立相应的村庄?)后,你上山下山就都只需要短短一段路

CARMEN 认为垃圾收集器、内存本地化这些抽象都是极其重要而又难以理解的一部分,正因为有优秀的人代替我们思考了这些难点,我们才能够安心的通过 Go 语言编程解决我们自己的逻辑问题

在 show 的最后几位采访者还推荐了不少 Go 相关有趣的项目,这里放几个我个人很感兴趣的:

简而言之,这是篇不可多得的好文章,推荐大家都看一看


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