ARTS
ARTS 是陈浩（网名左耳朵耗子）在极客时间专栏里发起的一个活动，目的是通过分享的方式来坚持学习。
每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。
本周内容
这一周的 ARTS 你将看到：
- Work Break II 这道题的评论区竟然有一半人都在吐槽测试例太恶心？
- 一篇文章了解 Golang GC 的“昨天、今天和明天”。
- 一个老 Gopher 常谈的问题，到底 return 和 defer 哪个先执行？
- 不要一开始就经陷入细节的地狱。
Algorithm
本周的算法题是 LeetCode 的 139.Work Break 和 140.Work Break II.
我本来只想做一下 140 题，这道题目的要求简单来说就是，输入一个字符串 s 和一个由不同单词组成的字典 wordDict，由你来判断上面输入的 s 是否可以通过只添加空格的方式（只能把字符串拆分成多个“单词”，但是不能调整字符顺序）拆分成由 wordDict 中的单词组成的一个“句子”。
不（jian）难写出了下面通过回溯来“从前到后”拼接所有合法结果的代码。
“从前向后”回溯但会超时的解法
func wordBreak(s string, wordDict []string) []string {
var ans []string
wd := make(map[string]struct{}, len(wordDict))
for _, word := range wordDict {
wd[word] = struct{}{}
}
bt140(0, s, "", wd, &ans)
return ans
}
func bt140(start int, s, currStr string, wd map[string]struct{}, ans *[]string) {
if start == len(s) {
*ans = append(*ans, currStr)
return
}
newStr := currStr
for i := start; i < len(s); i++ {
cs := s[start : i+1]
if _, ok := wd[cs]; !ok {
continue
}
if start != 0 {
cs = " " + cs
}
newStr += cs
bt140(i+1, s, newStr, wd, ans)
newStr = currStr
}
}但是无奈地发现单纯通过回溯的方式“从前向后”拼接符合要求的单词是没办法通过下面这个测试例的。无论怎么优化都超时，这是最致郁的。
s :="a...73a...aba...73a...a"
wordDict := []string{"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"}上面测试例中长达 140 多的输入字符串长度必然会让代码长时间卡在对第 75 个字符 b 判断失败之后的递归上。打开力扣评论区看到大半都在吐槽这个测试例我就放心了。除此之外还有很多评论在说可以根据第 139 题的结论，先对 140 的输入 s 判断一下是否能分割成句子，然后在真正的进行分割就可以通过。抱着试一试的心态，先把 139 题用最通俗的方式 AC 了，索性先看下 139 题。
使用第139题“从后向前”回溯的解法优化超时问题
大体思路就是使用回溯“从后往前”找满足要求的分割方式：每层判断当前起始位置 start 开始是否可以组成的单词，如果可以就把当前这个单词和 s “后面”部分每个满足要求的分割拼接在一起，直到从 start 为 0 的时候找到的单词也被拼接到结果中。具体代码如下。
func wordBreak(s string, wordDict []string) bool {
wd := make(map[string]struct{}, len(wordDict))
for _, s := range wordDict {
wd[s] = struct{}{}
}
return breakable(s, wd)
}
func breakable(s string, wd map[string]struct{}) bool {
mem := make(map[int]bool, len(wd))
var dfs func(start int) bool
dfs = func(start int) bool {
if _, ok := mem[start]; ok {
return mem[start]
}
if start == len(s) {
return true
}
for i := start; i < len(s); i++ {
_, ok := wd[s[start:i+1]]
if ok && dfs(i+1) {
mem[start] = true
return true
}
}
mem[start] = false
return false
}
return dfs(0)
}在最开始的 140 题目的解法中 wordBreak 函数里加入上面 breakable 函数先判断输入字符串能不能被正确分割，代码如下。
func wordBreak(s string, wordDict []string) []string {
var ans []string
wd := make(map[string]struct{}, len(wordDict))
for _, word := range wordDict {
wd[word] = struct{}{}
}
if !breakable(s, wd) {
return ans
}
bt140(0, s, "", wd, &ans)
return ans
}直接使用“从后向前”的回溯方式
上面使用 139 题答案帮助判断的方式不仅可以 AC，而且最吊诡的是这个“组合”解法竟然能拿双百。想象一下如果面试的时候真的被问到这道题的话，如果给出这样的结果还是显得有些太奇怪了。毕竟针对测试例单独做优化这种路子有点野，除非遇到一个野生面试官，否则这种接法不会让他满意。
既然已经选择了回溯，就用回溯最常用的记忆化优化一下吧。因为“从前向后”的方式我暂时想不到方便的记忆化实现方式（如果你知道怎么做的话请在评论里告诉我），参考了别人的答案还是用了“从后向前”的方式来做。简单来说，就是记忆从某个 start 起到 s 结束所有的正确分割，实现可以参考下面的代码。
func wordBreak(s string, wordDict []string) []string {
sz := len(wordDict)
wd := make(map[string]struct{}, sz)
mem := make(map[int][]string, sz)
for _, word := range wordDict {
wd[word] = struct{}{}
}
var dfs func(start int) []string
dfs = func(start int) []string {
if _, ok := mem[start]; ok {
return mem[start]
}
var ret []string
if start == len(s) {
return ret
}
for i := start; i < len(s); i++ {
w := s[start : i+1]
if _, ok := wd[w]; !ok {
continue
}
sfxs := dfs(i + 1)
// s 中的最后一个可匹配的 word 就不需要再加空格了
if i+1 == len(s) {
ret = append(ret, w)
}
for _, sfx := range sfxs {
ret = append(ret, w+" "+sfx)
}
}
mem[start] = ret
return ret
}
return dfs(0)
}Review
这周一起回顾一下 Go 官方介绍 GOGC 的文章：Getting to Go: The Journey of Go's Garbage Collector。
文章是 2018 年 7 月 在 Symposium on Memory Management (ISMM) 中的一次演讲的 PPT，可以算是目前为止官方对 Golang GC 历史最全面的一次介绍。下面是我对文中关于 GC 发展史主要内容的总结。
先说结论，目前 Golang 的 GC 算法是参考了 Dijkstra 的这篇论文 On-the-Fly Garbage Collection: An Exercise in Cooperation 来实现的。目前的 GC 是基于三色标记算法的，无分代，无碎片搬移，并使用了混合写屏障，存在微秒级别的 STW（Stop The World） 的，与业务逻辑并行执行的垃圾回收算法。
具体的故事还是从 2014 年开始说起，那时候的 GC 几乎是 Go 被吐槽最多的点，这已经严重拖累了 Go 的发展。这也是作者 Rick Hudson 刚来到 Go 团队时的情况，作者和其他开发人员一起制定了可实现的短期目标：没有读屏障的并行 GC.
Go 开发团队最终选择了“三色标记+并行执行+GC特殊阶段才开启写屏障”的实现，具体实现中还会使用“GC Pacer”来控制内存申请速度和内存标记速度，比如防止内存申请速度长期比标记速度快导致的“标记不完”的问题。
经过一番努力在 Go1.5 版本中（首次使用上述 GC 算法，在此之前写屏障会在 GC 时全程开启），经过线上服务的验证，垃圾回收延迟（原文中 GC latency）从 300-400 毫秒（ms）降低到了 30-40 毫秒。
1.6 版本中，延迟又被降低到了 5 毫秒以内。
1.8 版本中，延迟又又被降低到了 1 毫秒以内。
1.10 ……
至此作者认为 Go 终于摘掉了“GC 太垃圾”的帽子。在整个优化和提升的过程中，作者也客观的提到了 Go 团队所做出的取舍：为了编译速度放弃 ROC（Request Oriented Collector），为了吞吐量放弃分代（generational GC），等等。
最后作者表达了对未来 Go 发展的期待：保持性能的前提下提高可靠性，维持现有的 GC 模型，继续优化逃逸分析，优化写屏障，同时希望能够吃上未来五年内存性能发展所带来的红利（因为 GC 是 non-copying?）。
Tip
这周的 Tip 想聊一个经常被问到的问题：“return 和 defer 哪个先执行？”
先说结论吧：首先，编译器读到 defer 时对 defer function 的参数求值，这时会拷贝 defer function 的参数； 然后，程序执行到 return 时先将返回值保存到栈里；随后，按照后进先出的顺序执行之前保存好的 defer function；最后，函数退出并处理返回值。
如果这道题被问到的时候是结合代码的话，那么一定会涉及到 defer function 参数求值以及值传递引用传递的问题（虽然项目中并不推荐这样使用）。以上的这种问题，直接看官方的这个 https://blog.golang.org/defer-panic-and-recover 就可以完全解决了。文中最为关键的三句话，摘抄在这里。
- A deferred function's arguments are evaluated when the defer statement is evaluated.
一个 defer function 的参数在 defer 语句被求值（我理解是编译器读到这句时）的时候就已经被求值了。 - Deferred function calls are executed in Last In First Out order after the surrounding function returns.
defer function 在其外层函数 return 后才执行，且执行顺序是后进先出。 - Deferred functions may read and assign to the returning function's named return values.
defer function 可以对函数的有名返回值进行读取和赋值操作。
最后的最后，特别提醒一个值得注意的问题，就是 defer function 参数中如果出现了指针类型的话，一定要特别关注 defer function 是否会改变指针指向的值。
这个问题就聊到这里吧，如果你觉得我的观点存在任何问题，请随时在评论区指出来。
Share 灵光一闪
最近一直在看 GOGC 相关的东西，包括一些官网文档和大神们提炼的文章，越看越想深入去研究细节。结果就是陷入茫茫细节的海洋，逐渐忘了最开始想看什么内容。这个过程很像 DFS，但问题是可能深入的分支非常深，同时越深入的内容难度也会越大，导致花了非常多精力和时间之后还是没有一个整体的认知。或许学习的过程在最开始可以像 BFS 一样，先了解整体，再逐层深入，最后需要深度的时候在选择一个或者几个关键点深入学下去。
俗话说，细节是魔鬼（The devil is in the detail）。细节可能最后是无法避免的，接触魔鬼之前多学几样驱魔之术，应该比单纯靠勇气的结果好上不少。
以上。
有疑问加站长微信联系（非本文作者）
本文来自：Segmentfault
感谢作者：casmo澎湃哥
查看原文：ARTS 第3周| LeetCode 140 Word Break| Go GC 历史| return defer 哪个先执行
