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

0%

序言

备考某等级考试的时候,在教材中碰到了几个一直不太理解的、关于硬盘的概念:磁道、柱面号、扇区。然而教材没有配图,无法直观地了解这些概念的物理形态。维基百科的硬盘词条页中倒是有一副不错的示意图,我截图搬运了过来

机械硬盘示意图

原图是一张SVG图片,本质上是一堆指令——也就是所谓的语绘啦。我是一个语绘爱好者,也想试试看能否用代码画一幅差不多的图出来。

在旧文《程序员特有的画图方式——语绘工具小入门》中,我演示过几款写代码画图的工具,但它们都不适合用来绘制几何图形,所以这次它们没有用武之地。

本来我想试试用MetaPost来画的,但鉴于“入门”了太多次,这次还是换点新花样吧。这一次,我用LaTeX+TikZ来画。

TikZ是什么及光速入门

著名的压泡面神器、麻将桌脚垫《TAOCP》的作者发明了TeX,知名的Raft竞品Paxos算法的作者在此基础上创造了LaTeX,它们都是程序员简历论文排版的好帮手。而TikZ则是如虎添翼地在LaTeX中实现了简单易懂的绘图功能的一个红包宏包(macro package,TeX的术语)。简而言之,TikZ自定义了一套“语言”,可以在用LaTeX编写的文档中画出各种图形。

百闻不如一见,我演示一下如何用TikZ画一条线段、一个圆,以及一段圆弧。先将下列的代码保存到一个文件three_in_one.tex

1
2
3
4
5
6
7
8
9
10
11
12
13
\documentclass{standalone}
\usepackage{tikz}
\usetikzlibrary{shapes.geometric, arrows}
\begin{document}
\begin{tikzpicture}[scale=2]
%% 画一条从原点指向(1, 1)的线段
\draw (0, 0) -- (1, 1);
%% 画一个以(1, 1)为圆心,半径为2的圆。
\draw (1, 1) circle (2);
%% 画一段以原点为圆心,半径为1,张开角度为30度的圆弧。
\draw (1, 0) arc (0:30:1);
\end{tikzpicture}
\end{document}

再使用xelatex将其编译成PDF文件(xelatex可以通过安装TeXLive 2020获得)

1
xelatex three_in_one.tex

此时便得到了three_in_one.pdf文件。为了可以在文章中显示,我用ImageMagick将其转换为PNG文件

1
convert three_in_one.pdf /tmp/three_in_one.png

最终的图片如下

简单,就像画一匹马一样简单。

现在该来试试用TikZ复刻维基百科上的硬盘示意图了。

来点同心圆

在原图中最引人注目的,当属那十几个同心圆了。简单起见,我只画六个圆。这六个圆的半径相差1ptpt是TikZ默认的长度单位),从3pt一直递增到8pt,它们的圆心都在坐标原点(0, 0)上。

1
2
3
4
5
6
7
8
9
%% 为了节省篇幅,只给出TikZ部分的代码。
\begin{tikzpicture}
\draw (0, 0) circle (3);
\draw (0, 0) circle (4);
\draw (0, 0) circle (5);
\draw (0, 0) circle (6);
\draw (0, 0) circle (7);
\draw (0, 0) circle (8);
\end{tikzpicture}

来点等分线

原图中有12根线段,将每一个圆等分成了全等的12份。从前一节的内容可知,要用\draw命令绘制线段,需要的是线段两端的坐标,那么这批坐标要怎么计算呢?尽管可以用三角函数计算出这些点的笛卡尔坐标,但在TikZ中可以用更方便的极坐标来指定这些点。

以原图中从X轴开始逆时针旋转遇到的第一条线段为例,它在半径为3pt的圆上的点的坐标为(30:3)(30是极坐标中的角度,3是半径长度),而在半径为8pt的圆上的点的坐标为(30:8),因此可以用\draw (30:3) -- (30:8)来画出这根线段。

通过调整其中的角度可以画出剩余的其它线段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
\begin{tikzpicture}
\draw (0, 0) circle (3);
\draw (0, 0) circle (4);
\draw (0, 0) circle (5);
\draw (0, 0) circle (6);
\draw (0, 0) circle (7);
\draw (0, 0) circle (8);

\draw (0:3) -- (0:8);
\draw (30:3) -- (30:8);
\draw (60:3) -- (60:8);
\draw (90:3) -- (90:8);
\draw (120:3) -- (120:8);
\draw (150:3) -- (150:8);
\draw (180:3) -- (180:8);
\draw (210:3) -- (210:8);
\draw (240:3) -- (240:8);
\draw (270:3) -- (270:8);
\draw (300:3) -- (300:8);
\draw (330:3) -- (330:8);
\end{tikzpicture}

来张色图

原图大致的骨架已经画完了,现在来尝试给它上色。在TikZ中,可以用\fill命令给一段封闭的曲线上色。比如用\fill[red] (0, 0) -- (1, 0) -- (1, 1) -- (0, 1) -- cycle可以将左下角在原点、边长为1pt的正方形涂成红色。

先给原图中的区域B上色。区域B是一个扇形,它由两根长度为8pt的半径和一段夹角为30度的圆弧构成。要描述这段封闭曲线,可以借助入门一节中介绍的arc命令。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
\begin{tikzpicture}
%% 给区域B上色。
\fill[blue] (0, 0) -- (30:8) arc (30:60:8) -- cycle;

\draw (0, 0) circle (3);
\draw (0, 0) circle (4);
\draw (0, 0) circle (5);
\draw (0, 0) circle (6);
\draw (0, 0) circle (7);
\draw (0, 0) circle (8);

\draw (0:3) -- (0:8);
\draw (30:3) -- (30:8);
\draw (60:3) -- (60:8);
\draw (90:3) -- (90:8);
\draw (120:3) -- (120:8);
\draw (150:3) -- (150:8);
\draw (180:3) -- (180:8);
\draw (210:3) -- (210:8);
\draw (240:3) -- (240:8);
\draw (270:3) -- (270:8);
\draw (300:3) -- (300:8);
\draw (330:3) -- (330:8);
\end{tikzpicture}

\fill命令那一行最后的cycle的意思,是让曲线回到起点组成一个封闭的形状。另外,\fill命令需要写在\draw命令之前,是为了避免蓝色颜料将区域内的圆弧给盖住了。

对于区域C和区域D,方法是一样的,只是描述封闭曲线的坐标不同罢了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
\begin{tikzpicture}
%% 给区域B上色。
\fill[blue] (0, 0) -- (30:8) arc (30:60:8) -- cycle;
%% 给区域C上色。
\fill[purple] (30:4) -- (30:5) arc (30:60:5) -- (60:4) -- (60:4) arc (60:30:4);
%% 给区域D上色。
\fill[green] (240:6) -- (240:7) arc (240:330:7) -- (330:6) -- (330:6) arc (330:240:6);

\draw (0, 0) circle (3);
\draw (0, 0) circle (4);
\draw (0, 0) circle (5);
\draw (0, 0) circle (6);
\draw (0, 0) circle (7);
\draw (0, 0) circle (8);

\draw (0:3) -- (0:8);
\draw (30:3) -- (30:8);
\draw (60:3) -- (60:8);
\draw (90:3) -- (90:8);
\draw (120:3) -- (120:8);
\draw (150:3) -- (150:8);
\draw (180:3) -- (180:8);
\draw (210:3) -- (210:8);
\draw (240:3) -- (240:8);
\draw (270:3) -- (270:8);
\draw (300:3) -- (300:8);
\draw (330:3) -- (330:8);
\end{tikzpicture}

给环形上色

聪明的读者也许已经发现了,区域A的环形没办法用这种方式来描述。不过没关系,只要将其视为上下半两部分,再分别上色即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
\begin{tikzpicture}
%% 环的上半部分
\fill[red] (4, 0) -- (5, 0) arc (0:180:5) -- (-4, 0) -- (-4, 0) arc (180:0:4);
%% 环的下半部分
\fill[red] (4, 0) -- (5, 0) arc (360:180:5) -- (-4, 0) -- (-4, 0) arc (180:360:4);
%% 给区域B上色。
\fill[blue] (0, 0) -- (30:8) arc (30:60:8) -- cycle;
%% 给区域C上色。
\fill[purple] (30:4) -- (30:5) arc (30:60:5) -- (60:4) -- (60:4) arc (60:30:4);
%% 给区域D上色。
\fill[green] (240:6) -- (240:7) arc (240:330:7) -- (330:6) -- (330:6) arc (330:240:6);

\draw (0, 0) circle (3);
\draw (0, 0) circle (4);
\draw (0, 0) circle (5);
\draw (0, 0) circle (6);
\draw (0, 0) circle (7);
\draw (0, 0) circle (8);

\draw (0:3) -- (0:8);
\draw (30:3) -- (30:8);
\draw (60:3) -- (60:8);
\draw (90:3) -- (90:8);
\draw (120:3) -- (120:8);
\draw (150:3) -- (150:8);
\draw (180:3) -- (180:8);
\draw (210:3) -- (210:8);
\draw (240:3) -- (240:8);
\draw (270:3) -- (270:8);
\draw (300:3) -- (300:8);
\draw (330:3) -- (330:8);
\end{tikzpicture}

润色一下

用macOS的“数码测色计”看了一下原图中各个区域的颜色的RGB值,区域A大概是(236, 133, 130)、区域B大概是(122, 127, 237)、区域C大概是(131, 132, 139)、区域D大概是(0, 151, 27)。接下来我让TikZ以这四种指定的颜色填充图中的四个区域,先用LaTeX的\definecolor命令定义四个新的颜色的名字。

1
2
3
4
5
%% 下列四行代码置于document环境之前
\definecolor{areaA}{RGB}{236,133,130}
\definecolor{areaB}{RGB}{122,127,237}
\definecolor{areaC}{RGB}{131,32,139}
\definecolor{areaD}{RGB}{0,151,27}

再替换掉\fill命令中的颜色名即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
\begin{tikzpicture}
%% 环的上半部分
\fill[areaA] (4, 0) -- (5, 0) arc (0:180:5) -- (-4, 0) -- (-4, 0) arc (180:0:4);
%% 环的下半部分
\fill[areaA] (4, 0) -- (5, 0) arc (360:180:5) -- (-4, 0) -- (-4, 0) arc (180:360:4);
%% 给区域B上色。
\fill[areaB] (0, 0) -- (30:8) arc (30:60:8) -- cycle;
%% 给区域C上色。
\fill[areaC] (30:4) -- (30:5) arc (30:60:5) -- (60:4) -- (60:4) arc (60:30:4);
%% 给区域D上色。
\fill[areaD] (240:6) -- (240:7) arc (240:330:7) -- (330:6) -- (330:6) arc (330:240:6);

\draw (0, 0) circle (3);
\draw (0, 0) circle (4);
\draw (0, 0) circle (5);
\draw (0, 0) circle (6);
\draw (0, 0) circle (7);
\draw (0, 0) circle (8);

\draw (0:3) -- (0:8);
\draw (30:3) -- (30:8);
\draw (60:3) -- (60:8);
\draw (90:3) -- (90:8);
\draw (120:3) -- (120:8);
\draw (150:3) -- (150:8);
\draw (180:3) -- (180:8);
\draw (210:3) -- (210:8);
\draw (240:3) -- (240:8);
\draw (270:3) -- (270:8);
\draw (300:3) -- (300:8);
\draw (330:3) -- (330:8);
\end{tikzpicture}

图文并茂

剩下的需要复刻的东西就是原图中的文字以及标注用的线了。线很容易画,只要规定了坐标后用\draw命令即可。比如说,我可以把四条线定义如下,其中的坐标和线段的长度纯粹是个人偏好

1
2
3
4
\draw (75:4.5) -- (75:9);
\draw (40:7.5) -- (40:9);
\draw (50:4.5) -- (50:9);
\draw (285:6.5) -- (285:9);

线画完了,再到每一根线的“终点”标上文字说明,这需要用到TikZ的node功能。用法很简单,就是在需要标注文字的坐标后,紧跟着关键字node,以及一段用花括号包裹的文本即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
\documentclass{standalone}
\usepackage{tikz}
\usepackage{xeCJK}
\setCJKmainfont{Songti TC}
\usetikzlibrary{shapes.geometric, arrows}
\definecolor{areaA}{RGB}{236,133,130}
\definecolor{areaB}{RGB}{122,127,237}
\definecolor{areaC}{RGB}{131,32,139}
\definecolor{areaD}{RGB}{0,151,27}
\begin{document}
\begin{tikzpicture}
%% 环的上半部分
\fill[areaA] (4, 0) -- (5, 0) arc (0:180:5) -- (-4, 0) -- (-4, 0) arc (180:0:4);
%% 环的下半部分
\fill[areaA] (4, 0) -- (5, 0) arc (360:180:5) -- (-4, 0) -- (-4, 0) arc (180:360:4);
%% 给区域B上色。
\fill[areaB] (0, 0) -- (30:8) arc (30:60:8) -- cycle;
%% 给区域C上色。
\fill[areaC] (30:4) -- (30:5) arc (30:60:5) -- (60:4) -- (60:4) arc (60:30:4);
%% 给区域D上色。
\fill[areaD] (240:6) -- (240:7) arc (240:330:7) -- (330:6) -- (330:6) arc (330:240:6);

\draw (0, 0) circle (3);
\draw (0, 0) circle (4);
\draw (0, 0) circle (5);
\draw (0, 0) circle (6);
\draw (0, 0) circle (7);
\draw (0, 0) circle (8);

\draw (0:3) -- (0:8);
\draw (30:3) -- (30:8);
\draw (60:3) -- (60:8);
\draw (90:3) -- (90:8);
\draw (120:3) -- (120:8);
\draw (150:3) -- (150:8);
\draw (180:3) -- (180:8);
\draw (210:3) -- (210:8);
\draw (240:3) -- (240:8);
\draw (270:3) -- (270:8);
\draw (300:3) -- (300:8);
\draw (330:3) -- (330:8);

\draw (75:4.5) -- (75:9) node {磁道};
\draw (40:7.5) -- (40:9) node {扇面};
\draw (50:4.5) -- (50:9) node {扇区};
\draw (285:6.5) -- (285:9) node {簇};
\end{tikzpicture}
\end{document}

需要留意的是,我在源代码开头的位置,引入了xeCJK宏包(\usepackage{xeCJK}),并且指定了中文内容用的字体为宋体(\setCJKmainfont{Songti TC}),这样才能成功编译。

至此,复刻算是完成了。

后记

本文只是管中窥豹,TikZ还可以画出其它更复杂更美轮美奂的图形,有兴趣的读者可以移步这里观赏。此外,TikZ也可以“编程”,比如下面的两行代码便足矣画出上文中12行代码才完成的等分线

1
2
\foreach \x in {0,30,60,90,120,150,180,210,240,270,300,330}
\draw (\x:3) -- (\x:8);

TikZ的更多潜力和乐趣,就由各位读者自己探索吧。

用Emacs的时候,我习惯将它分成“四个部分”

怎么弄的呢?一般是先按C-x 3分出左右两个window,再到各个window中用C-x 2分出上下两个window——这不是我的笔误,在Emacs的术语中,用来显示一个buffer的区域就叫做一个window。而常常被人们冠名为window的、最外层的窗体,则叫做frame

这样划分后,多次按下C-Tab(我把这个快捷键绑定到了命令other-window上),便可以按照左上、左下、右上、右下的顺序轮换当前聚焦的window了。

如果需要从其它window中复制内容到当前window中粘贴,操作会麻烦一点。以右上角需要左下角的内容为例:

  1. 按三次C-Tab换到左下角的window中——用快捷键是因为我不想去挪鼠标;
  2. kj上下移动光标到目标行——用kj是因为用了evil-mode插件(参见这篇文章);
  3. 复制内容,再按一次C-Tab回到原来的window中粘贴。

听起来可麻烦了。

好在Emacs有一个非常好用的插件,可以把第1和第2个步骤合在一起完成。

avy

这个非常好用的插件就是avy,它提供的avy-goto-line函数可以一步到位地完成上面的第1和第2个步骤。

用Emacs的包管理器就可以安装它

1
M-x package-install RET avy RET

接着要为命令avy-goto-line绑定一个喜欢的快捷键

1
(global-set-key (kbd "M-g f") 'avy-goto-line)

至此便可以在Emacs中愉快地使用M-g f来快速跳转到当前或其它window中的行了。百闻不如一见,我来演示一番。

avy-goto-line

众所周知,我用org-mode来跟踪自己的学习计划,还会将摸索过程中的一些半成品代码保存到org-mode的条目中。例如,我想要将左下角的window中的三个函数的定义,复制到右上角的代码块中去

于是我先按下M-g f,让avy为每一行赋予一个标记

因为希望切换到左下角的window的第一行,所以我先按下j

此时,在前一幅截图中不以字母j开始的标记统统消失了,而以字母j开始的标记则只留下了从第二个字符开始的部分。

再按下字母l,就可以将焦点切换到左下角的window,并且将光标移动到第一行的行首了。然后只需要选中内容、复制,并返回原来的window中粘贴即可。完整的过程如下

后记

如果在按下组合键M-g f后,接着按下的是数字键的话,avy-goto-line会认为使用者打算跳转到指定的行。它将在Emacs的minibuffer中继续等待输入更多的数字或按下回车。不过我不怎么用这个功能,因为我没有让Emacs显示行号,按行号来跳转对我并不方便。

我经常使用Emacs来干写字的活——有时候是写代码、有时候是用org-mode管理待办事项、有时候是用restclient-mode来测试HTTP API。Emacs丰富的快捷键让我可以双手不离主键盘区就做到很多事情,不过这也带来了别样的烦恼:快捷键按多了,手容易累。

导致手累的第一个因素,是Emacs的不少快捷键需要按住ctrl来使用,而ctrl常常不容易按到。以我的键盘为例,ctrl键分布在主键盘区的最外侧

为了便于尾指按到两侧的ctrl键,我在macOS中交换了commandcontrol键的效果

当需要按住两边的ctrl键(实际按下的是上面照片中的Windows图标键)时,手腕需要往外拐过去。这个问题在使用VSCode时同样存在,因为我在VSCode中用的也是Emacs的键映射。

第二个因素是Emacs的一些快捷键太繁琐,导致使用时双手像在键盘上起舞一般到处按来按去,敲击次数过多。例如,让光标上下左右移动的快捷键分别是ctrl-pctrl-nctrl-b,以及ctrl-f,这比直接用键盘上的方向键麻烦得多。有一些功能甚至要按三组快捷键,比如org-clock-out要先按ctrl-c,再按ctrl-x,最后按ctrl-o

有没有办法既可以保留快捷键的高效,又尽量地减少击键导致的手腕和手指的疲劳呢?

当然有。

在Emacs中改用Vim的快捷键

既然Emacs默认的快捷键不容易按,那么不妨换成Vim风格的快捷键。同样是上下左右移动光标,在Vim中只需要单击k/j/h/l这四个按键即可,不仅能够单手操作,而且这四个键正好是右手”触手可及“的位置。其它的功能,例如在文件内搜索、保存文件等,也只需要按/:w即可,比起Emacs真是”finger-friendly“得多了。

那么如何才能在Emacs中用上Vim的快捷键呢?答案是用evil插件。先用包管理器安装它

1
M-x package-install RET evil RET

然后在Emacs的启动配置文件中添加启用evil-mode的代码

1
2
(require 'evil)
(evil-mode 1)

现在便可以在Emacs中使用Vim风格的快捷键了

定制evil-mode

只是简单地启用evil-mode还不足以将双手从频繁的按ctrl中解放出来,因为在Emacs中还有不少其它的高频快捷键依赖于ctrl,例如用ctrl-x b来切换到其它的buffer中、用ctrl-x ctrl-f来打开或新建一个文件,甚至是用ctrl-c ctrl-x ctrl-o来停止一个任务的计时器。

就像在数据压缩中,用较短的串来代替出现频率较高的原始字符串一样,对于高频使用且快捷键较长的功能,可以为它们绑定较短的快捷键。在evil-mode中,g是一个前缀键并且也很好按,所以我把一些重度使用的功能都绑定了在了以它为前缀的快捷键上

1
2
3
4
5
6
7
;;; evil-mode相关的键绑定
(evil-global-set-key 'normal (kbd "g b") 'ido-switch-buffer)
(evil-global-set-key 'normal (kbd "g f") 'ido-find-file)
(evil-global-set-key 'normal (kbd "g o") 'org-clock-out)
(evil-global-set-key 'normal (kbd "g s") 'cuckoo-org-schedule)
(evil-global-set-key 'normal (kbd "g t") 'org-todo)
(evil-global-set-key 'normal (kbd "s") 'save-buffer)

在VSCode中改用Vim的快捷键

搬砖的工具是VSCode,用来写Node.js的项目,主要是因VSCode在写Node.js代码这方面确实比Emacs的js-modejs2-mode,以及tide-mode之流要好用那么一点。在VSCode中我也改用了Vim的键映射,只需要在插件市场中点击安装即可

VSCode的Vim键映射实际上是一个独立的插件Vim,它也支持进一步地自定义快捷键。出于个人喜好,我把s绑定为保存文件的功能

1
2
3
4
5
6
7
8
9
// VSCode的配置文件setting.json
"vim.normalModeKeyBindings": [
{
"before": ["s"],
"commands": [
"workbench.action.files.save"
]
}
],

用BetterTouchTools补充evil-mode的不足

尽管在Emacs中可以将常用的功能绑定到一系列的、以g开头的较短的快捷键上,但这一招并不能用来处理所有的快捷键,因为太多的自定义快捷键也会带来记忆上的负担。但我不会就此止步。

仔细观察就会发现,多数较长的快捷键是以ctrl-cctrl-x作为前缀的。因此,如果能够让ctrl-cctrl-x更容易按——比如替换为单个按键,也有利于减少尾指按ctrl键的负担。

要用单键来代替ctrl-c,光凭Emacs其实也可以做到。比如可以让F10被按下的时候相当于按下ctrl-c

1
2
3
4
5
(defun simulate-C-c ()
"模拟输入C-c"
(interactive)
(setq unread-command-events (listify-key-sequence "\C-c")))
(global-set-key [f10] 'simulate-C-c)

问题在于它不可组合。

例如,先按F10再按ctrl-x,等价于按下ctrl-c ctrl-x。但如果先按ctrl-x再按F10,则Emacs不会再将F10转换为ctrl-c,它只会认为我按下的是ctrl-x F10的键序列。

既要用F10代替ctrl-c,又要具备可组合性,怎么办?我的答案是使用BetterTouchTool。我用BTT将F9F12都重定义了一遍

如此一来,当我需要输入复杂的、含有ctrl-cctrl-x的快捷键的时候,只需要单击一次F10F11就足够了,轻而易举!

遗憾的是,BTT是一款macOS only的软件。

后记

或许脑机接口才是缓解手指劳损的终极解决方案吧。

今年四月左右,我心血来潮地为自己立了一个学习Prolog的目标——对,就是那门以逻辑编程和人工智能为卖点的语言。不仅要学会它的基本用法,还妄想用它像朋友圈广告里的Python那样,用来处理Excel文件中的大数据!

尽管处理大数据是开个玩笑,但学习Prolog的目标是真的。既然要学习一门编程语言,就必须找一本靠谱的教材。在无中生友之后,我选择了由谭浩强老先生主编的《Learn Prolog Now》作为入门读物。

尽管《Learn Prolog Now》的内容一点也不real world,却循序渐进、非常地适合初学者,每一章的结尾还准备了“上机题”。出人意料的是,仅仅在第三章就遇到了不会做的题目。在焦急地苦战一番未果后,我拖着疲惫的身躯搁置了它,继续学习后面的章节。

时隔五个月,我再次尝试解答这道题目。却惊喜地发现,只需要冷静地分析再仔细运用前三章学过的知识,解决这道题目也就是水到渠成的事情了。

所以到底是个什么题?

讲了这么多,是时候揭晓这它的真面目了。由于第三题以第二题为基础,因此一并搬运了过来

感兴趣的朋友也可以直接移步源网页查看。

看完上面的题目,只学过主流编程语言的朋友大概会是一头雾水,毕竟无论是代码还是术语,都与平日里使用的大相径庭。我来试着解释一下。像byCar(auckland, hamilton)byTrain(metz, frankfurt)这样的代码,用Prolog的术语来讲叫做“事实”。就像数学中的公理一样,它们总是成立的。如果向Prolog提问,它会给出肯定的回答

byCarbyTrain被称为“谓词”,aucklandhamilton则是“原子”。

第二题要求定义travel/2,第三题要求定义travel/3travel是谓词的名字,2和3则是它所接受的参数的个数。定义一个谓词就是给出描述它何时成立的“规则”,举个例子,可以定义一个名为len的谓词,只有当第二个参数等于第一个参数的长度时才成立

以大写字母开头的标识符(如题目中的X,上图中的TL)是变量,在归一化(unification)时Prolog能够为它们赋值使得查询成立。

鉴于本文不是Prolog的入门教程,各位读者如果想进一步了解Prolog,还请移步《Learn Prolog Now》的相关章节。

先解决第二题吧

讲了这么多,该进入正题了。第二题其实不难,细心的读者应该已经发现,这题可以用递归来解决(就像上文的len一样)。

设谓词travel的两个参数分别叫做SE,各代表起点和终点。显然,travel(S, E)成立,当且仅当:

  1. 可以从S搭乘汽车(byCar)、火车(byTrain),或飞机(byPlane)抵达E,或者;
  2. 存在另一个城市M,可以从S搭乘汽车、火车,或飞机抵达M,并且travel(M, E)也成立。

上述算法可以轻松地写成Prolog代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
byCar(auckland,hamilton).
byCar(hamilton,raglan).
byCar(valmont,saarbruecken).
byCar(valmont,metz).

byTrain(metz,frankfurt).
byTrain(saarbruecken,frankfurt).
byTrain(metz,paris).
byTrain(saarbruecken,paris).

byPlane(frankfurt,bangkok).
byPlane(frankfurt,singapore).
byPlane(paris,losAngeles).
byPlane(bangkok,auckland).
byPlane(singapore,auckland).
byPlane(losAngeles,auckland).

travel(S, E) :- just_go(S, E).
travel(S, E) :- just_go(S, M), travel(M, E).

just_go(S, E) :- byCar(S, E).
just_go(S, E) :- byTrain(S, E).
just_go(S, E) :- byPlane(S, E).

让Prolog告诉咱们这个travel/2写得对不对

精彩!

你话我猜?

Prolog不仅知道一个查询是否成立,还知道这个查询在什么参数下成立。例如,可以让Prolog告诉咱们,从valmont可以抵达哪一些城市,以及哪一些城市可以抵达auckland

这正是在接下来的题目中需要发扬光大的能力。

终于来到第三题

第三题所要求的travel是一个接受三个参数的谓词,第三个参数由从起点到终点的途径城市构成。设这个新的变量为R,那么travel(S, E, R)成立当且仅当:

  1. 可以从S抵达E,并且Rgo(S, E),或者;
  2. 存在另一个城市M,以及另一条路径R2。可以从S抵达M,并且travel(M, E, R2)成立,并且Rgo(S, M, R2)

那么如何在规则中描述R的结构呢?莫非是像上面的谓词len那样,在:-的右侧写上形如R is go(S, M, R2)这样的代码?

并不是。

借助Prolog强大的模式匹配能力,只需要在:-的左边声明R的结构即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
byCar(auckland,hamilton).
byCar(hamilton,raglan).
byCar(valmont,saarbruecken).
byCar(valmont,metz).

byTrain(metz,frankfurt).
byTrain(saarbruecken,frankfurt).
byTrain(metz,paris).
byTrain(saarbruecken,paris).

byPlane(frankfurt,bangkok).
byPlane(frankfurt,singapore).
byPlane(paris,losAngeles).
byPlane(bangkok,auckland).
byPlane(singapore,auckland).
byPlane(losAngeles,auckland).

travel(S, E, go(S, E)) :- just_go(S, E).
travel(S, E, go(S, M, R)) :- just_go(S, M), travel(M, E, R).

just_go(S, E) :- byCar(S, E).
just_go(S, E) :- byTrain(S, E).
just_go(S, E) :- byPlane(S, E).

加载这段代码后,就能让Prolog告诉我们,如何从valmont去往losAngeles

Prolog不仅找出了题目中所给出的答案(见上图的第二行X =),还找出了另外一条可行的路径。

后记

确实不难,难怪可以作为第三章的习题。

序言

7月初的时候挑战了一下LeetCode的第29题(中等难度,似乎没什么值得夸耀的),题目要求在不使用除、乘,以及模运算的情况下,实现整数相除的函数。

既然被除数和除数都是整数,那么用减法就可以实现除除法了(多么naive的想法)。一个trivial的、用JavaScript编写的函数可以是下面这样的(为了简单起见,只考虑两个参数皆为正整数的情况)

1
2
3
4
5
6
7
8
function divide(n, m) {
let acc = 0;
while (n >= m) {
n -= m;
acc += 1;
}
return acc;
}

如此朴素的divide函数提交给LeetCode是不会被接受的的——它会在像2147483648除以2这样的测试用例上超时。可以在本地运行一下感受下究竟有多慢

1
2
3
➜  nodejs time node divide.js
2147483648/2=1073741824
node divide.js 1.14s user 0.01s system 99% cpu 1.161 total

那么有没有更快的计算两个整数的商的算法呢?答案当然是肯定的。

尝试优化

一眼就可以看出,运行次数最多的是其中的while循环。以2147483648除以2为例,while循环中的语句要被执行1073741824次。为了提升运行速度,必须减少循环的次数。

既然每次从n中减去m需要执行n/m次,那么如果改为每次从中减去2m,不就只需要执行(n/m)/2次了么?循环的次数一下子就减少了一半,想想都觉得兴奋啊。每次减2m,并且自增2的算法的代码及其运行效果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
➜  nodejs cat divide2.js
function divide(n, m) {
let acc = 0;
let m2 = m << 1; // 因为题目要求不能用乘法,所以用左移来代替乘以2。
while (n >= m2) {
n -= m2;
acc += 2;
}
while (n >= m) {
n -= m;
acc += 1;
}
return acc;
}

console.log(`2147483648/2=${divide(2147483648, 2)}`);
➜ nodejs time node divide2.js
2147483648/2=1073741824
node divide2.js 2.65s user 0.01s system 99% cpu 2.674 total

尽管耗时不降反升,令场面一度十分尴尬,但根据理论分析可知,第一个循环的运行次数仅为原来的一半,而第二个循环的运行次数最多为1次,可以知道这个优化的方向是没问题的。

如果计算m2的时候左移的次数为2,那么acc的自增步长需要相应地调整为4,第一个循环的次数将大幅下降至268435456,第二个循环的次数不会超过4;如果左移次数为3,那么acc的步长增至8,第一个循环的次数降至134217728,第二个循环的次数不会超过8。

显然,左移不能无限地进行下去,因为m2的值早晚会超过n。很容易算出左移次数的一个上限为

对数符号意味着即便对于很大的n和很小的m,上述公式的结果也不会很大,因此可以显著地提升整数除法的计算效率。

在开始写代码前,让我先来简单地证明一下这个方法算出来的商与直接计算n/m是相等的。

一个简单的证明

记被减数为n,减数为m。显然,存在一个正整数N,使得

,再令

,那么n除以m等价于

证明完毕。

从上面的公式还可以知道,新算法将原本规模为n的问题转换为了一个规模为r的相同问题,这意味着可以用递归的方式来优雅地编写最终的代码。

完整的代码

最终的divide函数的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function divide(n, m) {
if (n < m) {
return 0;
}

let n2 = n;
let N = 0;
// 用右移代替左移,避免溢出。
while ((n2 >> 1) > m) {
N += 1;
n2 = n2 >> 1;
}

// `power`表示公式中2的N次幂
// `product`代表`power`与被除数`m`的乘积
let power = 1;
let product = m;
for (let i = 0; i < N; i++) {
power = power << 1;
product = product << 1;
}
return power + divide(n - product, m);
}

这个可比最开始的divide要快得多了,有图有真相

1
2
3
➜  nodejs time node divide3.js
2147483648/2=1073741824
node divide3.js 0.03s user 0.01s system 95% cpu 0.044 total

后记

如果以T(n, m)表示被除数为n,除数为m时的算法时间复杂度,那么它的递推公式可以写成下列的形式

但这玩意儿看起来并不能用主定理直接求出解析式,所以很遗憾,我也不知道这个算法的时间复杂度究竟如何——尽管我猜测就是N的计算公式。

如果有哪位好心的读者朋友知道的话,还望不吝赐教。