准备过互联网公司的服务端岗位面试的人，对Redis中的5种数据类型想必是如数家珍。而网上很多面试题里也会出现这道题目

随着行业曲率的增大，光是知道有这些数据类型已经不够了，还得知道同一个类型也有不同的底层数据结构。例如同样是string类型，不同内容或不同长度会采用不同的编码方式：

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

127.0.0.1:6379> SET key1 "1"
OK
127.0.0.1:6379> SET key2 "value"
OK
127.0.0.1:6379> SET key3 "Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."
OK
127.0.0.1:6379> TYPE key1
string
127.0.0.1:6379> TYPE key2
string
127.0.0.1:6379> TYPE key3
string
127.0.0.1:6379> OBJECT ENCODING key1
"int"
127.0.0.1:6379> OBJECT ENCODING key2
"embstr"
127.0.0.1:6379> OBJECT ENCODING key3
"raw"

而hash类型也有两种底层实现

1
2
3
4
5
6
7
8

127.0.0.1:6379>  HSET myhash field1 "Hello"
(integer) 1
127.0.0.1:6379>  HSET myhash2 field1 "Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."
(integer) 1
127.0.0.1:6379> OBJECT ENCODING myhash
"ziplist"
127.0.0.1:6379> OBJECT ENCODING myhash2
"hashtable"

不知道你是否曾经好奇过，上文中的key1、key2、key3、myhash，以及myhash2这些键，与它们各自的值（前三个为string，后两个为hash）之间的关系又是存储在什么数据结构中的呢？

答案在意料之外，情理之中：键与值的关系，也是存储在一张哈希表中的，并且正是上文中的hashtable。

求证的办法当然是阅读Redis的源代码。

Redis命令的派发逻辑

阅读Redis的源码是比较轻松愉快的，一是因为其源码由简单易懂的C语言编写，二是因为源码仓库的README.md中对内部实现做了一番高屋建瓴的介绍。在README.md的server.c一节中，道出了有关命令派发的两个关键点

call() is used in order to call a given command in the context of a given client.

The global variable redisCommandTable defines all the Redis commands, specifying the name of the command, the function implementing the command, the number of arguments required, and other properties of each command.

位于文件src/server.c中的变量redisCommandTable定义了所有可以在Redis中使用的命令——为什么一个C语言项目里要用camelCase这种格格不入的命名风格呢——它的元素的类型为struct redisCommand，其中：

• name存放命令的名字；
• proc存放实现命令的C函数的指针；

比如高频使用的GET命令在redisCommandTable中就是这样定义的

1
2
3

{"get",getCommand,2,
 "read-only fast @string",
 0,NULL,1,1,1,0,0,0},

身为一名老解释器爱好者，对这种套路的代码当然是不会陌生的。我也曾在写过的、跑不起来的玩具解释器上用过类似的手法

Redis收到一道需要执行的命令后，根据命令的名字用lookupCommand找到一个命令（是个struct redisCommand类型的结构体），然后call函数做的事情就是调用它的proc成员所指向的函数而已

1

c->cmd->proc(c);

那么接下来，就要看看SET命令对应的C函数究竟做了些什么了。

SET命令的实现

redisCommonTable中下标为2的元素正是SET命令的定义

1
2
3
4
5

/* Note that we can't flag set as fast, since it may perform an
 * implicit DEL of a large key. */
{"set",setCommand,-3,
 "write use-memory @string",
 0,NULL,1,1,1,0,0,0},

其中函数setCommand定义在文件t_string.c中，它根据参数中是否有传入NX、XX、EX等选项计算出一个flags后，便调用setGenericCommand——顾名思义，这是一个通用的SET命令，它同时被SET、SETNX、SETEX，以及PSETEX四个Redis命令的实现函数所共用。

setGenericCommand调用了genericSetKey，后者定义在文件db.c中。尽管该函数上方的注释写着

All the new keys in the database should be created via this interface.

但人生不如意事十之八九事实并非如此。例如在命令RPUSH的实现函数rpushCommand中，调用了pushGenericCommand，后者直接调用了dbAdd往Redis中存入键和列表对象的关系。

言归正传。根据键存在与否，genericSetKey会调用dbAdd或dbOverwrite。而在dbAdd中，最终调用了dictAdd将键与值存入数据库中。

1
2
3
4
5
6
7
8
9

/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL);

    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

现在我们知道了，使用SET命令时传入的key和value，是存储在一个dict类型的数据结构中。

HSET命令的实现

依葫芦画瓢，Redis的HSET命令由位于文件t_hash.c中的函数hsetCommand实现，它会尝试转换要操作的hash值的编码方式。

1

hashTypeTryConversion(o,c->argv,2,c->argc-1);

如果hashTypeTryConversion发现要写入哈希表的任何一个键或者值的长度超过了server.hash_max_ziplist_value所规定的值，就会将hash类型的编码从ziplist转换为hashtable。server.hash_max_ziplist_value的值在文件config.c中通过宏设置，默认值为64——这正是上文中myhash2所对应的值的编码为hashtable的原因。

将思绪拉回到函数hsetCommand中。做完编码的转换后，它调用函数hashTypeSet，在编码为hashtable的世界线中，同样调用了dictAdd实现往哈希表中写入键值对。

殊途同归

结论

因此，在Redis中用以维持每一个键与其对应的值——这些值也许是string，也许是list，也许是hash——的关系的数据结构，与Redis中的一系列操作哈希表的命令——也许是HSET、也许HGET，也许是HDEL——所用的数据结构，不能说是毫不相关，起码是一模一样。

通常在糊业务代码的时候，不管是函数、方法，还是宏，都只会有一个返回值。比如在C语言用于检查一个字符是否为阿拉伯数字的isdigit函数就只会返回是（1）或否（0）

1
2
3
4
5
6
7
8
9
10

#include <ctype.h>
#include <stdio.h>

int
main(int argc, char *argv[])
{
    char c = 'a';
    printf("isdigit('%c') is %d\n", c, isdigit(c));
    return 0;
}

但有时候如果一个函数、方法，或宏可以返回多个值的话会更加方便。例如，在Python中dict类型有一个实例方法get，它可以取得dict实例中与给定的键对应的值。但如果有一个键在字典中的值为None，那么光凭get的返回值无法准确判断这个键是否存在——除非你给它一个非None的默认值

1
2
3
4
5
6
7
8
9
10
11

# -*- coding: utf8 -*-
def test(d, key):
    print("d.get('{0}') is {1}\t'{0}' in d is {2}".format(key, d.get(key), key in d))

if __name__ == '__main__':
    d = {
        'foo': 'bar',
        'baz': None,
    }
    test(d, 'foo')
    test(d, 'baz')

发展了这么多年的编程语言，又怎么会连一次调用、多值返回这么简单的事情都做不到呢。事实上，有各种各样、各显神通的返回多个值的方法，我给其中的一些做了个分类

Lisp的multiple-value-bind

Common Lisp（简称为CL）的多重返回值当之无愧是其中最正统、最好用的实现方式。以它的内置函数truncate为例，它的第一个返回值为第一个参数除以第二个参数的商，第二个返回值为对应的余数

1
2
3

CL-USER> (truncate 10 3)
3
1

如果不加修饰地调用truncate，就像其它只返回一个值的函数一样，也只会拿到一个返回值

1
2
3

CL-USER> (let ((q (truncate 10 3)))
           (format t "q = ~D~%" q))
q = 3

除非用multiple-value-bind来捕获一个函数产生的所有返回值

1
2
3
4

CL-USER> (multiple-value-bind (q r)
             (truncate 10 3)
           (format t "q = ~D~8Tr = ~D~%" q r))
q = 3   r = 1

CL的方案的优点在于它十分灵活。即使将一个函数从返回单个值改为返回多个值，也不会导致原本调用该函数的位置要全部修改一遍——对修改封闭，对扩展开放（误）。

Go的多重返回值

踩在C语言肩膀上的Go也能够从函数中返回多个值。在io/ioutil包的官方文档中有大量的例子，比如用ReadAll方法从字符串衍生的流中读取全部内容，就会返回两个值

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

package main

import (
	"fmt"
	"io/ioutil"
	"log"
	"strings"
)

func main() {
	s := "Hello, world!"
	reader := strings.NewReader(s)
	bytes, err := ioutil.ReadAll(reader)
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("bytes is %s", bytes)
}

Go以这种方式取代了C语言中用返回值表达成功与否、再通过指针传出读到的数据的风格。由于这个模式在有用的Go程序中到处出现，因此Gopher们用的都是定制的键盘（误）

不同于前文的multiple-value-bind，如果一个函数或方法返回多个值，那么调用者必须捕获每一个值，否则编译无法通过

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

➜  try cat try_read_all_ignore_err.go
package main

import (
	"fmt"
	"io/ioutil"
	"strings"
)

func main() {
	s := "Hello, world!"
	reader := strings.NewReader(s)
	bytes := ioutil.ReadAll(reader)
	fmt.Printf("bytes is %s", bytes)
}
➜  try go build try_read_all_ignore_err.go
# command-line-arguments
./try_read_all_ignore_err.go:12:8: assignment mismatch: 1 variable but ioutil.ReadAll returns 2 values

这一要求也是合理的，毕竟多重返回值机制主要用于向调用者传递出错原因——既然可能出错，那么就必须要检查一番。

Python和Rust的解构

就像CL的truncate函数一样，Python中的函数divmod也可以同时返回两个数相除的商和余数，并且咋看之下也是返回多个值的形式

1
2
3
4

# -*- coding: utf8 -*-
if __name__ == '__main__':
    q, r = divmod(10, 3)
    print('q = {}\tr = {}'.format(q, r))

但本质上，这是因为Python支持解构，同时divmod返回的是一个由商和余数组成的元组。这样的做法与CL的真·奥义·多重返回值的差异在于，如果只想要divmod的第一个值，那么等号左侧也要写成对应的结构

1
2
3
4

# -*- coding: utf8 -*-
if __name__ == '__main__':
    q, _ = divmod(10, 3)
    print('q = {}'.format(q))

在支持解构的语言中都可以模仿出多重返回值，例如Rust

1
2
3
4
5
6
7
8

fn divmod(a: u32, b: u32) -> (u32, u32) {
    (a / b, a % b)
}

fn main() {
    let (q, r) = divmod(10, 3);
    println!("q = {}\tr = {}", q, r);
}

Prolog的归一

到了Prolog这里，画风就有点不一样了。首先Prolog既没有函数，也没有方法，更没有宏。在Prolog中，像length/2和member/2这样的东西叫做functor，它们之于Prolog中的列表，就犹如CL的length和member之于列表、Python的len函数和in操作符之于列表，JavaScript的length属性和indexOf方法之于数组……

其次，Prolog并不“返回”一个functor的“调用结果”，它只是判断输入的查询是否成立，以及给出使查询成立的变量值。在第一个查询中，length/2的第二个参数为变量L，因此Prolog给出了使这个查询成立的L的值4；第二个查询中没有变量，Prolog只是简单地给出查询是否成立；第三个查询中，Prolog给出了四个能够使查询成立的变量X的值。

由于Prolog会给出查询中每一个变量的值，可以用这个特性来模拟多重返回值。例如，可以让Prolog一次性给出两个数字的和、差、积，和商

麻烦之处在于就算只想要得到两数之和，也必须用占位符填在后三个参数上：jjcc(10, 3, S, _, _, _)。

作弊的指针与全局变量

尽管在开篇的时候提到了C语言中的函数无法返回多个值，但如果像上文的Prolog那般允许修改参数的话，C语言也是可以做到的，谁让它有指针这个强力特性呢。例如，stat(2)函数就会将关于一个文件的信息填充到参数中所指向的结构体的内存中

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

#include <stdio.h>
#include <sys/stat.h>

int
main(int argc, char *argv[])
{
    char *path = "./try_stat.c";
    struct stat buf;
    stat(path, &buf);
    printf("inode's number of %s is %llu\n", path, buf.st_ino);
    return 0;
}

查看man 2 stat可以知道struct stat类型中有非常多的内容，这显然也是一种多重返回值。同样的手法，在Go中也可以运用，例如用于把从数据库中读取出来的行的数据写入目标数据结构的Scan方法。

最后，如果只要能让调用者感知就行，那么全局变量未尝不是一种通用的多重返回值机制。例如在C语言中的strtol函数，就会在无法转换出任何数字的时候返回0并设置errno，因此检查errno是必须的步骤

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

#include <stdio.h>
#include <stdlib.h>
#include <sys/errno.h>

void try_conversion(const char *str)
{
    long num = strtol(str, NULL, 10);
    if (errno == EINVAL || errno == ERANGE)
    {
        char message[64];
        snprintf(message, sizeof(message), "strtol(\"%s\")", str);
        perror(message);
        return;
    }
    printf("strtol(\"%s\") is %ld\n", str, num);
}

int
main(int argc, char *argv[])
{
    try_conversion("233");
    try_conversion("0");
    try_conversion("lisp");
    return 0;
}

鉴于errno是一个全局变量，strtol的使用者完全有可能忘记要检查。相比之下，Go的strconv包的函数都将转换过程中的错误以第二个参数的形式返回给调用者，用起来更安全。

后记

按照《代码写得不好，不要总觉得是自己抽象得不好》这篇文章的说法，代码写成什么样子完全是由产品经理决定的。但产品经理又怎么会在意你用的技术是怎么实现多重返回值的呢。综上所述，这个特性没用（误）。

全文完。

序言

在旧文《如何写一个命令行的秒表》中，借助命令tput，我实现了“原地更新”所输出的时分秒的效果

其中用到的是ASCII转义序列\x1b[8D和\x1b[0K。除此之外，ASCII转义序列还有许多其它功能。例如，可以用来定制输出内容的前景色

将转义序列中的参数38改为48，可以定制输出内容的背景色

将打印内容改为两个空格，看起来就像是在一块黑色的画布上涂了一个红色的方块

既然如此，只要尺寸合适，就可以在终端打印出一张图片，只需要将每一个像素的颜色作为背景色，在坐标对应的行列上输出两个空格即可。如果能抹掉输出的内容并在同样的位置上打印一张不同的图片，甚至可以实现动画的效果。

百闻不如一见，下面我用Python演示一番。

把GIF装进终端

要想用前文的思路在终端中显示一张GIF图片，必须先得到GIF图片每一帧的每个像素的颜色才行。在Python中使用名为Pillow的库可以轻松地解析GIF文件，先安装这个库

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

➜  /tmp rmdir show_gif
➜  /tmp mkdir show_gif
➜  /tmp cd show_gif
➜  show_gif python3 -m venv ./venv
➜  show_gif . ./venv/bin/activate
(venv) ➜  show_gif pip install Pillow
Collecting Pillow
  Using cached Pillow-8.1.0-cp39-cp39-macosx_10_10_x86_64.whl (2.2 MB)
Installing collected packages: Pillow
Successfully installed Pillow-8.1.0
WARNING: You are using pip version 20.2.3; however, version 21.0.1 is available.
You should consider upgrading via the '/private/tmp/show_gif/venv/bin/python3 -m pip install --upgrade pip' command.

接着便可以让它读入并解析一张GIF图片

1
2
3
4
5
6
7
8
9

import sys

from PIL import Image, ImageSequence

if __name__ == '__main__':
    path = sys.argv[1]
    im = Image.open(path)
    for frame in ImageSequence.Iterator(im):
        pass

然后将每一帧都转换为RGB模式再遍历其每一个像素

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

import sys

from PIL import Image, ImageSequence

if __name__ == '__main__':
    path = sys.argv[1]
    im = Image.open(path)
    for frame in ImageSequence.Iterator(im):
        rgb_frame = frame.convert('RGB')
        pixels = rgb_frame.load()
        for y in range(0, rgb_frame.height):
            for x in range(0, rgb_frame.width):
                pass

调用Image类的实例方法load得到的是一个PixelAccess类的实例，它可以像二维数组一般用坐标获取每一个像素的颜色值，颜色值则是一个长度为3的tuple类型的值，其中依次是像素的三原色的分量。

从ANSI escape code词条的24-bit小节中得知，使用参数为48;2;的转义序列，再接上以分号分隔的三原色分量即可设置24位的背景色

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

import sys

from PIL import Image, ImageSequence

if __name__ == '__main__':
    path = sys.argv[1]
    im = Image.open(path)
    for frame in ImageSequence.Iterator(im):
        rgb_frame = frame.convert('RGB')
        pixels = rgb_frame.load()
        for y in range(0, rgb_frame.height):
            for x in range(0, rgb_frame.width):
                colors = pixels[x, y]
                print('\x1b[48;2;{};{};{}m  \x1b[0m'.format(*colors), end='')
            print('')

在每次二重循环遍历了所有像素后，还必须清除输出的内容，并将光标重置到左上角才能再次打印，这可以用ASCII转义序列来实现。查阅VT100 User Guide可以知道，用ED命令可以擦除显示的字符，对应的转义序列为\x1b[2J；用CUP命令可以移动光标的位置到左上角，对应的转义序列为\x1b[0;0H。在每次开始打印一帧图像前输出这两个转义序列即可

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

import sys

from PIL import Image, ImageSequence

if __name__ == '__main__':
    path = sys.argv[1]
    im = Image.open(path)
    for frame in ImageSequence.Iterator(im):
        rgb_frame = frame.convert('RGB')
        pixels = rgb_frame.load()
        print('\x1b[2J\x1b[0;0H', end='')
        for y in range(0, rgb_frame.height):
            for x in range(0, rgb_frame.width):
                colors = pixels[x, y]
                print('\x1b[48;2;{};{};{}m  \x1b[0m'.format(*colors), end='')
            print('')

最后，只需要在每次打印完一帧后，按GIF文件的要求睡眠一段时间即可。每一帧的展示时长可以从info属性的键duration中得到，单位是毫秒

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

import sys
import time

from PIL import Image, ImageSequence

if __name__ == '__main__':
    path = sys.argv[1]
    im = Image.open(path)
    for frame in ImageSequence.Iterator(im):
        rgb_frame = frame.convert('RGB')
        pixels = rgb_frame.load()
        print('\x1b[2J\x1b[0;0H', end='')
        for y in range(0, rgb_frame.height):
            for x in range(0, rgb_frame.width):
                colors = pixels[x, y]
                print('\x1b[48;2;{};{};{}m  \x1b[0m'.format(*colors), end='')
            print('')
        time.sleep(rgb_frame.info['duration'] / 1000)

现在可以看看效果了。我准备了一张测试用的GIF图片，宽度和高度均为47像素，共34帧

让它在终端中显示出来吧

一点微小的改进

你可能留意到了，前文的演示效果中有明显的闪烁，这是因为打印ASCII转义序列的速度不够快导致的。既然如此，可以将一整行的转义序列先生成出来，再一次性输出到终端。改动不复杂

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

import sys
import time

from PIL import Image, ImageSequence

if __name__ == '__main__':
    path = sys.argv[1]
    im = Image.open(path)
    for frame in ImageSequence.Iterator(im):
        rgb_frame = frame.convert('RGB')
        pixels = rgb_frame.load()
        print('\x1b[2J\x1b[0;0H', end='')
        for y in range(0, rgb_frame.height):
            last_colors = None
            line = ''
            for x in range(0, rgb_frame.width):
                colors = pixels[x, y]
                if colors != last_colors:
                    line += '\x1b[0m\x1b[48;2;{};{};{}m  '.format(*colors)
                else:
                    line += '  '
                last_colors = colors
            print('{}\x1b[0m'.format(line))
        time.sleep(rgb_frame.info['duration'] / 1000)

但效果却很显著

全文完

仅以此文膜拜八年前的自己

序言

欧拉计划（Project Euler）就像LeetCode，是一个编程答题的网站。不同于LeetCode的是，欧拉计划只要求用户提交最终答案即可（一般是一个数字），而不需要完整代码。因此，可以尽情地使用自己喜欢的编程语言——不少题目甚至光靠笔和纸便能解决。

欧拉计划的第66题非常有意思，它的题目很简单，就是要求找出在不大于1000的整数中，以哪一个数字为丢番图方程的系数，可以得到所有最小解中的最大值。

可以很容易地看出方程有一个直观的暴力算法：让y从1开始递增，对于每一个y，计算公式Dy^2+1的值。如果该值为平方数，那么它的平方根就是最小的x解。再依照这个算法求解所有D不大于1000的方程，便可以求出题目的答案。很容易用Python写出这个算法

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

# -*- coding: utf8 -*-
import math

def is_square(num: int) -> bool:
    return math.isqrt(num) ** 2 == num

def find_x(D: int) -> int:
    """
    求出给定D时，满足题目所给的丢番图方程的最小的x。
    """
    assert not is_square(D)
    y = 1
    while True:
        candidate = D * y * y + 1
        if is_square(candidate):
            return math.isqrt(candidate)
        y += 1

def solve_66(limit):
    """
    找出不大于limi的D中，使find_x的返回值最大的那一个数字。
    """
    max_D = None
    max_x = None
    D = 2
    while D <= limit:
        if is_square(D):
            D += 1
            continue
        x = find_x(D)
        if max_x is None or x > max_x:
            max_D = D
            max_x = x
        D += 1
    return max_D, max_x

if __name__ == '__main__':
    D, x = solve_66(7)
    print('D is {} and x is {}'.format(D, x))

但如果将上限limit提升为1000，这个算法在有生之年是算不出结果的。

要想解决这一题，需要借助数学的力量。

佩尔方程

八年前第一次做这一题的时候，经过一番搜索，我从这篇文章中知道了题目中的方程叫做佩尔方程。它有标准的解法，但需要用到连分数。那么什么是连分数呢？

连分数不是一种新的数系，只是小数的另一种写法。例如可以把分数45除以16写成下面的形式

就像定义递归的数据结构一样，可以给连分数一个递归的定义。连分数要么是一个整数，要么是一个整数加上另一个连分数的倒数。除了上面的形式，连分数也可以写成更节省篇幅的样子。比如把45除以16写成[2;1,4,3]，即把原本的式子中所有的整数部分按顺序写在一对方括号之间。这种记法，看起来就像是编程语言中的数组一般。

如果用数组[2;1,4,3]的不同前缀来构造分式，那么结果依次为2/1、3/1、14/5。它们是这个连分数的渐进连分数，而佩尔方程的一组解，就来自于渐进连分数的分子和分母。

以系数为7的佩尔方程为例，先计算出根号7的连分数，然后依次尝试它的渐进连分数。前三个分别为2/1、3/1、5/2，都不是方程的解。第四个渐进连分数8/3才是方程的解。如果继续提高连分数的精度，还会找到第二个解127/48。继续找，还有更多，而8则是其中最小的x。

所以，想要快速算出佩尔方程的解，最重要的是找到计算一个数的平方根的连分数的算法。

计算平方根的连分数的错误方法

要计算一个数字的连分数，最重要的便是要算出所有的整数部分（a0、a2、a2等）。它们都可以依据定义直接计算

推广到一半情况，如果用变量n存储开平方的数字，用numbers存储所有已知的整数，那么用Python可以写出下面的算法来计算出下一个整数

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

# 计算连分数数列的下一个数字
import math

def compute_next_integer_part(n, numbers):
    v = math.sqrt(n)
    for a in numbers:
        v = 1 / (v - a)
    return int(v)

if __name__ == '__main__':
    n = 14
    numbers = [3, 1, 2, 1]
    v = compute_next_integer_part(n, numbers)
    print('下一个数字为{}'.format(v))

遗憾的是，这个算法算出来的数字会因为计算上的精度误差而导致失之毫厘谬以千里。

计算平方根的连分数的正确方法

要想计算出正确的结果，就需要尽可能地消除在计算1 / (v - a)的时候引入的误差，因此必须把浮点数从分母中除去。

在这个网站中，作者以计算根号14的连分数为例，列出了一个表格

可以看到x1、x2，以及x3都是形如(sqrt(n)+a)/b这样的格式，这样的式子更利于控制误差。那么是否每一个待计算的x都符合这种格式呢？答案是肯定的，可以用数学归纳法予以证明（为了方便写公式，用LaTeX写好后截了图）

在这个证明过程中，还得到了分子中的a以及分母中的b的递推公式，现在可以写出正确的计算连分数整数部分的代码了。

用Common Lisp实现上述算法

为了在实现这个算法的同时还要写出优雅的代码，我会用上Common Lisp的面向对象特性。首先是定义一个类来表示一个可以不断提高精度的连分数

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

(defpackage #:com.liutos.cf
  (:use #:cl))

(in-package #:com.liutos.cf)

(defclass <cf> ()
  ((a
    :documentation "数学归纳法中、分子中与平方根相加的数"
    :initform 0)
   (b
    :documentation "数学归纳法中的分母"
    :initform 1)
   (numbers
    :documentation "连分数中的整数部分依次组成的数组。"
    :initform nil)
   (origin
    :documentation "被开平方的数字"
    :initarg :origin))
  (:documentation "表示整数ORIGIN的平方根的连分数。"))

接着再定义这个类需要实现的“接口”

1
2
3
4
5

(defgeneric advance (cf)
  (:documentation "让连分数CF提高到下一个精度。"))

(defgeneric into-rational (cf)
  (:documentation "将连分数CF转换为有理数类型的值。"))

最后来实现上述两个接口

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

(defmethod advance ((cf <cf>))
  "根据递推公式计算出下一批a、b，以及连分数的整数部分。"
  (let* ((a (slot-value cf 'a))
         (b (slot-value cf 'b))
         (n (slot-value cf 'origin))
         (m (truncate (+ (sqrt n) a) b)))
    (let ((a (- (* b m) a))
          (b (/ (- n (expt (- a (* b m)) 2)) b)))
      (setf (slot-value cf 'a) a
            (slot-value cf 'b) b
            (slot-value cf 'numbers) (append (slot-value cf 'numbers) (list m))))
    (values)))

(defmethod into-rational ((cf <cf>))
  (let* ((numbers (reverse (slot-value cf 'numbers)))
         (v (first numbers)))
    (dolist (n (rest numbers))
      (setf v
            (+ n (/ 1 v))))
    v))

在实现into-rational方法上，Common Lisp的有理数数值类型给我带来了极大的便利，它使我不必担心计算(/ 1 v)的时候会引入误差，代码写起来简单直白。

解题

乘胜追击，用Common Lisp解答第66题

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

(defun find-min-x (D)
  (let ((cf (make-instance '<cf> :origin D)))
    (loop
       (advance cf)
       (let* ((ratio (into-rational cf))
              (x (numerator ratio))
              (y (denominator ratio)))
         (when (= (- (* x x) (* D y y)) 1)
           (return-from find-min-x x))))))

(defun square-p (n)
  (let ((rt (sqrt n)))
    (= rt (truncate rt))))

(defun pro66 (&optional (bnd 1000))
  (let ((target-d)
	(max-x 0))
    (loop :for i :from 2 :to bnd
       :when (not (square-p i))
       :do (let ((x (find-min-x i)))
	     (if (> x max-x)
		 (setf target-d i
		       max-x x))))
    (values target-d max-x)))

答案的D是多少就不说了，不过作为答案的x是16421658242965910275055840472270471049。有兴趣的读者可以试一下暴力解法要花多久才能算到这个数字。

全文完。

《实战Common Lisp》系列主要讲述在使用Common Lisp时能派上用场的小函数，希望能为Common Lisp的复兴做一些微小的贡献。MAKE COMMON LISP GREAT AGAIN。

序言

写了一段时间的Python后，总觉得它跟Common Lisp（下文简称CL）有亿点点像。例如，Python和CL都支持可变数量的函数参数。在Python中写作

1
2

def foo(* args):
    print(args)

而在CL中则写成

1
2

(defun foo (&rest args)
  (print args))

Python的语法更紧凑，而CL的语法表意更清晰。此外，它们也都支持关键字参数。在Python中写成

1
2

def bar(*, a=None, b=None):
    print('a={}\tb={}'.format(a, b))

而在CL中则是

1
2

(defun bar (&key (a nil) (b nil))
  (format t "a=~A~8Tb=~A~%" a b))

尽管CL的&key仍然更清晰，但声明参数默认值的语法确实是Python更胜一筹。

细心的读者可能发现了，在Python中有一个叫做format的方法（属于字符串类），而在CL则有一个叫做format的函数。并且，从上面的例子来看，它们都负责生成格式化的字符串，那么它们有相似之处吗？

答案是否定的，CL的format简直就是格式化打印界的一股泥石流。

format的基本用法

不妨从上面的示例代码入手介绍CL中的format（下文在不引起歧义的情况下，简称为format）的基本用法。首先，它需要至少两个参数：

• 第一个参数控制了format将会把格式化后的字符串打印到什么地方。t表示打印到标准输出；
• 第二个参数则是本文的主角，名为控制字符串（control-string）。它指导format如何格式化。

听起来很神秘，但其实跟C语言的fprintf也没什么差别。

在控制字符串中，一般会有许多像占位符一般的命令（directive）。正如Python的format方法中，有各式各样的format_spec能够格式化对应类型的数据，控制字符串中的命令也有很多种，常见的有：

• 打印二进制数字的~B，例如(format t "~B" 5)会打印出101；
• 打印八进制数字的~O，例如(format t "~O" 8)会打印出10；
• 打印十进制数字的~D；
• 打印十六进制数字的~X，例如(format t "~X" 161)会打印出A1；
• 打印任意一种类型的~A，一般打印字符串的时候会用到。

另外，format的命令也支持参数。在Python中，可以用下列代码打印右对齐的、左侧填充字符0的、二进制形式的数字5

1

print('{:0>8b}'.format(5))

format函数也可以做到同样的事情

1

(format t "~8,'0B" 5)

到这里为止，你可能会觉得format的控制字符串，不过就是将花括号去掉、冒号换成波浪线，以及参数语法不一样的format方法的翻版罢了。

接下来，让我们进入format的黑科技领域。

format的高级用法

进制转换

前面列举了打印二、八、十，以及十六进制的命令，但format还支持其它的进制。使用命令~R搭配参数，format可以打印数字从2到36进制的所有形态。

1
2
3
4
5
6
7
8
9
10

(format t "~3R~%" 36)   ; 以 3进制打印数字36，结果为1100
(format t "~5R~%" 36)   ; 以 5进制打印数字36，结果为 121
(format t "~7R~%" 36)   ; 以 7进制打印数字36，结果为  51
(format t "~11R~%" 36)  ; 以11进制打印数字36，结果为  33
(format t "~13R~%" 36)  ; 以13进制打印数字36，结果为  2A
(format t "~17R~%" 36)  ; 以17进制打印数字36，结果为  22
(format t "~19R~%" 36)  ; 以19进制打印数字36，结果为  1H
(format t "~23R~%" 36)  ; 以23进制打印数字36，结果为  1D
(format t "~29R~%" 36)  ; 以29进制打印数字36，结果为  17
(format t "~31R~%" 36)  ; 以31进制打印数字36，结果为  15

之所以最大为36进制，是因为十个阿拉伯数字，加上二十六个英文字母正好是三十六个。那如果不给~R加任何参数，会使用0进制吗？非也，format会把数字打印成英文单词

1

(format t "~R~%" 123) ; 打印出one hundred twenty-three

甚至可以让format打印罗马数字，只要加上@这个修饰符即可

1

(format t "~@R~%" 123) ; 打印出CXXIII

天晓得为什么要内置这么冷门的功能。

大小写转换

你，作为一名细心的读者，可能留意到了，format的~X只能打印出大写字母，而在Python的format方法中，{:x}可以输出小写字母的十六进制数字。即使你在format函数中使用~x也是无效的，因为命令是大小写不敏感的（case insensitive）。

那要怎么实现打印小写字母的十六进制数字呢？答案是使用新的命令~(，以及它配套的命令~)

1

(format t "~(~X~)~%" 26) ; 打印1a

配合:和@修饰符，一共可以实现四种大小写风格

1
2
3
4

(format t "~(hello world~)~%")   ; 打印hello world
(format t "~:(hello world~)~%")  ; 打印Hello World
(format t "~@(hello world~)~%")  ; 打印Hello world
(format t "~:@(hello world~)~%") ; 打印HELLO WORLD

对齐控制

在Python的format方法中，可以控制打印出的内容的宽度，这一点在“format的基本用法”中已经演示过了。如果设置的最小宽度（在上面的例子中，是8）超过了打印的内容所占据的宽度（在上面的例子中，是3），那么还可以控制其采用左对齐、右对齐，还是居中对齐。

在CL的format函数中，不管是~B、~D、~O，还是~X，都没有控制对齐方式的选项，数字总是右对齐。要控制对齐方式，需要用到~<和它配套的~>。例如，下面的CL代码可以让数字在八个宽度中左对齐

1

(format t "|~8<~B~;~>|" 5)

打印内容为|101 |。~<跟前面提到的其它命令不一样，它不消耗控制字符串之后的参数，它只控制~<和~>之间的字符串的布局。这意味着，即使~<和~>之间是字符串常量，它也可以起作用。

1

(format t "|~8,,,'-<~;hello~>|" 5)

上面的代码运行后会打印出|---hello|：8表示用于打印的最小宽度；三个逗号（,）之间为空，表示忽略~<的第二和第三个参数；第四个参数控制着打印结果中用于填充的字符，由于-不是数字，因此需要加上单引号前缀；~;是内部的分隔符，由于它的存在，hello成了最右侧的字符串，因此会被右对齐。

如果~<和~>之间的内容被~;分隔成了三部分，还可以实现左对齐、居中对齐，以及右对齐的效果

1

(format t "|~24<left~;middle~;right~>|") ; 打印出|left    middle     right|

跳转

通常情况下，控制字符串中的命令会消耗参数，比如~B和~D等命令。也有像~<这样不消耗参数的命令。但有的命令甚至可以做到“一参多用”，那就是~*。比如，给~*加上冒号修饰，就可以让上一个被消耗的参数重新被消耗一遍

1

(format t "~8D~:*~8D~8D~%" 1 2) ; 打印出       1       1       2

在~8D消耗了参数1之后，~:*让下一个被消耗的参数重新指向了1，因此第二个~8D拿到的参数仍然是1，最后一个拿到了2。尽管控制字符串中看起来有三个~D命令而参数只有两个，却依然可以正常打印。

在format的文档中一个不错的例子，就是让~*和~P搭配使用。~P可以根据它对应的参数是否大于1，来打印出字母s或者什么都不打印。配合~:*就可以实现根据参数打印出单词的单数或复数形式的功能

1
2

(format t "~D dog~:*~P~%" 1) ; 打印出1 dog
(format t "~D dog~:*~P~%" 2) ; 打印出2 dogs

甚至你可以组合一下前面的毕生所学

1

(format t "~@(~R dog~:*~P~)~%" 2) ; 打印出Two dogs

条件打印

命令~[和~]也是成对出现的，它们的作用是选择性打印，不过比起编程语言中的if，更像是取数组某个下标的元素

1
2
3

(format t "~[~;one~;two~;three~]~%" 1) ; 打印one
(format t "~[~;one~;two~;three~]~%" 2) ; 打印two
(format t "~[~;one~;two~;three~]~%" 3) ; 打印three

但这个特性还挺鸡肋的。想想，你肯定不会无缘无故传入一个数字来作为下标，而这个作为下标的数字很可能本身就是通过position之类的函数计算出来的，而position就要求传入待查找的item和整个列表sequence，而为了用上~[你还得把列表中的每个元素硬编码到控制字符串中，颇有南辕北辙的味道。

给它加上冒号修饰符之后倒是有点用处，比如可以将CL中的真（NIL以外的所有对象）和假（NIL）打印成单词true和false

1

(format t "~:[false~;true~]" nil) ; 打印false

循环打印

圆括号和方括号都用了，又怎么能少了花括号呢。没错，~{也是一个命令，它的作用是遍历列表。例如，想要打印出一个列表中的每个元素，并且两两之间用逗号和空格分开的话，可以用下列代码

1

(format t "~{~D~^, ~}" '(1 2 3)) ; 打印出1, 2, 3

~{和~}之间也可以有不止一个命令，例如下列代码中每次会消耗列表中的两个元素

1

(format t "{~{\"~A\": ~D~^, ~}}" '(:a 3 :b 2 :c 1))

打印结果为{"A": 3, "B": 2, "C": 1}。如果把这两个format表达式拆成用循环写的、不使用format的等价形式，大约是下面这样子

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

; 与(format t "~{~D~^, ~}" '(1 2 3))等价
(progn
  (do ((lst '(1 2 3) (cdr lst)))
      ((null lst))
    (let ((e (car lst)))
      (princ e)
      (when (cdr lst)
        (princ ", "))))
  (princ #\Newline))

; 与(format t "{~{\"~A\": ~D~^, ~}}" '(:a 3 :b 2 :c 1))等价
(progn
  (princ "{")
  (do ((lst '(:c 3 :b 2 :a 1) (cddr lst)))
      ((null lst))
    (let ((key (car lst))
          (val (cadr lst)))
      (princ "\"")
      (princ key)
      (princ "\": ")
      (princ val)
      (when (cddr lst)
        (princ ", "))))
  (princ "}")
  (princ #\Newline))

这么看来，~{确实可以让使用者写出更紧凑的代码。

参数化参数

在前面的例子中，尽管用~R搭配不同的参数可以将数字打印成不同进制的形式，但毕竟这个参数是固化在控制字符串中的，局限性很大。例如，如果我想要定义一个函数print-x-in-base-y，使得参数x可以打印为y进程的形式，那么也许会这么写

1
2
3

(defun print-x-in-base-y (x y)
  (let ((control-string (format nil "~~~DR" y)))
    (format t control-string x)))

但format的灵活性，允许使用者将命令的前缀参数也放到控制字符串之后的列表中，因此可以写成如下更简练的实现

1
2

(defun print-x-in-base-y (x y)
  (format t "~VR" y x))

而且不只一个，你可以把所有参数都写成参数的形式

1
2
3
4
5
6
7

(defun print-x-in-base-y (x
                          &optional y
                          &rest args
                          &key mincol padchar commachar commainterval)
  (declare (ignorable args))
  (format t "~V,V,V,V,VR"
          y mincol padchar commachar commainterval x))

恭喜你重新发明了~R，而且还不支持:和@修饰符。

自定义命令

要在CL中打印形如2021-01-29 22:43这样的日期和时间字符串，是一件比较麻烦的事情

1
2
3
4
5

(multiple-value-bind (sec min hour date mon year)
    (decode-universal-time (get-universal-time))
  (declare (ignorable sec))
  (format t "~4D-~2,'0D-~2,'0D ~2,'0D:~2,'0D~%"
          year mon date hour min))

谁让CL没有内置像Python的datetime模块这般完善的功能呢。不过，借助format的~/命令，我们可以在控制字符串中写上要调用的自定义函数，来深度定制打印出来的内容。以打印上述格式的日期和时间为例，首先定义一个后续要用的自定义函数

1
2
3
4
5
6
7

(defun yyyy-mm-dd-HH-MM (dest arg is-colon-p is-at-p &rest args)
  (declare (ignorable args is-at-p is-colon-p))
  (multiple-value-bind (sec min hour date mon year)
      (decode-universal-time arg)
    (declare (ignorable sec))
    (format dest "~4D-~2,'0D-~2,'0D ~2,'0D:~2,'0D~%"
            year mon date hour min)))

然后便可以直接在控制字符串中使用它的名字

1

(format t "~/yyyy-mm-dd-HH-MM/" (get-universal-time))

在我的机器上运行的时候，打印内容为2021-01-29 22:51。

后记

format可以做的事情还有很多，CL的HyperSpec中有关于format函数的详细介绍，CL爱好者一定不容错过。

最后，其实Python跟CL并不怎么像。每每看到Python中的__eq__、__ge__，以及__len__等方法的巧妙运用时，身为一名Common Lisp爱好者，我都会流露出羡慕的神情。纵然CL被称为可扩展的编程语言，这些平凡的功能却依旧无法方便地做到呢。