ARTS第三周

1 概述

ARTS 是耗子叔发起的编程挑战：

每周完成一个ARTS：每周至少做一个 leetcode 的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的技术文章。（也就是 Algorithm、Review、Tip、Share 简称ARTS）

2 Algorithm

2.1 Linked List Cycle

问题描述：

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

见141-Linked List Cycle。

难度：简单。

问题求解：

思路很简单：利用快慢两个指针，慢指针每次走一步，快指针每次走两步，如果快指针能追上慢指针，则证明有环，反之无环。由于快指针每次比慢指针多走一步，如果有环一定可以追上。

实现：

Java 实现见github，耗时 0ms。

2.2 Merge k Sorted Lists

问题描述：

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

见23-Merge k Sorted Lists。

难度：困难。

问题求解：

需要每次从 n 个 list 中取出最小值插入新的 list。
由此，可以使用一个最小堆，每次取堆顶的值即可。构造新元素插入新的 list。
如果被取出的元素有下一个元素，则将其放入最小堆。直到所有列表元素都遍历完成且最小堆中无元素。

实现：

Java实现见github，耗时 7ms。

3 Review

本周 review 是 medium 上一篇关于 go 语言中 defer 用法的文章。文章中介绍了 go 语言中 defer 的常见和不常见的用法。举了大量的示例。看完之后，我认为：

很多例子牵扯到 go 语法很细节的层面，实用性不大，例如在defer中修改函数返回值。
掌握常见的用法就已经足够，非编译器实现者深入下去性价比不高。当然你有兴趣，有时间另说😉。

我认为 defer 的最重要用法就是保证资源的释放（如文件，网络连接等），避免在每个返回路径上都写上释放资源的代码（繁琐且容易遗漏）。例如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func f1() {
    f, err := os.Open();
    if err != nil {
        // error handle
        return
    }

    defer f.Close()

    if condition1 {
        // ...
        return
    }

    if condition2 {
        // ...
        return
    }

    // ...
}

这里只需要写一次f.Close()，defer保证在函数返回前这行代码一定会被调用。

其次，defer可以用来处理panic异常：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func f2() {
    defer func () {
        if errRecover := recover(); errRecover != nil {
            // panic handle
            fmt.Println(errRecover)
            debug.PrintStack()
            return
        }

        // no error
    }()


    // ...
    panic("test")
}

recover的返回值是panic的参数，如果没有panic则返回nil。

另外，需要关注defer的一个使用问题：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func f3() {
	for i := 1; i < 10; i++ {
		f, err := os.Open(fmt.Sprintf("test%d", i))
		if err != nil {
			return
		}

		defer f.Close()

		// ...
	}
}

需要注意的是，defer代码是在函数返回前执行的，而不是在代码块结束时。在上面代码中，如果for循环之后还有其他比较耗时的代码，那么变量f占用的文件句柄就不能很快释放。可以使用闭包来改进：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func f3() {
	for i := 1; i < 10; i++ {
        func() {
            f, err := os.Open(fmt.Sprintf("test%d", i))
            if err != nil {
                return
            }

            defer f.Close()

            // ...
        }()
	}
}

这时，for循环中的代码在一个匿名函数中执行，该函数执行完成后f.Close就会被调用从而释放资源。

4 Tip

分享一个go generate的使用技巧。

我是一个游戏后端程序员，最近和平台对接行为日志规范。其中有一个资源获取和消耗日志，需要记录资源来源或去向的描述（比如通过日常任务获得，或者在用在武将升星上）。我们在编写功能的过程中就已经记录了日志，不过我们是通过一个自定义的常量数字来表示来源或去向的。定义获取或消耗途径的代码如下（为了描述方便，做了简化）：

1
2
3
4
5


const (
    LogTypeDailyMission = 1 // 日常任务
    LogTypeKnightStarup = 2 // 武将升星
    LogTypeKnightLayerup = 3 // 武将突破
)

这时，可以通过维护途径常量数字和描述的一个映射。在需要获取描述时，传入常量即可。如下所示：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// todo: 新增途径修改这里！！！
var mapLogType = map[uint32]string {
    LogTypeDailyMission: "日常任务",
    LogTypeKnightStarup: "武将升星",
    LogTypeKnightLayerup: "武将突破",
}

func GetLogMessage(logType uint32) string {
    if logMessage, exist := mapLogType[logType]; exist {
        return logMessage
    }

    return fmt.Sprintf("logtype(%d)", logType)
}

采用这种做法，以后每次添加一种新的途径，都需要修改mapLogType，很繁琐。后来，我想到了使用go generate来自动生成。

首先，定义一个新类型。将途径常量全改为新类型。在const头部加入go generate命令：

1
2
3
4
5
6
7
8


type LogType uint32

//go:generate stringer -type=LogType -linecomment
const (
    LogTypeDailyMission  LogType = 1 // 日常任务
    LogTypeKnightStarup  LogType = 2 // 武将升星
    LogTypeKnightLayerup LogType = 3 // 武将突破
)

执行这个转换需要stringer工具，该工具可以通过go get安装（自备梯子或者通过笔者搭建go开发环境这篇文章中介绍的方法安装）。

1

$ go get golang.org/x/tools/cmd/stringer

go get会将stringer安装到$GOPATH/bin目录中，将$GOPATH/bin放到系统path目录中，使stringer可以在任何目录执行。
然后在文件同目录下执行go generate命令，即可生成logsub_string.go文件：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


// Code generated by "stringer -type=LogType -linecomment"; DO NOT EDIT.

package main

import "strconv"

const _LogType_name = "日常任务武将升星武将突破"

var _LogType_index = [...]uint8{0, 12, 24, 36}

func (i LogType) String() string {
	i -= 1
	if i >= LogType(len(_LogType_index)-1) {
		return "LogType(" + strconv.FormatInt(int64(i+1), 10) + ")"
	}
	return _LogType_name[_LogType_index[i]:_LogType_index[i+1]]
}

现在，我们就可以定义一个LogType类型的变量，直接调用其String方法获取描述了。简便！优雅！
如果嫌每次执行go generate命令太烦的话，可以在 Makefile 中编写规则使其在编译代码时自动执行。

注意：

stringer默认使用常量名称作为描述，使用-linecomment标志可以指定其使用行后的注释。
stringer生成的文件名默认为类型名小写_string.go，可以通过-output=filename.go标志指定。

本周分享一篇孟岩老师的文章《刺激与回应之间存在一段距离，成长和幸福的关键就在那里》。我开始学习编程时，孟岩老师的文章教了我很多技术与方法。

在人类漫长的进化过程中，我们会对外界的刺激做很多应激反应（Reactive）—— 战或逃（Fight or Flight），这些应激反应可以帮助人类躲避外在危险，更好的保护自己。从进化的角度看，这些应激反应是为了完成生存和繁衍的任务，但并不能让我们更幸福、更自由。

如果我们能够感知外界的刺激，能够在本能的应激反应（Reactive）之前，给自己一段距离，选择合适的回应方式，我们就能找到更多的幸福和自由。

我相信很多人都有这样的体会：

当你在看书时，突然想拿起手机刷一下朋友圈，这是来自大脑的刺激。这时，你可以应激反应（Reactive），马上拿起手机刷一会儿。你也可以在觉知后给自己一段距离（Space），你知道短暂的愉悦后会很空虚，知道继续看书会有更大的愉悦感，于是你选择用继续看书来回应（Responsive）。

我非常喜欢这段话。相信很多人在回想自己的学习，生活和工作时，会有更深刻的体会。

这种状态不仅是关于学习，更是对生活的态度。这值得我们一生去寻找和学习！！！

文章目录