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

0%

我经常使用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的计算公式。

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

序言

理论上,开发人员是不允许操作生产环境的,更别说是像商品、订单这样的重要业务数据。不过对小公司来说,后台系统往往不是很完善,总有一些需求让运营或客服部门的同事操作起来捉襟见肘,不得不寻求开发人员的帮助。

通常这些部门的同事会给过来一批需要处理的商品或订单的ID,我会将它们粘贴到一个脚本中,并将脚本放到生产环境的机器上运行,以实现他们的ad hoc需求。ID一般用Excel文件,或在线文档的方式提供过来,将它们粘贴到脚本的源码中之后,还要为它们添加必要的引号和逗号,以满足所用语言的语法要求。比如下图就是直接粘贴后,VSCode提示错误的样子

那么,怎样才能不失逼格地给这批ID加上前后的引号及行末的逗号呢?

八仙过海,各显神通

有很多方法可以完成这个任务,比如借助VSCodemulti-cursor功能,手动添加前后缀

当要添加光标的位置处于同一列时,更适合用VSCode的另一个功能在下面添加光标(快捷键是command+option+↓)来实现,免去了一遍遍点击鼠标的烦恼。multi-cursor所敲入的每个光标还可以在各自的行上沿同方向移动不同的距离,适合处理每行长度不一致的情况。

也可以用Vim中的列编辑模式,操作体验差不多,还可以比VSCode按更少的键——起码不需要一直压着option键。

Vim列模式的效果

但列编辑模式不方便在行末追加内容——必须先在第一行的末尾敲入一个空格,往右移动依次光标,然后才能继续用列编辑模式批量添加后缀。

Emacs也有类似列编辑模式的功能,它的string-insert-rectangle命令比Vim的更便于添加后缀。但它没有默认的快捷键,需要先按下M-x,再输入命令名并回车,略为繁琐(尽管命令名可以自动补全)。

Emacs的string-insert-rectangle的效果

除了各家编辑器内置的功能,命令行工具也适合完成这种处理,比如可以用sed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
➜  /tmp cat b
5FEB1AE4-239A-4276-8E37-BE913CE6D117
5FEB1AE4-239A-4276-8E37-BE913CE6D117
5FEB1AE4-239A-4276-8E37-BE913CE6D117
5FEB1AE4-239A-4276-8E37-BE913CE6D117
5FEB1AE4-239A-4276-8E37-BE913CE6D117
5FEB1AE4-239A-4276-8E37-BE913CE6D117
5FEB1AE4-239A-4276-8E37-BE913CE6D117
➜ /tmp sed -e "s/^/'/" -i '' b
➜ /tmp sed -e "s/$/',/" -i '' b
➜ /tmp cat b
'5FEB1AE4-239A-4276-8E37-BE913CE6D117',
'5FEB1AE4-239A-4276-8E37-BE913CE6D117',
'5FEB1AE4-239A-4276-8E37-BE913CE6D117',
'5FEB1AE4-239A-4276-8E37-BE913CE6D117',
'5FEB1AE4-239A-4276-8E37-BE913CE6D117',
'5FEB1AE4-239A-4276-8E37-BE913CE6D117',
'5FEB1AE4-239A-4276-8E37-BE913CE6D117',

有些从在线文档上复制下来的ID会有一行空行存在于两两之间,如果是在命令行的话,只需要先用grep筛选一遍即可,可组合性比编辑器更强。

美中不足的是,用sed处理后需要手动将文件b的内容粘贴到脚本中——如果是用Emacs的话,也可以用C-x i让编辑器在光标处直接插入该文件的内容。

如果可以寸步不离Emacs,通过简单的命令或快捷键来完成这个操作,岂不美哉?

自己动手,丰衣足食

用上自定义的Elisp函数后的效果如下

其实实现思路很简单:

  1. 首先用户会选中一片要添加前后缀的区域;
  2. 使用buffer-substring-no-properties函数复制这个region中的字符串,绑定为text
  3. read-from-minibuffer提示并读取用户输入待添加的前后缀字符串;
  4. split-stringtext切割为一行行的字符串,给每一行添加前后缀,再用mapconcat拼回一个字符串;
  5. delete-region删除被选中的内容,然后用insert插入新的字符串。

最终的Elisp函数的定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(defun lt--insert-at-start-end ()
"为TEXT中的每一行添加PREFIX前缀和SUFFIX后缀。"
(interactive)
(let* ((text (buffer-substring-no-properties (mark) (point)))
(prefix (read-from-minibuffer "插入的前缀:"))
(suffix (read-from-minibuffer "插入的后缀:"))
(lines (split-string text))
(decorated-lines
(mapcar (lambda (line)
(concat prefix line suffix))
lines))
(new-text (mapconcat 'identity decorated-lines "\n")))
(delete-region (mark) (point))
(insert new-text)))

欢迎读者朋友中的Emacs用户也来使用使用;-)

序言

《编码》这本书曾经在我的豆瓣“想读”列表中躺了很久,大概在今年年初才开始看。但读着读着发现书中的电路图越来越多,而我的阅读热情也随之被慢慢浇灭。五月初的时候,终究还是把它合上,并在豆瓣上羞愧难当地将其标注为“读过”。

抛开晦涩的电路图不谈,书中有一句话吸引了我的注意力

第一次读到这里时,我想作者应当会在下一段给出具体的证明过程——结果居然没有。难道作者觉得两侧的空白太小了,不足以写下他所发现的美妙证法?

受好奇心的驱使,我便试着证明书中的这个结论。

不过正式开始前,还得明确一下命题:对于任意的正整数aba不等于b),10的a次幂和2的b次幂不相等。

先证明一条引理

为了证明上面的命题,需要先证明一条引理:对于任意的正整数a,5的a次幂是一个奇数。可以用数学归纳法来证明。

首先验证a为1时命题成立。由于5的1次幂为5,并且5是一个奇数,所以命题成立;

接着,假设ak时命题成立,将5的k次幂写成2n+1的形式,当ak+1时,

因此,5的k次幂也是一个奇数。因此,该命题对于任意的正整数a都是成立的。

同理可证:对于任意的正整数a,2的a次幂是偶数。

反证法证明原命题

假设存在正整数abb大于a),使得10的a次幂与2的b次幂相等

将10分解为2和5的积,再两边同时除以2的a次幂

等式的左边和右边分别是5的正整数次幂与2的正整数次幂。由前一节的引理可知,左边是奇数,右边是偶数,两者不可能相等,与上述等式产生矛盾。因此,原假设不成立,命题得证。

后记

我最开始的想法很复杂。虽然也是采用反证法,但我将等式做了如下变换

然后试图证明以2为底的10的对数不是有理数,和等式右边不相等。不过这个方法于我而言太难了,便没有继续尝试下去。