乍听之下,不无道理;仔细揣摩,胡说八道

0%

什么是尾递归

如果一个函数在定义时引用了自身,那么这个函数就是一个递归函数。例如我们所熟知的阶乘就可以通过递归函数的形式予以定义

1
2
3
4
(defun fact (n)
(if (<= n 0)
1
(* n (fact (1- n)))))

在if语句的备选路径上,正在定义的函数fact被自身所调用,因此fact就是一个递归函数了。递归有一类较为特殊的形式,叫做尾递归,它们的特征是递归函数的调用位于被定义函数的最后一个步骤。也就是说,这个递归调用的返回值也就是整个函数调用的返回值,后面不再有其它的计算步骤了。例如实现了辗转相除法的下面这个函数就是尾递归的

1
2
3
4
(defun my-gcd (a b)
(cond ((zerop a) b)
((zerop b) a)
(t (my-gcd b (mod a b)))))

此处命名为my-gcd,是因为在Common Lisp中已经预置了一个叫做gcd的函数了

什么是尾递归优化

递归调用其实也就是函数调用,每一次调用都需要保存当前的执行上下文(寄存器的值、程序计数器的值等信息)并压入栈中。如果递归调用得非常深,那么很可能将栈空间消耗殆尽导致程序崩溃,因此很多时候都会选择使用循环来实现用递归实现的效果。尾递归形式的一个优势,就在于编译器可以对其进行优化,使得原本需要添加一个栈帧的函数调用操作,直接重用当前的调用中所使用的栈帧即可。这样一来,递归函数的调用就不会无节制地消耗栈空间了。

另一种对尾递归进行优化的方式,则是将其改写为【赋值】与【跳转】。例如对于上面的my-gcd函数,可以改写为如下形式

1
2
3
4
5
6
7
8
9
(defun my-gcd (a b)
(tagbody
rec
(cond ((zerop a) (return-from my-gcd b))
((zerop b) (return-from my-gcd a))
(t (progn
(psetf a b
b (mod a b))
(go rec))))))

如何在Common Lisp中实现

如果要使用递归的形式定义一个计算列表长度的函数,那么很可能会写出这样子的代码

1
2
3
4
(defun my-length (lst)
(if (null lst)
0
(1+ (my-length (rest lst)))))

采用累加器的思路,可以将上述函数改写为下面的尾递归形式

1
2
3
4
(defun my-length (lst acc)
(if (null lst)
acc
(my-length (rest lst) (1+ acc))))

对于第二个版本的my-length函数,同样可以手动改写为基于【赋值】和【跳转】的实现形式,结果如下

1
2
3
4
5
6
7
8
9
(defun my-length (lst acc)
(tagbody
rec
(if (null lst)
(return-from my-length acc)
(progn
(psetf lst (rest lst)
acc (1+ acc))
(go rec)))))

你可能已经注意到了,my-gcdmy-length函数的改写都是很有规律的,甚至可以通过一个宏来帮助我们自动完成这种变换。这个宏所需要做的事情其实只有三件:

  1. 将原本的定义中的函数体包裹在一个tagbody
  2. 将原本作为返回值的表达式包裹在一个return-from
  3. 将递归调用的表达式改为按顺序执行的psetfgo的组合

为了降低一下实现难度,第二点暂时就不处理了,函数的实现者必须手动编写return-from语句。因此,如果只考虑首尾两个条件,首先,可以考虑实现第三条,将函数体内的递归调用修改为prognpsetfgo的组合。要实现这个变换,可以使用macrolet,如下

1
2
3
4
5
6
7
8
9
10
(defun my-length (lst acc)
(tagbody
rec
(macrolet ((my-length (&rest args)
`(progn
(psetf ,@(mapcan #'list '(lst acc) args))
(go rec))))
(if (null lst)
(return-from my-length acc)
(my-length (rest lst) (1+ acc))))))

为了自动生成上面的代码,我编写了这样的一个宏

1
2
3
4
5
6
7
8
9
10
(defmacro define-rec (name lambda-list &body body)
(let ((rec (gensym)))
`(defun ,name ,lambda-list
(tagbody
,rec
(macrolet ((,name (&rest exprs)
,``(progn
(psetf ,@(mapcan #'list ',lambda-list exprs))
(go ,',rec))))
,@body)))))

利用上面这个宏编写一个计算列表长度的尾递归形式的函数,代码如下

1
2
3
4
(define-rec my-length (lst acc)
(if (null lst)
(return-from my-length acc)
(my-length (rest lst) (1+ acc))))

利用macroexpand-1或者是SLIME提供的展开一次宏的调试功能,在我的及其上得到的代码如下

1
2
3
4
5
6
7
8
9
10
(DEFUN MY-LENGTH (LST ACC)
(TAGBODY
#:G937
(MACROLET ((MY-LENGTH (&REST EXPRS)
`(PROGN
(PSETF ,@(MAPCAN #'LIST '(LST ACC) EXPRS))
(GO ,'#:G937))))
(IF (NULL LST)
(RETURN-FROM MY-LENGTH ACC)
(MY-LENGTH (REST LST) (1+ ACC))))))

跟上面手写的代码没有太大的差别,并且用于计算所得到的列表长度也是正确的。那么如何验证这个函数是采用了【赋值】和【跳转】的机制来完成运算的呢?可以借助Common Lisp提供的trace函数。如果使用的真实执行递归调用的my-length函数的定义,那么执行(trace my-length)后运行(my-length '(1 2 4 5) 0),在我的机器上会输出如下内容

1
2
3
4
5
6
7
8
9
10
11
12
CL-USER> (my-length '(1 2 4 5) 0)
0: (MY-LENGTH (1 2 4 5) 0)
1: (MY-LENGTH (2 4 5) 1)
2: (MY-LENGTH (4 5) 2)
3: (MY-LENGTH (5) 3)
4: (MY-LENGTH NIL 4)
4: MY-LENGTH returned 4
3: MY-LENGTH returned 4
2: MY-LENGTH returned 4
1: MY-LENGTH returned 4
0: MY-LENGTH returned 4
4

而如果是使用define-rec宏定义的my-length,求值同样的表达式的输出为

1
2
3
4
CL-USER> (my-length '(1 2 4 5) 0)
0: (MY-LENGTH (1 2 4 5) 0)
0: MY-LENGTH returned 4
4

显然,这当中没有递归的函数调用,my-length确实不需要调用自身。

全文完

在UC就职时养成了一个习惯,就是将自己所参与的项目的源代码都存放在一个名为uc的目录下。换了工作之后这个习惯仍然保留下来了,只不过原本名为uc的目录现在改名了(假设这个目录叫做work)。在新公司参与的项目比较多,因此在这个work目录下有许多的子目录,大致上的结构如下

1
2
3
work/
|-- A/
|-- B/

其中A和B分别表示一个项目的源代码目录。在work目录下存放的直接是A和B两个项目的目录。work目录本身是放置在~/src/这个目录下的,因此项目A和B的完整根目录路径是~/src/work/A/~/src/work/B/。由于参与的项目比较多,经常需要在几个项目间交替着编码,因此经常会在终端键入下面的指令

1
2
cd ~/src/work/A/ # 或者
cd ~/src/work/B/

不得不说这样确实是非常的麻烦,因此我很快就定义了一个shell函数来简化这串命令,这个shell函数的定义如下

1
2
3
4
5
6
7
8
function she() {
dir=${1}
target="/home/liutos/src/work/${dir}"
if [ -d "${target}" ]; then
cd "${target}"
return
fi
}

有了这个辅助工具后,要切换到项目A和B中就简单多了,只需要输入

1
2
she A # 或者
she B

即可。但一使用起来就会发现,原本直接使用cd命令时所能享用的目录名补全功能没有了!绝大多数情况下补全功能是非常有用的,为此打算动手为she函数配备一个目录名的补全功能。显然自定义命令行补全的想法已经有前人实践过了,略加搜索就可以找到这么一篇指南。模仿文章中的方法,我先是写了下面的代码骨架

1
2
3
4
5
_she() {
local cur
_get_comp_words_by_ref cur
}
complete -F _she she

我的想法是只要当前的输入能够作为work下的一个目录名字的前缀,那么就认为这个子目录是本次补全的目标。为此,我需要先获取到work目录下的所有子目录的名称。利用ls命令可以做到这一点,同时为了便于处理,在这里将ls返回的文件名列表作为数组保存起来。修改后的_she函数的代码如下

1
2
3
4
5
6
_she() {
local cur
local dirs
_get_comp_words_by_ref cur
dirs=($(ls ~/src/work/))
}

现在,只要遍历${dirs}并找出第一个以用户输入的${cur}为名字前缀的目录即可。最终_she函数的定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
_she() {
local cur
local dirs
_get_comp_words_by_ref cur
dirs=($(ls ~/src/work/))
for dir in ${dirs[@]}
do
case ${dir} in
${cur}*)
COMPREPLY="${dir}"
return 0
;;
esac
done
}

主流的编程语言中,表示出现错误的手段不外乎两种:

  • 函数调用返回错误码
  • 函数调用抛出异常

C语言就属于前者,它的fopen(3)函数在成功打开文件时返回一个FILE指针,失败时返回NULL,并将错误代码写入全局变量errno;Ruby语言属于后者,它的File.open方法在找不到文件时抛出ENOENT的异常,在File.open之外包裹一层begin…rescue…end即可捕捉其抛出的异常。

Common Lisp的错误机制叫做状况系统(Condition System),与异常机制相似,可以实现抛出异常(使用函数error)和捕捉异常(使用宏handler-case)。但与其它语言的异常机制不同的地方在于,状况系统有一种名为RESTART的特性,能够由使用者、或者由代码决定是否要、以及如何从错误中恢复过来。听起来很别致也很诡异,不妨继续往下看。

假设我有一个Web框架,它提供了将日志记录到文件中的功能。这个功能需要先调用名为init-logger的函数进行初始化,该函数实现如下

1
2
3
4
5
(defun init-logger ()
(with-open-file (s "/tmp/log/web.log"
:direction :output
:if-exists :supersede)
(format s "Logger module starting...")))

这个函数被框架的初始化代码所调用,如下

1
2
3
4
5
6
7
(defun init-framework ()
(format t "Framework starting...~%")
(init-plugin))

(defun init-plugin ()
(format t "Plugins starting...~%")
(init-logger))

而框架的初始化代码则由应用的初始化代码所调用,如下

1
2
3
(defun init-app ()
(format t "Application starting...~%")
(init-framework))

如果在目录/tmp/log不存在时调用init-app函数,我将会收到一个错误,说明其无法找到/tmp/log/web.log这个文件。为了避免错误打断了应用的正常启动流程,可以让init-app函数负责创建这个用于存放日志文件的目录。将init-app函数改写为如下形式

1
2
3
4
(defun init-app ()
(format t "Application starting...~%")
(ensure-directories-exist "/tmp/log/")
(init-framework))

尽管这种做法确实可行,但它导致应用层的代码(init-app函数)必须了解位于底层的日志模块的实现细节。直觉告诉我这样子是不对的,框架的事情应该由框架本身提供方案来解决。借助Common Lisp的restart功能,框架确实可以对外提供一种解决方案。

首先需要主动检测用于存放日志文件的目录是否存在。借助UIOP这个包可以写出如下代码

1
2
3
4
5
6
7
8
(defun init-logger ()
(let ((dir "/tmp/log/"))
(unless (uiop:directory-exists-p dir)
(error 'file-error :pathname dir))
(with-open-file (s (format nil "~Aweb.log" dir)
:direction :output
:if-exists :supersede)
(format s "Logger module starting..."))))

接着,init-logger需要主动为调用者提供目录不存在的问题的解决方案,一种办法就是当这个目录不存在时,可以由调用者选择是否创建。使用Common Lisp的restart-case宏,我将init-logger改写为如下形式

1
2
3
4
5
6
7
8
9
10
11
12
13
(defun init-logger ()
(let ((dir "/tmp/log/"))
(restart-case
(unless (uiop:directory-exists-p dir)
(error 'file-error :pathname dir))
(create-log-directory ()
:report (lambda (stream)
(format stream "Create the directory ~A" dir))
(ensure-directories-exist dir)))
(with-open-file (s (format nil "~Aweb.log" dir)
:direction :output
:if-exists :supersede)
(format s "Logger module starting..."))))

此时如果调用第一版的init-app函数,那么init-logger仍将抛出异常(类型为file-error与之前一样)并将我带入到SBCL(我用的是SBCL)的调试器中,但看到的内容会稍有不同

1
2
3
4
5
6
7
8
error on file "/tmp/log"
[Condition of type FILE-ERROR]

Restarts:
0: [CREATE-LOG-DIRECTORY] Create the directory /tmp/log ;; <- 新增了这一行
1: [RETRY] Retry SLIME REPL evaluation request.
2: [*ABORT] Return to SLIME's top level.
3: [ABORT] abort thread (#<THREAD "new-repl-thread" RUNNING {1001F958A3}>)

在Restarts中新增了名为create-log-directory的一项,这正是在init-logger中通过restart-case定义的新的”恢复措施“。我输入0触发这个restart,Common Lisp会回到它被定义的restart-case宏相应的子句中执行其中的表达式,也就是调用CL:ENSURE-DIRECTORY-EXIST函数创建/tmp/log。

如果总是希望执行CREATE-LOG-DIRECTORY这个选项来创建存放日志文件的目录,可以直接在代码中指定,只需要配合使用Common Lisp的handler-bindinvoke-restart函数即可,最终init-app函数的实现如下

1
2
3
4
5
6
7
(defun init-app ()
(format t "Application starting...~%")
(handler-bind
((file-error #'(lambda (c)
(declare (ignorable c))
(invoke-restart 'create-log-directory))))
(init-framework)))

在战舰少女贴吧里,偶尔能看到的一个说法叫做“这活动我用脚打都能过”,意思是活动关卡很容易(实际上有时候并非真的那么简单,仅仅是调侃)。在安装mysql这件事情上,也有用脚安装和用手安装两种。

典型的用脚安装就是使用系统的包管理器。例如在我的LinuxMint系统中,在shell中键入下列命令就可以装上mysql

1
sudo apt-get install mysql-server

遗憾的是,包管理器并不是任何时候都可用的。举个例子:以前在UC,研发团队是可以申请到一些机器用于分配给开发人员使用的,但如果要在上面使用数据库,那么多半需要开发人员自己动手部署。此外,只要掌握了手动部署单个mysql实例的方法,就可以轻松地在一台机器上部署多个mysql实例了,而这正是我最近需要完成的一个任务。为了方便自己很久之后查阅,也为了帮到其他有此类需求的程序员,我写了这篇手动安装的指南。

初始化数据库

安装mysql的第一步,是创建数据库运行所需要的一系列文件。在5.7.6版本之前的mysql中,这个过程是由mysql_install_db这个脚本完成的。在5.7.6的发行版中,这个功能被集成到了mysqld中,下面的操作也是基于mysqld实现的。mysqld提供了执行用于初始化的命令行选项:

  • –initialize
  • –initialize-insecure

–initialize-insecure会为数据库的root账户设置空的密码,方便稍后登录,因此将选用这一个初始化的方法。

为了初始化数据库,还需要指定mysql的安装目录和存放数据文件的目录。安装目录即mysql的二进制安装包解压缩后生成的目录,而存放数据文件的目录则可以自由选择。这两个路径分别传递给mysqld的–basedir和–datadir参数。为了方便起见,也为了避免mysqld启动后读取了已存在的mysql配置文件造成干扰,我将这两个参数写到了配置文件中。在我的机器上配置文件路径是~/local/mysql/my.cnf,内容如下

1
2
3
[mysqld]
basedir = /home/liutos/local/mysql
datadir = /home/liutos/data/mysql/data

需要注意的是,根据官方文档的说明,datadir所设置的目录,必须为一个尚不存在的目录或者是一个空目录。在我的系统中,/home/liutos/data/mysql/data是一个尚未创建的目录。

现在可以进行初始化了。因为在我的系统上解压缩后的目录为~/local/mysql,因此在shell中执行的命令为

1
2
cd ~/local/mysql/
./bin/mysqld --defaults-file=/home/liutos/local/mysql/my.cnf --initialize-insecure --user=`whoami`

启动数据库服务

完成初始化后就可以启动mysqld了。启动的命令为

1
./bin/mysqld_safe --defaults-file=/home/liutos/local/mysql/my.cnf --user=`whoami` > /dev/null 2>&1 &

由于在我的系统中,已经使用包管理器安装了mysql服务并且正在监听着3306端口,为此必须修改即将启动的mysqld进程所监听的端口。监听的端口号可以通过配置文件来指定,修改后的配置文件如下

1
2
3
4
[mysqld]
basedir = /home/liutos/local/mysql
datadir = /home/liutos/data/mysql/data
port = 3307 # 新增该行

现在可以执行刚才的启动命令了。成功启动后,使用netstat -apn | grep '3307'应当可以看到类似下文的输出

1
tcp6       0      0 :::3307                 :::*                    LISTEN      30898/mysqld

登录数据库

一番波折,终于可以登录了。因为当初是使用–initialize-insecure执行初始化的,root账户没有登录密码,因此在shell中键入下列命令登录

1
mysql -u root --skip-password -h 127.0.0.1 -P 3307

登录后建议为root账户设置登录密码。例如,我要给root账户设置密码为1234567,就执行下列SQL语句

1
ALTER USER 'root'@'localhost' IDENTIFIED BY '1234567';

UNIX socket配置

按照上述步骤启动后,mysqld会在系统的/tmp目录下创建一个mysql.sock文件。此时如果再按照上述步骤是无法启动另一个mysql实例的,因此每一个mysqld必须使用单独的.sock文件。这可以通过配置文件来实现,在我的系统上的配置如下

1
2
3
4
5
[mysqld]
basedir = /home/liutos/local/mysql
datadir = /home/liutos/data/mysql/data
port = 3307
socket = /home/liutos/local/mysql/mysql.sock # 新增该行

题外话

大一的时候为了装13就自己去图书馆借了很多讲解和CS有关却又还没有教或者不会教的内容的书来看,其中就有数据结构那一类的。不过我已经忘记了当时去图书馆借到的是什么样子的书了,只知道书的封面是蓝色的(要是有空的话去图书馆找找就可以知道了=。=)。不过说到数据结构方面的书,在国内大部分和计算机或者信息技术沾边的专业的学生中,比较广为人知的应该既不是《算法导论》,也不是《算法概论》,而是编者为严蔚敏的那本《数据结构C语言描述》吧。我也有幸看过,并且印象中那时候觉得那本教材还是不错的。只不过现在道行稍微有点高了,就开始有点鄙视当初习得技能的恩师了——哦,有种过河拆桥的感觉。

百度面试题

第一次去百度面试时,面试官看起来和蔼可亲,同样给出的问题也很和蔼可亲。当时的问题有三道,第一道是让我随意写一个二叉树的遍历的代码,我挑了个深度优先搜索来写,因为我觉得这货算得上是最容易写的代码之一了。然后面试官就让我用广度优先搜索再写一遍,我就再写了一次。说真的,队列那一部分的处理还真是让人头大,尤其是我居然稀里糊涂地把队列的处理和栈的处理混淆在一起了,结果代码看起来也是稀里糊涂的。要不是面试官大慈大悲耐心地和我商量着来修改,我可能就没有遇到第三题的机会了。不过终究第二题还是安全过关了,之后就是第三题了:给广度优先搜索增加一个返回所找到的关键字在二叉树的哪一层的功能。

老实说,听到题目的当即我就想到了一种最最最简单的办法,就是修改二叉树的定义,给它增加一个数据字段来存储每一个节点究竟位于第几层就可以了嘛,唉真是简单得无趣啊=。=不过面试官说不允许这样做,那好,我再换一种办法,就是增加一个新的队列来存储每一个进入队列的节点究竟是位于哪一层的。因为一开始肯定是从第一层开始的,所以只要中间的每一个节点都不要漏掉,那么根据父节点的层数就可以推知直接的子节点的层数,那么在将每一个节点入队列的时候都有办法知道它们是在哪一层的。嗯,这个办法也很好,不过面试官也不允许增加新的队列,呃。。你这不是存心刁难我么!还好,把队列的版本稍微修改一下就可以去掉队列了,不过要增加广度优先搜索的实现函数的参数。

第三个版本

首先要明确这个函数的参数与返回值究竟是怎样的。因为当时这个功能是用C语言来实现的,所以只允许函数调用有一个返回值。在一开始写的两个版本中函数的返回值是所找到的二叉树中的节点,所以在第三个版本中也依然返回所查找到的节点或者是在找不到的时候返回C语言中的空——NULL。那么这样一来节点所对应的深度的信息只能通过下面的两种方法来返回了:

  • 全局变量
  • 传出参数

我选择了第二种,因此查找功能需要增加一个传出参数depth,它的类型声明是int *。因此查找功能的入口函数的整体类型声明为:

TreeNode dfs_search_tree(Tree tree, char target, int *depth)

(我觉得标识符取得还不错,不用解释了吧→_→)那么dfs_search_tree这个函数要如何实现具体的功能呢?现在我们是为了要在队列的版本上进行修改来实现查找功能的,那么原本需要使用队列来存储的深度信息现在应该交给函数的参数来存储,但是这个参数不能添加到入口函数中,因此我们需要一个辅助函数,就叫做dfs_search_tree_aux函数好了,它至少需要上面的函数所拥有的三个参数,并且还需要一个用来传递而不是用来返回的深度的信息,不妨声明为int *nd。

试想一下,如果我们在处理第i层的一个节点,那么显然可以知道它的左右子树的根结点如果存在,必定会位于第i+1层,因此在广度优先搜索的函数递归调用的时候,nd参数的传递是以加一的形式进行的,即遍历子树的时候nd必定要比测试当前节点的时候加一。不过实际上这样子是不可行的,因为我们不是在测试了父节点之后就立即递归调用函数来测试两个子节点,在测试父节点的时候,只是把两个子节点给放进了队列罢了,因此没有办法通过简单地直接加一的方法来传递深度参数。我们需要的信息是,现在这个节点和上一个节点到底是不是在同一层。

确定是否在同一层的一个办法,是知道每一层的节点的数目。例如第一层显然只能有一个节点,因此当测试了第一个节点后就可以知道第一层已经测试完了,那么接下来的函数调用的nd参数的值就至少应该增加一,并且应该把表示一层的节点个数的参数设置为第二层的对应值。第二层的节点个数可以利用遍历第一层的时候来得到。例如对于第i层的节点,如果每一个节点都有两个子节点,那么第i+1层的节点数目就是第i层的两倍,对于其它情况也可以很简单地推算出来。因此,我们需要额外的两个参数current_count和next_count,来分别存储当前层剩下的节点数目以及下一层目前所探测到的节点数目。现在,我们可以写出辅助函数的原型了:

TreeNode dfs_search_tree_aux(char target, int depth, int *nd, Queue queue, int current_count, int next_count)

其中没有和dfs_search_tree一样的tree参数,因为在广度优先搜索中,树的节点是存储在队列queue中的。dfs_search_tree_aux这个函数的逻辑是这样子的:

  1. 先看看队列是否为空。如果是就说明节点都已经测试完了,仍然没有找到目标节点,所以返回NULL;
  2. 从队列中取出最早进入的节点。
  3. 既然已经开始测试新的节点,那么当前层的剩余节点数就少了一个,因此current_count要自减一;
  4. 测试节点的关键字。如果是一致的就先设置传出参数nd为depth,然后返回对应节点的指针;
  5. 如果测试失败,那么就说明函数需要继续递归调用下去了。这时候需要先决定current_count和next_count的值。
  6. 如果current_count为0,也就是说这一层没有节点剩下了,那么就让depth加一,把当前的节点数目(current_count)设置为下一层的节点数目(next_count),然后下一层的节点数目重新归零。
  7. 接下来,测试左子树是否为空。如果非空,就把当前节点的左子树根结点入队,并给next_count加一。同样的,右子树也是类似的处理办法。
  8. 最后,递归调用辅助函数本身。

最后给出代码链接好了:https://github.com/Liutos/CLab/blob/master/binary_tree/prototype.c